解析输入文件以创建有向图 C++
Parsing an input file to create a directed graph C++
所以我开始了一个关于有向图和拓扑排序的项目。我正在寻找最有效的方法来解析以下形式的课程输入文件：
COURSE_1 COURSE_2
其中 COURSE_1 是 COURSE_2 的先决条件
NONE COURSE_3
其中 COURSE_3 没有先决条件。
显然，所有顶点标签都是字符串。我创建了一个 Graph class 数据成员来存储顶点、边和顶点标签。稍后，我将添加方法以进行拓扑排序并找到从一个顶点到另一个顶点的最短路径。考虑到这些未来计划，我的问题是使用邻接表会更好吗？或矩阵？另外，从输入文件填充图形的最有效方法是什么？我最初的想法是使用邻接表。由于在编译时不知道图形的大小我的想法
std::vector<std::list<std::string>> adjacencyList;
另外，我想到了创建一个辅助函数来解析输入文件。类似于
void populateGraph(std::string filename, Graph* graph)
我是不是完全走错了方向？
关于邻接表和矩阵之间的选择，这取决于你的图的性质和你打算用它做什么。
例如，参见此 thread。
你在很多事情上都走在正确的轨道上。
如果你可以假设你将遇到的所有输入只是 NONE 和 COURSE_X 并且你可以假设所有 X 形成一个连续的整数区间，从 1（或 0）开始跨越到顶点的数量，那么你可以在内部将顶点视为数字。如果不是这种情况，您可以为每个顶点标签分配一个数字（例如使用 std::unordered_map）并且无论如何都具有这个抽象结构。
现在，如果你选择坚持使用这个模型，使用起来很方便，因为你的整个图可以表示为std::vector<std::list<int>>。如果你想存储更多关于边缘的信息，比如标签、权重等，你可以用一些结构类型替换 int 。每当你想访问特定节点的邻接列表时，你只需访问该节点下的矢量单元id.
显然这是一个基于邻接表的解决方案。一般来说，这对稀疏图很有用。这样想：如果您对稀疏图使用矩阵，那么分配的内存的很大一部分将不会被使用。使用邻接图消除了这一点，但是它消除了对任意边的恒定访问时间。这意味着检查给定边是否存在可能需要线性时间。话虽如此，我不希望您以拓扑排序使用该检查。但是，如果您选择使用矩阵，您仍然需要将顶点映射到数字，该部分保留。
最后但同样重要的是，您可以使用指针而不是整数 ID。基本上您不会使用 id 在向量中查找顶点，而是通过存储的指针直接访问顶点。您很可能仍然需要字符串 -> 指针映射，至少对于图形创建而言。
所以我开始了一个关于有向图和拓扑排序的项目。我正在寻找最有效的方法来解析以下形式的课程输入文件：
COURSE_1 COURSE_2
其中 COURSE_1 是 COURSE_2 的先决条件
NONE COURSE_3
其中 COURSE_3 没有先决条件。
显然，所有顶点标签都是字符串。我创建了一个 Graph class 数据成员来存储顶点、边和顶点标签。稍后，我将添加方法以进行拓扑排序并找到从一个顶点到另一个顶点的最短路径。考虑到这些未来计划，我的问题是使用邻接表会更好吗？或矩阵？另外，从输入文件填充图形的最有效方法是什么？我最初的想法是使用邻接表。由于在编译时不知道图形的大小我的想法
std::vector<std::list<std::string>> adjacencyList;
另外，我想到了创建一个辅助函数来解析输入文件。类似于
void populateGraph(std::string filename, Graph* graph)
我是不是完全走错了方向？
关于邻接表和矩阵之间的选择，这取决于你的图的性质和你打算用它做什么。
例如，参见此 thread。
你在很多事情上都走在正确的轨道上。
如果你可以假设你将遇到的所有输入只是 NONE 和 COURSE_X 并且你可以假设所有 X 形成一个连续的整数区间，从 1（或 0）开始跨越到顶点的数量，那么你可以在内部将顶点视为数字。如果不是这种情况，您可以为每个顶点标签分配一个数字（例如使用 std::unordered_map）并且无论如何都具有这个抽象结构。
现在，如果你选择坚持使用这个模型，使用起来很方便，因为你的整个图可以表示为std::vector<std::list<int>>。如果你想存储更多关于边缘的信息，比如标签、权重等，你可以用一些结构类型替换 int 。每当你想访问特定节点的邻接列表时，你只需访问该节点下的矢量单元id.
显然这是一个基于邻接表的解决方案。一般来说，这对稀疏图很有用。这样想：如果您对稀疏图使用矩阵，那么分配的内存的很大一部分将不会被使用。使用邻接图消除了这一点，但是它消除了对任意边的恒定访问时间。这意味着检查给定边是否存在可能需要线性时间。话虽如此，我不希望您以拓扑排序使用该检查。但是，如果您选择使用矩阵，您仍然需要将顶点映射到数字，该部分保留。
最后但同样重要的是，您可以使用指针而不是整数 ID。基本上您不会使用 id 在向量中查找顶点，而是通过存储的指针直接访问顶点。您很可能仍然需要字符串 -> 指针映射，至少对于图形创建而言。