Topological Sort pseudocode

Question

I have the following pseudocode for Topological Sort

Repeat:
Find a vertex with no successor
Remove it from graph
Put It at beginning of list
Until graph is empty

My question is, should it be amended to "Find a vertex with no predecessor"?

Answer 1

Yes, it should. Successor doesn't make sense, unless, of course, you reversed all edges before performing the topological sort.

Answer 2

A topological sort is a way of drawing a graph that all edges go forward(horizontally). Suppose you have a graph G (G should be a DAG)and you want to do a topological sot. Pseudocode for topological sort: Repeat: Find a vertex with no incoming edges Remove the vertex and edges in G Put It at beginning of list Until graph is empty

You can also use DFS for topological sort. That is run DFS on your G, as each time a vertex is finished, inserts its identifier at the head of your topological sort list. When all the vertices in G have been discovered, the completed list is topological sort. The time complexity for this algorithm is the same with DFS which is big O of (V + E).