我正在尝试为DAG实现拓扑排序算法。 (http://en.wikipedia.org/wiki/Topological_sorting) 这个简单算法的第一步是查找度数为零的节点,但是我无法找到任何一种不使用二次算法的方法来完成这一步骤。
我的图形实现是一个简单的邻接表,基本过程是循环遍历每个节点,对于每个节点遍历每个邻接列表,因此复杂度将为
拓扑排序的复杂度为
我的图形实现是一个简单的邻接表,基本过程是循环遍历每个节点,对于每个节点遍历每个邻接列表,因此复杂度将为
O(|V| * |V|)
。拓扑排序的复杂度为
O(|V| + |E|)
,因此我认为必须有一种以线性方式计算所有节点度数的方法。
indeg(y)
是一个变量,不是一个函数。它已经有了正确的值,我们只需要读取它。我试图让这一点更清楚了。 - Niklas B.x
进行初始化indeg[x] = 0
。对于每一条边(v,w)
,增加indeg[w]
。 - Niklas B.