c++ - 当接收到不明确的规范时，表示图形邻接表的数据结构

Question

我正在设计一个应该基于图形的应用程序。我不确定哪种是在内存中表示图形邻接列表的最佳方式。客户的要求很模糊，所以我必须做一些假设。图的节点是一些ID，但我不确定这些ID是否是连续的。当涉及到一般规范时，图论怎么说？如果是顺序的，节点数(N)也要限制最大ID，基本保证ID覆盖区间1,2…N .见下面的选项 A。如果它们不是连续的，则 ID 可能会从 1 跳到例如11、规范中可能会跳过一些自然数。见下文选项 B。除了 ID，还有一个 C++ 数据结构，我在其中存储多个信息(有效负载、连接的边等)我的算法有两个选项:

A. 将图形表示为 vector < Data > ， vector 的索引将表示节点ID。

B.将图表示为 map ，其中 Node ID 是键，Data 是存储值。

Map 允许我有随机 ID，假设输入数据是随机给出的。

文献(例如 DFS、BFS 或其他图文章)主要考虑选项 A，其中节点 ID 完全覆盖区间 [1..N]。我也会选择这个选项，因为它代表了一种普遍认可的符号。然后，将其添加到我的应用程序的文档/前提条件部分。

正确覆盖客户不明确规范的最佳选择是什么？

Answer 1

您可以选择将您的图表表示为您列出的两个选项的组合:有一个 Node包含两个成员的结构 - 一个整数 label以及您需要的其他结构。

图表将存储一个 std::vector<Node*> nodes; .但是，考虑到节点的标签与它在上述 vector 中的位置不匹配的限制，您需要将标签和 vector 索引之间的对应关系存储在 std::map<int, int> corresp; 中。

给定这个结构，如果你需要访问标签值为 11 的节点*，你会做 Node* node = nodes[corresp[label]];

此外，标签可以是任何其他类型，例如 std::string .唯一需要做的修改是将 map 的键类型更改为 std::string .