Question

When the topological sort of a graph is unique?

(a) When there exists a hamiltonian path in the graph

(b) In the presence of multiple nodes with indegree 0

(c) In the presence of single node with indegree 0

(d) In the presence of single node with outdegree 0

I have been asked this question during a job interview.

My question comes from Topological Sort topic in portion Miscellaneous of Data Structures & Algorithms II

Answer 1

Right answer is (a) When there exists a hamiltonian path in the graph

Easiest explanation - A hamiltonian path exists in a Directed Acyclic Graph when all pairs of consecutive vertices are in sorted order and are connected by edges. In such a case, there exists a unique topological sorting order.