所以我正在开始一个关于有向图和拓扑排序的项目 . 我正在寻找解析表单中的课程输入文件的最有效方法：
COURSE_1 COURSE_2
其中COURSE_1是COURSE_2的先决条件
NONE COURSE_3
其中COURSE_3没有先决条件 .
显然，所有顶点标签都是字符串 . 我创建了一个带有数据成员的 Graph 类来存储顶点，边和顶点标签 . 稍后，我将添加拓扑排序方法，并找到从一个顶点到另一个顶点的最短路径 . 鉴于这些未来的计划，我的问题是，使用邻接列表会更好吗？还是矩阵？从输入文件填充图形的最有效方法是什么？我最初的想法是使用邻接列表 . 由于图形的大小在编译时不知道我的想法
std::vector<std::list<std::string>> adjacencyList;
另外，我想创建一个辅助函数来解析输入文件 . 有点像
void populateGraph(std::string filename, Graph* graph)
我在这里完全走错了方向吗？
2 回答
你有很多东西在正确的轨道上 .
如果您可以假设您将遇到的所有输入都只是
NONE和COURSE_X并且您可以假设所有Xes从1（或0）开始形成连续的整数间隔并且跨越到顶点数量，那么您可以只处理顶点作为数字在内部 . 如果不是这种情况，您可以为每个顶点标签指定一个数字（例如，使用std :: unordered_map）并且仍然具有此抽象结构 .现在，如果您选择坚持使用此模型，则使用起来非常方便，因为您的整个图形可以表示为
std::vector<std::list<int>>. 如果要存储有关边缘的更多信息（如标签，权重等），则可以使用某种结构类型替换int. 每当您想要访问节点ID下的特定节点's adjacency list, you just access the vector' s单元格时 .显然，这是一个基于邻接列表的解决方案 . 它使用矩阵作为稀疏图，不会使用分配内存的很大一部分 . 使用邻接图消除了这一点，它消除了对任意边缘的恒定访问时间 . 这意味着可以花费线性时间来检查给定边缘是否存在 . 话虽这么说，我不希望你在拓扑排序中使用该检查 . 但是，如果您选择使用矩阵，则仍需要将顶点映射到数字，以保留该部分 .
最后但并非最不重要的是，您可以使用指针而不是整数ID . 基本上你不会使用id在向量中查找顶点，但是你可以通过存储的指针直接访问顶点 . 您很可能仍需要字符串 - >指针映射，至少对于图形创建 .
关于邻接列表和矩阵之间的选择，它取决于图形的性质以及您打算用它做什么 .
例如，请参阅此thread .
另外，您是否看过boost库为图表提供的内容？还有lemon作为替代方案 . 可能值得检查您打算实施的内容是否已存在 .