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.

Algorithm

Example of prim’s algorithm

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

 Spanning Tree

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

 Spanning Tree

  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}         

 Spanning Tree

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}     

 Spanning Tree

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}       

 Spanning Tree

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}  

 Spanning Tree

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}  

 Spanning Tree

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}  

 Spanning Tree

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

Prim’s algorithm program in C language

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:

Edgeab  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

Pin It on Pinterest

Share This