MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -Topological sort is equivalent to which of the traversals in trees? Explanation: In pre-order traversal of trees, we process the root first and then child from left to right. 8.

Detailed explanation-2: -Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Detailed explanation-3: -Topological Sort by BFS: In BFS implementation of the Topological sort we do the opposite: We look for for edges with no inbound edges. And consequently in BFS implementation we don’t have to reverse the order in which we get the vertices, since we get the vertices in order of the topological ordering.

Detailed explanation-4: -The best data structure used to implement topological sort is stack, since topological sort based on depth first traversal.

Detailed explanation-5: -Topological sort is a DFS-based algorithm on a directed acyclic graph (DAG). Topological ordering is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles.