If topological sort uses DFS, how can it succeed on disconnected graphs?

Question

There's a gap in my knowledge but I'm not sure exactly where. Topological sorting can be done using depth first search, as wikipedia explains. However I've only seen depth first search implemented for trees, where as topological sort is for DAGs.

1. is a tree a special case of a DAG where the implied direction of the edges is from the root node down
2. is the algorithm used for topological sort not really doing DFS, only something a lot like it?

For example, topological sort can handle disconnected graphs where as DFS cannot traverse a node with no edges connecting it...can it?

Answer 1

Because when used for topological sort you do a DFS on every nodes. If one of the children is already visited by a previous DFS (colored black). Then it is already pushed in the output vector and so you the dependency is already done.

Quoting your link (emphasis mine):

The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search ...

As 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 compute the complexity:

• We paint a vertex white, grey and black once per vertex: O(V)
• We check the color of the vertex at line 5 once per vertex: O(V)
• We check the color of the vertex at line 10 once per edge: O(E)
• We push the vertex to output at line 13 once per vertex: O(V)

So the final complexity is: O(V+E). It is pretty efficient.

One of the strength of this algorithm is that it doesn't need to modify the input graph. We can easily implement coloring by a temporary hashtable with a size in O(V). Some other topological sort algorithm requires to destroy the graph when they proceed (by removing edges). This would require to copy the graph before running the toplogical sort if you still need the graph after the sort.