计算节点度的图算法
计算节点度的图算法
提问于 2014-03-06 17:33:34
我在尝试实现DAG的拓扑排序算法。(sorting)这个简单算法的第一步是找到零度的节点，如果没有二次算法，我就找不到任何方法来做到这一点。
我的图形实现是一个简单的邻接列表，其基本过程是遍历每个节点，对每个节点遍历每个邻接列表，因此复杂度将是O(|V| * |V|)。
拓扑排序的复杂性是O(|V| + |E|)，所以我认为必须有一种方法来计算所有节点的线性度。
回答 3
Stack Overflow用户
回答已采纳
发布于 2014-03-06 17:44:24
您可以在从图中删除节点的同时维护所有顶点的索引树，并维护一个由零个索引树节点组成的链接列表：
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进行拓扑排序在概念上要简单得多，IMHO：
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)Stack Overflow用户
发布于 2017-02-27 06:05:29
您可以在o(|v|+|e|)中实现它。按照下列步骤执行：
- 创建两个列表
inDegree，outDegree，它为每个节点保持输入和输出边沿的计数，将其初始化为0。 - 现在遍历给定的邻接表，对于图g中的
edge (u,v)，增加u的outdegree计数，对v增加indegree的增量计数。 - 您可以遍历
o(v +e)中的邻接列表，对于o(|v|+|e|)中的每个u都有索引和度。
Stack Overflow用户
发布于 2014-03-06 17:49:28
您还可以使用DFS进行拓扑排序。在处理每个节点后，您将不需要额外的传递来计算内度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22231815
复制相关文章
相似问题
腾讯云开发者
