Topological sort on directed and undirected graphs using DFS algorithm

Question

I can determine the topological sort of a directed graph using DFS algorithm. If there are no cycles, I assume the topological order I found is valid. If there is a cycle, I assume the topological order is useless. Am I correct so far?

What about undirected graphs? Is "topological sort of an undirected graph" a valid statement? Should the graph have to be directed acyclic graph for topological sort?

Answer 1

It’s hard to pin down what a topological ordering of an undirected graph would mean or look like. A topological ordering of a directed graph is one where for every edge (u, v) in the graph, u appears in the ordering before v. If you have a directed graph, the edges (u, v) and (v, u) are not the same as one another, and the edges have a clear start and endpoint.

However, in an undirected graph, edges have no start and end point - nodes either are mutually adjacent or mutually not adjacent. So what would a topological ordering look like? Given an edge {u, v} = {v, u}, it’s ambiguous which node would have to come first in the ordering, since neither one occupied a privileged position over the other.

Answer 2

The closest to what you would want in this case an ordering that goes from the "leaves" of such a graph towards the centroid of the graph. This means that the right most items (or the top of the stack) of the ordering would have the minimum height (i.e distance) to any other node in the graph. For this you can use a modification of Kahn's algorithm. Instead of starting with 0 indegree vertices you'd start with all leaves having 1 indegree vertices. Remember that in an undirected graph, all node's edges are bidirectional, so it's impossible to have a 0 indegree vertex. Then you remove all 1 indegree vertices, push to your stack, update the indegree vertices of the others and repeat until all vertices in the graph have been added to your stack.

Using DFS doesn't make sense here since your result will vary based on the ordering of the source vertex in the graph that you choose.