c++ - 解析输入文件以创建有向图 C++

Question

所以我开始了一个关于有向图和拓扑排序的项目。我正在寻找最有效的方法来解析以下形式的类(class)输入文件:

COURSE_1    COURSE_2    

其中 COURSE_1 是 COURSE_2 的先决条件

NONE    COURSE_3

其中 COURSE_3 没有先决条件。

显然，所有顶点标签都是字符串。我创建了一个包含数据成员的 Graph 类来存储顶点、边和顶点标签。稍后，我将添加方法以进行拓扑排序并找到从一个顶点到另一个顶点的最短路径。考虑到这些 future 计划，我的问题是使用邻接表会更好吗？或矩阵？另外，从输入文件填充图形的最有效方法是什么？我最初的想法是使用邻接表。由于在编译时不知道图形的大小我的想法

std::vector<std::list<std::string>> adjacencyList;

另外，我想创建一个辅助函数来解析输入文件。类似的东西

void populateGraph(std::string filename, Graph* graph)

我是不是完全走错了方向？

Answer 1

你在很多事情上都走在正确的轨道上。

如果您可以假设您将遇到的所有输入都是 NONE和 COURSE_X并且您可以假设所有 X 形成一个连续的整数区间，从 1(或 0)开始并跨越到顶点数，那么您可以在内部将顶点视为数字。如果不是这种情况，您可以为每个顶点标签分配一个数字(例如使用 std::unordered_map)并且无论如何都具有这个抽象结构。

现在，如果你选择坚持使用这个模型，使用起来很方便，因为你的整个图可以表示为 std::vector<std::list<int>> .你可以用 int 代替如果您想存储更多关于边的信息，例如标签、权重等，请使用某种结构类型。无论何时您想要访问特定节点的邻接列表，您只需访问该节点 ID 下的 vector 单元。

显然这是一个基于邻接表的解决方案。一般来说，这对稀疏图很有用。这样想:如果您对稀疏图使用矩阵，那么分配的内存的很大一部分将不会被使用。使用邻接图消除了这一点，但是它消除了对任意边的恒定访问时间。这意味着检查给定边是否存在可能需要线性时间。话虽如此，我不希望您以拓扑排序使用该检查。但是，如果您选择使用矩阵，您仍然需要将顶点映射到数字，该部分保留。

最后但同样重要的是，您可以使用指针而不是整数 ID。基本上您不会使用 id 在 vector 中查找顶点，而是通过存储的指针直接访问顶点。您很可能仍然需要字符串 -> 指针映射，至少对于图形创建而言。