Spanning Tree | Data Structure

 

Spanning tree of a graph G is a tree hold following properties:

1. Number of vertex in graph G = Number of vertex in spanning tree.

2. If n = Number of vertex in graph G than spanning tree has (n-1) edges.

3. Spanning tree does not have any cycle.

Example: 

Suppose G is any graph having four vertices {1,2,3,4}.

Now from from above graph we can construct following spanning tree such as:

In the above spanning tree the minimum cost of spanning tree is 3.which is marked as yellow box. That minimum cost spanning tree is called minimum cost spanning tree.

Minimum Cost Spanning Tree:

Spanning tree having minimum cost is known as minimum cost spanning tree.

Minimum Spanning Tree Algorithms:

The most popular minimum spanning tree algorithms are.

1. Kruskal's Algorithm :

Let we discuss Kruskal's algorithm by the help of an example:

STEP 1: Prepare edge list of given graph.

    Edge            Cost

    AB                 1

    AC                 1

    CF                 3

    FG                 2

    GE                 1

    EB                 2

    BD                 5

    DC                1                                       

STEP 2: Sort the given list in increasing order.

    Edge            Cost

    AB                 1

    AC                 1

    DC                 1 

    GE                 1

    FG                 2

    EB                 2

    CF                 3

    BD                 5

   

STEP 3: Now add (n-1) edge to the graph such that no cycle will form.

Remove those edges which make cycle.But removing edge in such a manner which have maximum cost such as edge (CD) & (DB) make cycle where the cost is 5,1 respectively. So here 5 is maximum cost so remove it because we want to create minimum cost spanning tree.

same as edge CF make a cycle and having cost 3 which is maximum so remove it Now we get final spanning tree.

↓

Final cost of spanning tree is 8

2. Prim's Algorithm :

Let we discuss Prim's algorithm by the help of an example:

STEP 1: Prepare edge list of given graph.

      Edge            Cost

        AB                 1

        AC                 1

        CF                 3

        FG                 2

        GE                 1

        BE                 2

        BD                 5

        DC                1      

STEP 2: Now add (n-1) edges , starting with the edge having minimum cost.

    STEP 2.1 : Choose AB with cost 1

    Now create a new edge table from edge list having A or B as an adjacent vertex.

      Edge             Cost

        AC                 1

        BD                 1

        BF                 3

    STEP 2.2: Now choose edge with minimum cost and does not form any cycle.

    Now create a new edge table from edge list having A,B & C as an adjacent vertex.

       Edge             Cost

        BD                 5

        BE                 2

        CF                 3

 

        CD                 1

    STEP 2.3: Repeat same as in step 2.2 , choose CD

   Now create a new edge table from edge list having A,B,C & D as an adjacent vertex.

       Edge             Cost

        BD                 5

        BE                 2

        CF                 3

 

        

 STEP 2.4: Now choose edge with minimum cost and does not form any cycle.

    Now create a new edge table from edge list having A,B,C,D & E as an adjacent vertex.

       Edge             Cost

        BD                 5

        EG                 1

        CF                 3

   STEP 2.5: Repeat same as in step 2.2 , choose EG

    Now create a new edge table from edge list having A,B,C,D,E & F as an adjacent vertex.

       Edge             Cost

        GF                 2

        CF                 3

    STEP 2.6: Repeat same as in step 2.5 , choose GF

Now we get the final spanning tree whose cost is 8 which is minimum.