f********e
发帖数: 166 | 1 describe an algorithm to schedule jobs, each job depend on some other jobs
. How to detect cycle?
Topological sort?? | f*******t
发帖数: 7549 | | f********e
发帖数: 166 | 3 谢谢楼上的！
是不是还要首先检测是否有环，有环的话Topological sort就不work了吧？ | y*******g
发帖数: 6599 | 4 Topological sort过程中可以检测环 | c**j
发帖数: 103 | 5 Graph: cycle detection: using colored DFS. http://www.eecs.berkeley.edu/~kamil/teaching/sp03/041403.pdf (Java)
http://www.cs.utk.edu/~parker/Courses/CS302-fall05/Notes/GraphIntro/ (C++
In order to detect cycles, we use a modified depth first search called a
colored DFS. All nodes are initially
marked white. When a node is encountered, it is marked grey, and when its
descendants are completely
visited, it is marked black. If a grey node is ever encountered, then there
is a cycle | f*******t
发帖数: 7549 | 6 拓扑排序每次找没有入度的节点，找不到的话就说明有环存在 |
|
