我读了一些声称可以在线性时间内进行拓扑排序的地方.这里提出了一个这样的主张 - 他们说 - O(V + E) http://en.wikipedia.org/wiki/Topological_sorting
但他们拥有的算法:对于每个内部循环都有一个.我认为这使它成为O(n ^ 2).
然后我在幻灯片19上找到了这个解决方案 - https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf - 显然他们正在寻找更快的方法 - 但是在第3步的第二步,他们正在寻找所有相邻节点(在while循环内),因此也使它成为O(n ^ 2).
这种情况也是如此 - http://www.geeksforgeeks.org/topological-sorting/
我在这里错过了什么？
每个内部都有一个while循环.我认为这使它成为O(n ^ 2).
如果使用图形的邻接列表表示,则在内部循环中只查看每个边缘一次,因此它是O(max {n,m})= O(n + m).
当然它也是O(n ^ 2),但这不是一个紧张的上限.
他们正在寻找所有相邻节点(在while循环内),因此也使它成为O(n ^ 2).
同样,如果您使用邻接列表来表示图形,它也是O(n + m).