PadhaikoAll subjects

Past exam question: 2064 Jestha, Q9

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

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:

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.

Answer:

All past exam questions for Data Structure and Algorithms