Past exam question: 2064 Jestha, Q9
Open in the Padhaiko appQuestion
Describe a strongly and weakly connected graph with suitable examples. Write algorithms for Depth-First and Breath-First topological sorting and trace your algorithms for a given acyclic directed graph.
[figure: directed acyclic graph on 8 vertices 0, 1, 2, 3, 4, 5, 6, 7 with directed edges 0->2, 2->1, 2->3, 2->4, 1->3, 3->4, 3->5, 5->4, 5->7, 4->6]
Solution
Strongly vs. Weakly Connected Directed Graphs:
- Strongly Connected: Every vertex is reachable from every other vertex along directed edges (for all , paths and exist). Example: A directed 3-cycle
A -> B -> C -> A. - Weakly Connected: Not strongly connected, but replacing all directed edges with undirected edges yields a connected graph. Example:
A -> B -> C(Chas no directed path back toA).
BFS (Kahn's) and DFS Topological Sorting Algorithms:
Algorithm BFS_TOPOSORT(V, adj):
1. Compute indeg[v] for all v in V; enqueue all v with indeg[v] == 0 into Q
2. While Q not empty:
u = DEQUEUE(Q); append u to order
For each v in adj[u]:
indeg[v]--; if indeg[v] == 0: ENQUEUE(Q, v)
Algorithm DFS_TOPOSORT(V, adj):
1. Mark all v unvisited; empty stack S
2. For each v in V: if !visited[v]: DFS_VISIT(v)
3. Pop all vertices from S to form topological order
DFS_VISIT(u): visited[u]=TRUE; for v in adj[u]: if !visited[v]: DFS_VISIT(v); PUSH(S, u)Trace on the Given DAG (0..7): Edges: 0->2, 2->1, 2->3, 2->4, 1->3, 3->4, 3->5, 5->4, 5->7, 4->6.
- 1. BFS (Kahn's) Trace: Initial in-degrees:
0:0, 1:1, 2:1, 3:2, 4:3, 5:1, 6:1, 7:1. QueueQ = [0]:- Dequeue
0indeg[2]=0 - Dequeue
2indeg[1]=0, indeg[3]=1, indeg[4]=2 - Dequeue
1indeg[3]=0 - Dequeue
3indeg[4]=1, indeg[5]=0 - Dequeue
5indeg[4]=0, indeg[7]=0 - Dequeue
4indeg[6]=0 - Dequeue
7, then6. - BFS Topological Order:
0, 2, 1, 3, 5, 4, 7, 6.
- Dequeue
- 2. DFS Trace (visiting neighbors in ascending numeric order):
0 -> 2 -> 1 -> 3 -> 4 -> 6(push6, push4), backtrack to3 -> 5 -> 7(push7, push5), then push3, 1, 2, 0. Popping stack gives DFS Topological Order:0, 2, 1, 3, 5, 7, 4, 6.
Answer:
- Strongly connected: directed paths exist both ways between every pair; weakly connected: underlying undirected graph is connected.
- BFS Topological Sort:
0, 2, 1, 3, 5, 4, 7, 6 - DFS Topological Sort:
0, 2, 1, 3, 5, 7, 4, 6