PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q11

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

What are different representation methods of graph? Explain Kruskal's algorithm to find Minimum Spanning Tree with example.

Solution

Graph Representation Methods ( Vertices, Edges):

  1. Adjacency Matrix: A matrix where (or weight ) if edge , else (or ). Space: ; edge lookup.
  2. Incidence Matrix: A matrix where if vertex is incident to edge (for directed graphs, for tail, for head). Space: .
  3. 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 T

Example 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):

  1. Pick A-B(1) {A, B}
  2. Pick B-C(2) {A, B, C}
  3. Pick C-D(3) {A, B, C, D}
  4. 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).

All past exam questions for Data Structure and Algorithms