拓扑排序中的邻接表表示

Question

我在Leetcode上看到了下面使用DFS实现的拓扑排序https://leetcode.com/problems/course-schedule/discuss/58509/18-22-lines-C++-BFSDFS-Solutions

现在让我感到困惑的部分是用于顶级排序的有向图的表示。图形创建如下：

vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<unordered_set<int>> graph(numCourses);
    for (auto pre : prerequisites)
        graph[pre.second].insert(pre.first);
    return graph;
}

让我困惑的是这一行：

    graph[pre.second].insert(pre.first);

大概该图被表示为邻接表；如果是这样，为什么每个节点都由传入边而不是传出边表示？有趣的是，如果我像这样翻转 pre.second 和 pre.first：

graph[pre.first].insert(pre.second);

顶级排序仍然有效。但是，似乎同一问题的大多数实现都使用前一种方法。这是否推广到所有有向图？我在本科阶段被教导有向图的邻接列表应该包含每个节点传出节点的列表。对于邻接列表的表示，传入节点和传出节点的选择是否任意？

Answer 1

对于只需要回答true或false的具体问题，翻转每条边都没有关系。这是因为当且仅当图没有环时，图是拓扑可排序的。但是如果你想要一个订单，它不起作用，正如你在 [[0, 1]] 和 [[1, 0]].

的不同结果中看到的那样

图形以何种方式保存取决于你如何解决问题。在这种情况下，我们需要知道每个节点（课程）的入度，并在每次从图中删除一个节点（参加课程）时更新它，以便我们知道是否可以删除一个节点（我们可以当入度为 0 时执行）。更新时，我们对删除的节点指向的每个节点减 1。如果你应用这种方法（大多数人都这样做），那么你应该如何保存图表就很清楚了

拓扑排序中的邻接表表示

Adjacency List Representation in Topological Sort

c++

algorithm

data-structures

graph-theory

topological-sort