CODEWITHSUNDEEP
directed-graphtopological-sort
TRUMPI
TRUMPI

Reputation: 33

checking if a directed graph has only single one topological sort

I'm trying to write pseudo-code for an algorithm that suppose to check whether a directed graph has only single one topological ordering. I've already come up with the pseudo-code for a topological sort (using DFS), but it does not seem to help me much. I wonder if there is no sinks in that graph -then there's not a single one topological ordering (might it help?).

Upvotes: 1

Views: 2729

Answers (1)

Victor
Victor

Reputation: 771

This is an improvement of this answer, as the best possible runtime is improved when it starts at a vertex with no outgoing edges.

If your directed graph has N vertices, and you have exactly one starting vertex with indegree 0,

  • Do DFS (but only on the starting vertex) to get a topological sort L.
  • If L doesn't have N vertices, either some vertices are unreachable (those are part of a cycle) or you need another starting vertex (so there are multiple toposorts).
  • For i in [0,N-2],
    • If there is no edge from L[i] to L[i+1],
      • Return false.
  • Return true.

Alternatively, modify Kahn’s algorithm: if more than one vertex is in the set (of vertices of indegree 0) while the algorithm is running, return false. Otherwise, return true.

Upvotes: 3

Related Questions