We just need to store both incoming and outgoing edges and slightly modify the adjacency lists.
1. Represent the graph with two lists on each vertex (incoming edges and outgoing edges)
2. Make an empty queue Q;
3. Make an empty topologically sorted list T;
4. Push all items with no predecessors in Q;
5. While Q is not empty
a. Dequeue from Q into u;
b. Push u in T;
c. Remove all outgoing edges from u;
6. Return T;
This approach will give us a better performance than the “brute force” approach. The running time complexity is O(|V| + |E|). The problem is that we need additional space and an operational queue, but this approach is a perfect example of how by using additional space you can get a better performing algorithm.
Read full article from Computer Algorithms: Topological Sort Revisited
1. Represent the graph with two lists on each vertex (incoming edges and outgoing edges)
2. Make an empty queue Q;
3. Make an empty topologically sorted list T;
4. Push all items with no predecessors in Q;
5. While Q is not empty
a. Dequeue from Q into u;
b. Push u in T;
c. Remove all outgoing edges from u;
6. Return T;
This approach will give us a better performance than the “brute force” approach. The running time complexity is O(|V| + |E|). The problem is that we need additional space and an operational queue, but this approach is a perfect example of how by using additional space you can get a better performing algorithm.
Read full article from Computer Algorithms: Topological Sort Revisited
No comments:
Post a Comment