A spanning tree is a subset of graph G, which has all the vertices covered with the minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be a disconnected graph.
For example, we will consider the following graph –
The various spanning trees from the above graph are –
Following are a few properties of a spanning tree connected to the graph G =
- A spanning tree does not have any cycle
- A connected graph G can have more than one spanning tree.
- All possible spanning trees of graph G, have the same number of edges and vertices.
- A spanning tree is minimally connected. Therefore, removing one edge from the spanning tree will make the graph disconnected.
- A spanning tree is maximally acyclic. Therefore, adding one edge to the spanning tree will create a circuit or a loop.
Minimum Spanning Tree
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph in which all the vertices are connected together without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of the weights on its edges is as small as possible.
The first spanning tree is a minimum spanning tree as it has the minimum total weight on its edges.
There are many methods to create a spanning tree from a Graph. The two widely used algorithms for this are –
- Prim’s Algorithm
- Kruskal Algorithm
Prim’s Algorithm
The process can be started from any of the vertices of a graph. Start from vertex v1. Label it with permanent status and the remaining vertices as temporary nodes. Set its distance from the starting as 0 as node v1 itself is the starting node. Set the distance of the remaining nodes an infinity.
Now, find the adjacent node to v1 with minimum weight on its edge among all the adjacent nodes. Add the edge and the node in the spanning tree. For example. If the nodes v2 and v3 are the adjacent nodes to v1 and the node v2 has the minimum weight on the edge connecting v1 and v2, then node v2 and its edge connected to v1 will be added in the spanning tree.
Again, find the node having the least weight on its edge connecting v2, add it and its edge to the spanning tree. One thing is to be considered that no cycle(loop) should be former while adding the edge in the spanning tree. Repeat the process until all the nodes become permanent.
Prim’s algorithm code in C
Given below, is the coding implementation for Prim’s algorithm –
#include<stdio.h>
#include<stdbool.h>
#define INF 9999999
#define V 5
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}};
int main() {
int no_edge;
int selected[V];
memset(selected, false, sizeof(selected));
no_edge = 0;
selected[0] = true;
int x;
int y;
printf("Edge : Weight\n");
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) {
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
printf("%d - %d : %d\n", x, y, G[x][y]);
selected[y] = true;
no_edge++;
}
return 0;
}
Kruskal Algorithm
Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. The algorithm finds a subset of the edges that forms a tree that includes all the vertices with the condition that the total weight for all the edges is the least in a minimum spanning tree.
Kruskal Algorithm code in C
Given below, is the coding implementation for Kruskal Algorithm –
#include <stdio.h>
#define MAX 30
typedef struct edge {
int u, v, w;
} edge;
typedef struct edge_list {
edge data[MAX];
int n;
} edge_list;
edge_list elist;
int Graph[MAX][MAX], n;
edge_list spanlist;
void kruskalAlgo();
int find(int belongs[], int vertexno);
void applyUnion(int belongs[], int c1, int c2);
void sort();
void print();
void kruskalAlgo() {
int belongs[MAX], i, j, cno1, cno2;
elist.n = 0;
for (i = 1; i < n; i++)
for (j = 0; j < i; j++) {
if (Graph[i][j] != 0) {
elist.data[elist.n].u = i;
elist.data[elist.n].v = j;
elist.data[elist.n].w = Graph[i][j];
elist.n++;
}
}
sort();
for (i = 0; i < n; i++)
belongs[i] = i;
spanlist.n = 0;
for (i = 0; i < elist.n; i++) {
cno1 = find(belongs, elist.data[i].u);
cno2 = find(belongs, elist.data[i].v);
if (cno1 != cno2) {
spanlist.data[spanlist.n] = elist.data[i];
spanlist.n = spanlist.n + 1;
applyUnion(belongs, cno1, cno2);
}
}
}
int find(int belongs[], int vertexno) {
return (belongs[vertexno]);
}
void applyUnion(int belongs[], int c1, int c2) {
int i;
for (i = 0; i < n; i++)
if (belongs[i] == c2)
belongs[i] = c1;
}
void sort() {
int i, j;
edge temp;
for (i = 1; i < elist.n; i++)
for (j = 0; j < elist.n - 1; j++)
if (elist.data[j].w > elist.data[j + 1].w) {
temp = elist.data[j];
elist.data[j] = elist.data[j + 1];
elist.data[j + 1] = temp;
}
}
void print() {
int i, cost = 0;
for (i = 0; i < spanlist.n; i++) {
printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w);
cost = cost + spanlist.data[i].w;
}
printf("\nSpanning tree cost: %d", cost);
}
int main() {
int i, j, total_cost;
n = 6;
Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 4;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 0;
Graph[0][6] = 0;
Graph[1][0] = 4;
Graph[1][1] = 0;
Graph[1][2] = 2;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 0;
Graph[1][6] = 0;
Graph[2][0] = 4;
Graph[2][1] = 2;
Graph[2][2] = 0;
Graph[2][3] = 3;
Graph[2][4] = 4;
Graph[2][5] = 0;
Graph[2][6] = 0;
Graph[3][0] = 0;
Graph[3][1] = 0;
Graph[3][2] = 3;
Graph[3][3] = 0;
Graph[3][4] = 3;
Graph[3][5] = 0;
Graph[3][6] = 0;
Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 4;
Graph[4][3] = 3;
Graph[4][4] = 0;
Graph[4][5] = 0;
Graph[4][6] = 0;
Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][2] = 2;
Graph[5][3] = 0;
Graph[5][4] = 3;
Graph[5][5] = 0;
Graph[5][6] = 0;
kruskalAlgo();
print();
}
So, in this article, we learned about the Minimum Spanning tree, Prim’s, and Kruskal’s algorithm.
Attempt Free Data Structures MCQ Test
