What is Minimum Spanning Tree in C?
Minimum Spanning Tree in C can be represented in different ways, depending on the algorithm used. Here we use Kruskal’s Algorithm to Implement Minimum Spanning Tree.
- Begins with all edges sorted by weight and iterates through them, adding an edge to the Minimum Spanning Tree if it does not create a cycle.
- And Requires an edge list and a Disjoint Set Union structure to track connected components in the graph.
Minimum Spanning Tree has V-1 edges where V is the number of vertices in Graph.
Example
Here we take one example to explain how Implement Minimum Spanning Tree by using the Kruskal’s algorithm by calculating minimum total weights without a cycle.
Explanation
The graph has 4 vertices (0, 1, 2, 3) and 5 edges with the following weights
- Edge from vertex 0 to 1 with a weight of 10.
- Edge from vertex 0 to 2 with a weight of 6.
- Edge from vertex 0 to 3 with a weight of 5.
- Edge from vertex 1 to 3 with a weight of 15.
- Edge from vertex 2 to 3 with a weight of 4.
Minimum Spanning Tree of the Above Graph
Kruskal’s algorithm sorts the edges by weight, then iterates through the edges to include them in the MST if they don’t create a cycle.
- Edge from vertex 2 to 3 with a weight of 4
- Edge from vertex 0 to 3 with a weight of 5
- Edge from vertex 0 to 1 with a weight of 10
These edges connect all four vertices without creating cycles, forming the Minimum Spanning Tree with the minimum total weight 19.
C Program to Implement Minimum Spanning Tree
A Minimum Spanning Tree is a subset of edges from a undirected graph that connects all vertices with minimum total weight and contains no cycle. The most common algorithms to generate Minimum Spanning Tree are Kruskal’s algorithm and Prim’s algorithm. In this article we explain about implement Minimum Spanning Tree with Kruskal’s algorithm. You can also use Prim’s algorithm based on your requirement.