Question

Topological sort of a Directed Acyclic graph is?

(a) Always unique

(b) Always Not unique

(c) Sometimes unique and sometimes not unique

(d) Always unique if graph has even number of vertices

The question was posed to me during an interview for a job.

I'm obligated to ask this question of Topological Sort in chapter Miscellaneous of Data Structures & Algorithms II

Answer 1

Correct choice is (c) Sometimes unique and sometimes not unique

To explain: The topological sort of a graph can be unique if we assume the graph as a single linked list and we can have multiple topological sort order if we consider a graph as a complete binary tree.