DSA: Graph- Spanning Tree

    Spanning Tree concept in Computer science is related to the Graph Data Structures, so do not confuse it with trees. A Spanning Tree is a subgraph or subset of a Graph G which contain all the vertices of the Graph G with the minimum number of edges. A graph can have more than one spanning tree and all the spanning trees of a graph must have all the vertices of that graph. As we know that tree data structure does not form a closed-loop or cycle so does spanning tree, all the spanning trees of a graph should not form a closed loop or cyclic structure.

    Spanning Tree

    When we design a spanning tree of a graph, that tree must contain all the vertices of the graph. We can also define a spanning tree as follow, “ a spanning tree is a connected graph G with all the vertices of G, that have a minimum number of edges and does not form a cyclic structure

    Example:

     Graph
                             X
                           /   \
                          /     \
                         /       \
                        Y---------Z   
    
    Spanning Trees
    
               X
                \
                 \ 
                  \
         Y---------Z
    
    
              X
            /   \
           /     \ 
          /       \
         Y         Z
    
     
              X
            /  
           /      
          /      
         Y---------Z

    We have a formula which can calculate the maximum number of spanning trees a complete graph could have. Suppose we have a complete undirected graph with node n so the maximum number of spanning trees of this graph would have n n-2 where n is the total number of nodes or vertices present in the graph. In the above example, we have a complete undirected graph with vertices X, Y and Z, which mean it has 3 vertices so the total number of spanning trees that could be formed from it are 3 3-2 = 3.

    Properties of a Spanning Tree

    As we can form more than one spanning tree from a graph, so while constructing a spanning tree we need to take care of some properties.

    • We can form a spanning tree from a connected graph.
    • The spanning-tree which is formed from a graph should have all the vertices of the Graph.
    • Like a tree, a spanning tree does not form a cyclic structure.
    • If we remove an edge from a spanning tree, it would make the graph disconnected which is also known as minimally connected
    • If we add an edge in the spanning tree it would make the graph cyclic.
    • A spanning tree can have n-1 number of edges where n is the number of nodes or vertices present in the graph.
    • We can only form n n-2 number of spanning trees from a complete disconnected graph.

    Real-world Applications of Spanning Tree

    There are many applications of Spanning tree and all of those are used to reduce the cost of a cluttered network.

    • Many pathfinding algorithms such as Dijkstra’s Algorithms and A* search algorithm, build spanning tree to solve the problem
    • To minimize the cost of a power network, for wiring connections, piping, automatic speech recognition we use spanning tree.
    • For internet and many other telecommunication networks transmission link we use spanning tree.
    • To find the shortest path while searching for a specific result on the internet.

    Minimum Spanning Tree

    In the graph, we have weighted graphs, in which a number or weight associated with every edge, the weight signifies the expense or cost of edge from one vertex to another. A minimum spanning tree is a spanning tree of a graph with minimum total weight. For example:

     Weighted Graph               
                              X
                            /   \
                         10/     \20
                          /       \
                         Y---------Z
                             30
    
    Spanning Trees
    
          X                                          
           \                                        
            \20                                      
             \                                         
      Y-------Z                                          
         30
                 
    
             X
           /   \
        10/     \ 20
         /       \
        Y         Z
     minimum spanning tree
    
    
          X
        /  
     10/      
      /      
      Y---------Z
          30

    Algorithms of Minimum Spanning Tree

    There are two basic and most important spanning tree algorithms:

    • Kruskal’s Algorithm
    • Prim Algorithm

    People are also reading: