Topological sorting with DFS. Another algorithm for sorting DAG nodes topologically. The idea is simple: perform
a DFS and sort the nodes by inverse finish time. To easily get a linear running time, you can instead simply append
nodes to your ordering as they receive their finish times in DFS. (See Listing 5-7.)
Tremaux’s algorithm. Like Ore’s algorithm, this is designed to be executed in person, while walking through a maze.
The pattern traced by a person executing Tremaux’s algorithm is essentially the same as that of DFS. (See Chapter 5.)
Do'stlaringiz bilan baham: |