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.
Stepbystep 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


C++


Python


In all these implementations, UnionFind
is a helper class for managing disjointset data structures. This class should have find()
and union()
methods for unionfind 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.