Select Page

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

1. The connected graph may contain more than one spanning tree.
2. There is no cycle in the spanning tree.
3. If any node in the spanning tree is truncated, the entire graph fails.
4. 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.

1. Prim’s algorithm
2. 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.

#### 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

Output:

### 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

### Example of Kruskal’s algorithm

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

Solution:

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

MST is complete