Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

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

  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

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.

 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

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

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

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



ADVERTISEMENT
ADVERTISEMENT