Computing a Minimum Spanning Tree in Undirected Graph

A Minimum Spanning Tree (MST) in an undirected graph is a tree that spans all the vertices and has the minimum possible total edge weight among all the trees that can be created. Two popular algorithms for computing MST are Kruskal’s algorithm and Prim’s algorithm.

I can guide you on how to illustrate the concept of computing a minimum spanning tree in an undirected graph. For this visualization, a whiteboard or paper and pen will be useful.

Initial Graph: Draw a set of circles (vertices) connected by lines (edges). Label the edges with weights, which can be numerical values.
Highlighting Algorithm Steps: Use different colored markers or notations to indicate the edges that you are considering and those you have confirmed as part of the minimum spanning tree. For example, use a dashed line for considered edges and a solid line for confirmed ones.
Step-by-step Action:
- Start at any vertex.
- Choose the edge with the smallest weight that connects a vertex inside your current tree to a vertex outside of it.
- Highlight this edge as a solid line, indicating it’s part of the minimum spanning tree.
- Add the new vertex to your tree.
- Repeat until you have a tree that includes all vertices.
Final Minimum Spanning Tree: Once all vertices are included, you should have a tree where all lines are solid, representing the edges in your minimum spanning tree. The sum of the weights of these edges should be the minimum possible to connect all vertices.

This visual approach lets you understand the progressive nature of algorithms like Kruskal’s or Prim’s in building a minimum spanning tree. It also provides a clear visual cue for the concept of ‘minimum weight’ across a spanning tree.

Kruskal’s Algorithm

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Arrays;
import java.util.Comparator;

class Edge {
    int src, dest, weight;
    // Constructor
}

class UnionFind {
    int[] parent, rank;
    // Union-Find operations: find() and union()
}

public class Kruskal {
    public static void main(String[] args) {
        // Initialize edges and sort them by weight
        Edge[] edges = //...
        Arrays.sort(edges, Comparator.comparingInt(e -> e.weight));

        UnionFind uf = new UnionFind();
        // Initialize MST result

        for (Edge edge : edges) {
            int set1 = uf.find(edge.src);
            int set2 = uf.find(edge.dest);
            
            if (set1 != set2) {
                // Add edge to MST result
                uf.union(set1, set2);
            }
        }
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include <vector>

struct Edge {
    int src, dest, weight;
    // Constructor
};

class UnionFind {
    std::vector<int> parent, rank;
    // Union-Find operations: find() and union()
};

int main() {
    // Initialize edges and sort
    std::vector<Edge> edges; //...
    std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    UnionFind uf;
    // Initialize MST result

    for (const auto& edge : edges) {
        int set1 = uf.find(edge.src);
        int set2 = uf.find(edge.dest);
        
        if (set1 != set2) {
            // Add edge to MST result
            uf.unionSets(set1, set2);
        }
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    # Union-Find operations: find() and union()

edges = [
    # Initialize edges
]

# Sort edges by weight
edges.sort(key=lambda x: x['weight'])

uf = UnionFind()
# Initialize MST result

for edge in edges:
    set1 = uf.find(edge['src'])
    set2 = uf.find(edge['dest'])

    if set1 != set2:
        # Add edge to MST result
        uf.union(set1, set2)

In all these implementations, UnionFind is a helper class for managing disjoint-set data structures. This class should have find() and union() methods for union-find operations. The edges are sorted by weight before the main loop. In the loop, the algorithm iterates through the sorted edges and includes them in the MST if they connect two different sets, which is verified by the UnionFind object.