图算法计算节点度数

Question

我正在尝试为DAG实现拓扑排序算法。 (http://en.wikipedia.org/wiki/Topological_sorting) 这个简单算法的第一步是查找度数为零的节点，但是我无法找到任何一种不使用二次算法的方法来完成这一步骤。

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

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

- IgnazioC

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)

话虽如此，使用深度优先搜索进行拓扑排序在概念上要简单得多，个人认为：

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)

- Niklas B.

---

我认为他在询问如何在你的代码中快速计算indeg()。 - Leo

@linwei：哦，现在我明白你在评论中的意思了。indeg(y)是一个变量，不是一个函数。它已经有了正确的值，我们只需要读取它。我试图让这一点更清楚了。 - Niklas B.

我明白了。只是在我阅读完OP的问题之后，我也很好奇，你最初如何在线性时间内获得每个节点的所有入度？ - Leo

@Linwei：对所有的 x 进行初始化 indeg[x] = 0。对于每一条边(v,w)，增加 indeg[w]。 - Niklas B.

在从用户输入中获取数据时，可以轻松地找到入度。这很可能是一个循环，因此是线性的。 - jack_1729

Answer 2

你可以在 o(|v|+|e|) 的时间复杂度内完成。按照下面给出的步骤操作：

1. 创建两个列表inDegree和outDegree，用于维护每个节点的入度和出度计数，并将其初始化为0。
2. 现在遍历给定的邻接表，在图g中对于边(u,v)，增加u的outdegree计数，增加v的indegree计数。
3. 您可以在o(v+e)的时间复杂度内遍历邻接表，并在o(|v|+|e|)的时间复杂度内获得每个u的入度和出度。

- Bhagwati Malav

Answer 3

你提到的访问相邻节点的复杂度并不完全正确（O(n²)），因为如果你仔细思考，你会发现这更像是一次BFS搜索。所以，你只访问每个节点和每条边一次。因此，复杂度是O(m+n)。其中，n是节点数，m是边数。

- Ghasem

Answer 4

你也可以使用深度优先搜索进行拓扑排序。在处理每个节点后，您无需额外的遍历来计算入度。

http://www.geeksforgeeks.org/topological-sorting/

- Delta