CODEWITHSUNDEEP
graphgraph-algorithmdirected-acyclic-graphsundirected-graph
Mehmed
Mehmed

Reputation: 3040

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?

Upvotes: 11

Views: 10807

Answers (2)

arviman
arviman

Reputation: 5255

Topological sort is only valid when there are no cycles. You can use a tie-breaker heuristic like break the last outgoing path from the least in-degree vertex. What i do in my projects is just output the potential tie-breakers and use human judgement to break the cycle.

The closest to what you would want in this case is 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.

Edit for the case of undirectional and fleshing out the idea for using the centroid of a graph to convert undirectional to directional - you can use the idea as follows: start with each vertex v and perform dfs from it, assuming the edge you traverse to any unvisited node is directional (also mark the edge as completed so a reverse path isn't possible) and calculate the max depth encountered for each such traversal and store it for every node. The min such depth among all nodes is the centroid of the graph (for eg. a practical use will be a hub in a flight graph as it's easily accessible to all other regions).

Now use the dfs traversal from the centroid to generate your directional graph and then generate topological sort. (you can use either time of first seen algorithm or kahn's remove 0 in-degree vertex, decrement neighbours and add to stack logic)

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 372814

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.

Upvotes: 17

Related Questions