What can you tell me about implementing Kruskal Algorithm to find a minimum spanning tree for a different graphs in C++? How does this algorithm work?

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
What can you tell me about implementing Kruskal Algorithm to find a minimum spanning tree for a different graphs in C++? How does this algorithm work?
Expert Solution
Step 1

Below are the steps which show how the algorithm works:

  1. Arrange all the edges in non-decreasing order of their weight.
  2. Pick the smallest edge. Examine if it makes a cycle with the spanning-tree formed so far. If the cycle is not formed, add this edge. Else, reject it.
  3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Step 2

Implementing Kruskal Algorithm to find a minimum spanning tree for a different graph in C++:

 

//Header file
#include<bits/stdc++.h> 
using namespace std; 
  
//Create shortcut for the integer pair 
typedef  pair<int, int> iPair; 
  
//Structure to describe a graph 
struct Graph 

    int V, E; 
    vector< pair<int, iPair> > edges; 
  
    Graph(int V, int E) 
    { 
        this->V = V; 
        this->E = E; 
    } 
  
    //Function to append an edge 
    void addEdge(int u, int v, int w) 
    { 
        edges.push_back({w, {u, v}}); 
    } 
  
    // Call the function to find MST using Kruskal's MST algorithm 
    int kruskalMST(); 
}; 
  
//Structure to represent the Disjoint Sets 
struct DisjointSets 

    int *parent, *rnk; 
    int n; 
  
    //Constructor
    DisjointSets(int n) 
    { 
        //Allocate memory 
        this->n = n; 
        parent = new int[n+1]; 
        rnk = new int[n+1]; 
  
        //Initially, every vertex are in distinct sets and have rank 0. 
        for (int i = 0; i <= n; i++) 
        { 
            rnk[i] = 0; 
  
            //every element is parent of itself 
            parent[i] = i; 
        } 
    } 
  
    //Find the parent of a node 'u' Path Compression 
    int find(int u) 
    { 
        //Make the parent of the nodes in the path from u--> parent[u] point to parent[u] 
        if (u != parent[u]) 
            parent[u] = find(parent[u]); 
        return parent[u]; 
    } 
  
    //Union by rank 
    void merge(int x, int y) 
    { 
        x = find(x), y = find(y); 
  
        // Make tree with smaller height a subtree of the other tree 
        if (rnk[x] > rnk[y]) 
            parent[y] = x; 
        else 
            parent[x] = y; 
  
        if (rnk[x] == rnk[y]) 
            rnk[y]++; 
    } 
}; 
  
 // Functions returns weight of the MST 
int Graph::kruskalMST() 

    int mst_wt = 0;
  
    //Sort the edges in increasing order on basis of cost 
    sort(edges.begin(), edges.end()); 
  
    //Create disjoint sets 
    DisjointSets ds(V); 
  
    //Iterate through all the sorted edges 
    vector< pair<int, iPair> >::iterator it; 
    for (it=edges.begin(); it!=edges.end(); it++) 
    { 
        int u = it->second.first; 
        int v = it->second.second; 
  
        int set_u = ds.find(u); 
        int set_v = ds.find(v); 
  
        //Examine if the selected edge is creating a cycle or not
        if (set_u != set_v) 
        { 
            //Current edge will be in the MST so print it 
            cout << u << " - " << v << endl; 
  
            //Update MST weight 
            mst_wt += it->first; 
  
            //Merge the two sets 
            ds.merge(set_u, set_v); 
        } 
    } 
  
    return mst_wt; 

  
//Main
int main() 

    //Create weighted and unidrected graph 
    int V = 9, E = 14; 
    Graph g(V, E); 
  
    g.addEdge(0, 1, 4); 
    g.addEdge(0, 7, 8); 
    g.addEdge(1, 2, 8); 
    g.addEdge(1, 7, 11); 
    g.addEdge(2, 3, 7); 
    g.addEdge(2, 8, 2); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 4, 9); 
    g.addEdge(3, 5, 14); 
    g.addEdge(4, 5, 10); 
    g.addEdge(5, 6, 2); 
    g.addEdge(6, 7, 1); 
    g.addEdge(6, 8, 6); 
    g.addEdge(7, 8, 7); 
  
    cout << "Edges of MST: \n"; 
    int mst_wt = g.kruskalMST(); 
    cout<<endl;
    cout << "Weight of MST: " << mst_wt; 
  
    return 0; 

 

steps

Step by step

Solved in 3 steps with 1 images

Blurred answer
Knowledge Booster
Types of trees
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education