Past exam question: 2076 Baisakh (Back), Q11
Open in the Padhaiko appQuestion
What are different representation methods of graph? Explain Kruskal's algorithm to find Minimum Spanning Tree with example.
Solution
Graph Representation Methods ( Vertices, Edges):
- Adjacency Matrix: A matrix where (or weight ) if edge , else (or ). Space: ; edge lookup.
- Incidence Matrix: A matrix where if vertex is incident to edge (for directed graphs, for tail, for head). Space: .
- Adjacency List: An array of linked lists where list
adj[u]stores all neighbors of (and edge weights). Space: ; optimal for sparse graphs.
Kruskal's Algorithm for MST:
Algorithm KRUSKAL_MST(G = (V, E)):
1. Sort all edges in E in non-decreasing order of weight.
2. Initialize disjoint sets (Union-Find) so each vertex is its own tree.
3. T = empty set of MST edges.
4. For each edge (u, v) in sorted order:
If FIND(u) != FIND(v):
Add (u, v) to T
UNION(u, v)
If |T| == |V| - 1: break
5. Return TExample on a 5-Vertex Graph (A, B, C, D, E): Edges: A-B(1), B-C(2), A-C(5), C-D(3), D-E(4), B-E(6). Sorted: A-B(1), B-C(2), C-D(3), D-E(4), A-C(5), B-E(6):
- Pick
A-B(1){A, B} - Pick
B-C(2){A, B, C} - Pick
C-D(3){A, B, C, D} - Pick
D-E(4){A, B, C, D, E}(4 edges = , stop!).
Total MST weight = .
Answer:
Graphs are represented via adjacency matrix, incidence matrix, or adjacency list. Kruskal's algorithm greedily adds lightest non-cycle edges (via Union-Find) until edges connect all vertices (yielding weight on the 5-vertex example).