Topological Sort

Question

Given a directed acyclic graph G=(V,E), a topological sort T is an ordering of vertices, such that, for each directed edge(u,v) in E, u comes before v in T. Which is the best possible algorithm to perform a topological sort on the graph.

Answer 1

1. DFS the graph: as each vertex is finished, insert it in a linked list.

2. Return the linked list of vertices.

Total cost: O(|V| + E).

Comments

As confirmed by Prof. Arora, this answer is incorrect. Consider the case we have a directed graph who has 3 nodes 1,2,3, such that, 1->2 and 3->2, If we DFS it and store the vertices in a linked list, it may be “3,2,1”, “1,2,3” or “2,1,3”, “2,3,1”.
However, the topological sort should be “3,1,2” or “1,3,2” which u comes before v in every edge (u,v).

---

Hi. It seems my algorithm can't give right answer with your input. I think one of the best ways to handle topological sort problem is BFS. First enqueue all vertices which has 0 in-degree. Then expand them and remove 1 in-degree to the connected vertices. Finally we will get the right order of topological sort. Thanks for replying!

Answer 2

I think the answer might be:

First, use DFS to get the start point v' in the graph

that is, v' does not have a parent node directed to it

which means v' is the starting vertex

Then, start at v', use BFS to examine each branch of each parent node

for each depth, sort the detected child node by the direction relations among them

this is to make sure the lower level child nodes are found and sorted to be added to the main sequence

at the end of BFS, it will get the topological sort

time for DFS is O(n), BFS is O(n) and multiply O(n) for the inner sorting procedure

total time complexity T(n) is O(n^2)