graphgraph-algorithmdirected-acyclic-graphsundirected-graph

Topological sort on directed and undirected graphs using DFS algorithm


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?


Solution

  • 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.