Final answer:
Using BFS for topological sorting of a DAG can fail to produce a valid ordering, as shown by a simple DAG where BFS could result in a sequence that does not respect all dependency orders - hence, algorithms like Kahn's or DFS are preferred.
Step-by-step explanation:
The student's problem involves finding a counterexample to demonstrate that topological sorting of a Directed Acyclic Graph (DAG) cannot be correctly performed by simply using Breadth-First Search (BFS) from a vertex with an in-degree of 0 and then listing the vertices based on their distance from the starting vertex.
Consider the following simple DAG, which has the vertex set V = {A, B, C, D} and edge set E = {(A, B), (A, C), (B, D), (C, D)}:
- A has in-degree of 0
- B has in-degree of 1
- C has in-degree of 1
- D has in-degree of 2
Starting BFS from A would give us A at distance 0, both B and C at distance 1, and D at distance 2. Therefore, BFS would suggest the order A, B, C, D. This is a valid topological sort. However, consider another DAG with vertex set V = {A, B, C} and edge set E = {(A, B), (B, C), (A, C)}:
- A has an in-degree of 0
- B has an in-degree of 1
- C has in-degree of 2
Starting BFS from A, the possible orders could be either A, B, C or A, C, B, depending on the order in which neighbors are visited by BFS. However, A, C, B is not a valid topological order because it does not respect the dependency of C on B.
This shows that BFS does not necessarily yield a correct topological sort and illustrates why an algorithm like Kahn's or DFS-based sorting must be used instead.