Topological OrderingWhat is a Topological Ordering of a Graph?A topological ordering of a directed acyclic graph G is a linear ordering of all its nodes as follows. If G contains an edge e=(u,v), node u appears before v in the ordering. If G is contains cycles, no topological ordering is possible. Where can I use a Topological Ordering?Directed acyclic graphs can be used to model tasks and precedences among the tasks, that is, there is an edge from A to B if I have to do task A before I can do task B. A topological ordering of such a graph gives an order for the tasks that respects the precedences. Example of how to compute a topological ordering in graph. Running TimeThe running time is linear in the size of the graph (O(|V|+|E|)). |
See also:GraphWin for visualizing graphs and graph algorithms Manual Entries: |