algorithm - 图算法计算节点度

Question

我正在尝试为 DAG 实现拓扑排序算法。 ( http://en.wikipedia.org/wiki/Topological_sorting )这个简单算法的第一步是找到度数为零的节点，如果没有二次算法，我找不到任何方法来做到这一点。

我的图形实现是一个简单的邻接表，基本过程是循环遍历每个节点，每个节点遍历每个邻接表，因此复杂度为 O(|V| * |V|).

拓扑排序的复杂度是O(|V| + |E|)，所以我认为必须有一种方法以线性方式计算所有节点的度数。

Answer 1

您可以在从图中删除节点的同时维护所有顶点的入度，并维护零入度节点的链表:

indeg[x] = indegree of node x (compute this by going through the adjacency lists)
zero = [ x in nodes | indeg[x] = 0 ]
result = []
while zero != []:
    x = zero.pop()
    result.push(x)
    for y in adj(x):
        indeg[y]--
        if indeg[y] = 0:
            zero.push(y)

也就是说，使用 DFS 的拓扑排序在概念上要简单得多，恕我直言:

result = []
visited = {}
dfs(x):
    if x in visited: return
    visited.insert(x)
    for y in adj(x):
        dfs(y)
    result.push(x)
for x in V: dfs(x)
reverse(result)