# Spanning Tree

**Spanning Tree**: The spanning tree is a subset of the graph. It is a non-cyclic graph. If any node in the spanning tree is truncated, the entire graph fails.

There are several ways to create a spanning tree from a graph. Three types of spanning trees have been created from a graph, which has all the vertices and some edges in the graph. Ensure that no spreading trees form a circle.

### Properties of the spanning tree

- The connected graph may contain more than one spanning tree.
- There is no cycle in the spanning tree.
- If any node in the spanning tree is truncated, the entire graph fails.
- If you add an edge to the spanning tree, it creates a loop or circuit.

**Cost of a spanning tree**

The cost of a spanning tree can be calculated by adding the weights of its vertices.

**Minimum spanning tree**

The minimum spanning tree is that spanning-tree, which costs the lowest.There are two types of algorithms for finding the minimum spanning tree.

- Prim's algorithm
- Kruskal's algorithm

### Prim’s algorithm

Prim’s algorithm is based on the greedy algorithm. It is used to find a minimum spanning tree in the graph. This algorithm treats a single tree as a node, and adds a new node to it to create a spanning tree from the given graph.

#### Algorithm

Step 1. Select a starting vertex. Step 2. Repeat Steps 3 and 4 until there are fringe vertices. Step 3. Select an edge e connecting the tree vertex and fringe vertex that has minimum weight. Step 4. Add the selected edge and the vertex to the minimum spanning tree T. Step 5. Exit.

#### Example of prim’s algorithm

Construct the MST for the given graph in the following figure using Prime's algorithm.

Step 1: Choose a vertex S = {a} V/S = {b, c, d, e, f, g}

Step 2: Choose the shortest edge from this vertex, and add it. S = {a} V/S = {b, c, d, e, f, g} Lowest edge = {ab}

Step 3: Choose the shortest edge from the b vertex and add it. S = {a, b} V/S = {c, d, e, f, g} Lowest edge = {bd}

Step 4: Choose the shortest edge from the d vertex and add it. S = {a, b, d} V/S = {c, e, f, g} Lowest edge = {dc}

Step 5: Choose the shortest edge from the c vertex and add it. S = {a, b, d, c} V/S = {e, f, g} Lowest edge = {cf}

Step 6: Choose the shortest edge from the f vertex and add it. S = {a, b, d, c, f} V/S = {e, g} Lowest edge = {fg}

Step 7: Choose the shortest edge from the g vertex and add it. S = {a, b, d, c, f, g} V/S = {e} Lowest edge = {ge}

MST is complete MST cost = 5 + 8 + 2 + 1 + 2 + 4 = 22

#### Prim’s algorithm program in C language

#include <stdio.h> #include <conio.h> #include <limits.h> #define vertices 5 int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; for (i = 0; i < vertices; i++) if (mst[i] == 0 && k[i] < minimum ) minimum = k[i], min = i; return min; } void prim(int g[vertices][vertices]) { int parent[vertices]; int k[vertices]; int mst[vertices]; int i, count,u,v; for (i = 0; i < vertices; i++) k[i] = INT_MAX, mst[i] = 0; k[0] = 0; parent[0] = -1; for (count = 0; count < vertices-1; count++) { u = minimum_key(k, mst); mst[u] = 1; for (v = 0; v < vertices; v++)if(g[u][v] && mst[v] == 0 && g[u][v] < k[v]) parent[v] = u, k[v] = g[u][v]; } for (i = 1; i < vertices; i++) printf("%d %d %d \n", parent[i], i, g[i][parent[i]]); } void main() { int g[vertices][vertices] = { {3, 2, 1, 9, 0}, {5, 1, 2, 10, 4}, {0, 4, 1, 0, 9}, {8, 10, 0, 2, 10}, {1, 6, 8, 11, 0} }; prim(g); }

**Output:**

0 1 5 0 2 0 0 3 8 1 4 6

### Kruskal’s algorithm

Kruskal’s algorithm is also based on the greedy algorithm. Kruskal’s algorithm is used to find a minimum spanning tree in a graph. It follows all properties of the minimum spanning tree. In this algorithm, a graph is treated as a forest and all nodes are treated as an individual tree.

To find the minimum spanning tree with the help of Kruskal algorithm, firstly we choose a lowest cost edge in the graph. After that, again, we choose the second lowest cost edge, and the process continues until all the vertices have been added.

**Algorithm**

MST_Kruskal’s(G, v) Step 1: for each vartex V in graph G do Step 2: create a set (actually tree) with element v Step 3: Initialize a pririty queue ‘Q’ containing all edges in descending order of their weight Step 4: Forest ? A //contain all edges of the MST Step 5: while Tree (T) has edges <= N-1 do // N is no of vertices Step 6: Select edge with minimum weight Step 7: if T(v) ? T(u) then add (u, v) to forest union T(v) and T(u) Step 8: return

### Example of Kruskal’s algorithm

Construct the MST for the given graph in the following figure using Kruskal’s algorithm.

**Solution:**

Edge | ab | df | ce | ac | bd | bc | ef | de |

Weight | 1 | 2 | 3 | 4 | 6 | 8 | 10 | 15 |

**Step 1:**

**Step 2:**

**Step 3:**

**Step 4:**

**Step 5:**

**MST is complete**

### Kruskal’s algorithm program in C language

#include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair<int, int> > p[MAX]; void init() { for(int i = 0;i < MAX;++i) id[i] = i; } int root(int x) { while(id[x] != x) { id[x] = id[id[x]]; x = id[x]; } return x; } void union1(int x, int y) { int p = root(x); int q = root(y); id[p] = id[q]; } long long kruskal(pair<long long, pair<int, int> > p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i < edges;++i) { x = p[i].second.first; y = p[i].second.second; cost = p[i].first; if(root(x) != root(y)) { minimumCost += cost; union1(x, y); } } return minimumCost; } int main() { int x, y; long long weight, cost, minimumCost; init(); cout <<"Enter Nodes and edges"; cin >> nodes >> edges; for(int i = 0;i < edges;++i) { cout<<"Enter the value of X, Y and edges"; cin >> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<"Minimum cost is "<< minimumCost << endl; return 0; }