If topological sorting uses DFS, how can it succeed on disabled graphs?

Question

There is a gap in my knowledge, but I don’t know exactly where. Topological sorting can be done using a depth search, as wikipedia explains . However, I saw only the first deep search implemented for trees, where topological sorting is for DAG.

• is a tree a special case of DAG where the implied direction of the edges from the root node down
• Is the algorithm used for topological sorting not actually running DFS, just something very similar to it?

For example, topological sorting can handle disabled graphics, where DFS cannot cross a node without snapping ... can it?

Answer 1

Because when used for topological sorting, you run DFS on each node. If one of the children has already been visited by the previous DFS (color black). Then it is already inserted into the output vector, and so you are already doing the dependency.

Quoting your link (my selection):

The algorithm goes through each node of the graph in an arbitrary order , initiating a search by depth ...

Since the wikipedia article is a bit confusing (in my opinion), I will try to better describe the algorithm:

V: set of vertices E: set of edges E.adj(v): set of vertices adjacent to vertex v 0 function topological_sort(V,E): 1 for v in V: 2 paint v white 3 4 for v in V: 5 if v is white: 6 dfs(v) 7 function dfs(v): 8 paint v grey 9 for child in E.adj(v) 10 if child is white: 11 dfs(child) 12 paint v black 13 push v to output 

We can easily calculate the complexity:

• We draw a vertex of white, gray, and black once onto the vertex: O(V)
• We check the color of the vertex in line 5 once per vertex: O(V)
• We check the color of the vertex in line 10 once per edge: O(E)
• We push the vertex to output on line 13 once per vertex: O(V)

So, the final complexity: O(V+E) . It is quite effective.

One of the advantages of this algorithm is that it does not need to change the input chart. We can easily implement coloring using a temporary hash table with size in O(V) . Some other topological sorting algorithm requires destroying the graph when it is executed (by removing edges). This would require you to copy the graph before starting topological sorting if you still need the graph after sorting.

Answer 2

You might want to add a new “source” node to your graph and connect it to every other node with a directed edge. Then start searching / navigating from this new node. This approach may or may not suit your needs.