Skip to main content

Develop a program to model a graph using an adjacency list and employ Kruskal's algorithm to find the minimum spanning tree

 Code:


#include <iostream>

#include <vector>

#include <algorithm>


using namespace std;


// Structure to represent an edge in the graph

struct Edge {

    int src, dest, weight;

};


// Structure to represent a subset for union-find

struct Subset {

    int parent, rank;

};


// Class to represent a graph and perform Kruskal's algorithm

class Graph {

    int V; // Number of vertices

    vector<Edge> edges; // Vector to store graph edges


public:

    // Constructor

    Graph(int V) {

        this->V = V;

    }


    // Function to add an edge to the graph

    void addEdge(int src, int dest, int weight) {

        Edge edge = {src, dest, weight};

        edges.push_back(edge);

    }


    // Function to find the subset of an element 'i'

    int find(vector<Subset>& subsets, int i) {

        if (subsets[i].parent != i)

            subsets[i].parent = find(subsets, subsets[i].parent);

        return subsets[i].parent;

    }


    // Function to perform union of two subsets

    void Union(vector<Subset>& subsets, int x, int y) {

        int xroot = find(subsets, x);

        int yroot = find(subsets, y);


        if (subsets[xroot].rank < subsets[yroot].rank)

            subsets[xroot].parent = yroot;

        else if (subsets[xroot].rank > subsets[yroot].rank)

            subsets[yroot].parent = xroot;

        else {

            subsets[yroot].parent = xroot;

            subsets[xroot].rank++;

        }

    }


    // Function to find the minimum spanning tree using Kruskal's algorithm

    void KruskalMST() {

        vector<Edge> result; // Vector to store the result MST


        // Sort all the edges in non-decreasing order of their weight

        sort(edges.begin(), edges.end(), [](Edge a, Edge b) {

            return a.weight < b.weight;

        });


        // Allocate memory for creating V subsets

        vector<Subset> subsets(V);

        for (int v = 0; v < V; v++) {

            subsets[v].parent = v;

            subsets[v].rank = 0;

        }


        int i = 0; // Index used to pick the next edge


        // Number of edges to be taken is equal to V-1

        while (result.size() < V - 1) {

            Edge next_edge = edges[i++];


            int x = find(subsets, next_edge.src);

            int y = find(subsets, next_edge.dest);


            // If including this edge doesn't cause cycle, include it in the result and increment the index for next edge

            if (x != y) {

                result.push_back(next_edge);

                Union(subsets, x, y);

            }

        }


        // Print the result MST

        cout << "Edges of the Minimum Spanning Tree:" << endl;

        for (auto edge : result)

            cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;

    }

};


// Driver code

int main() {

    int V = 4; // Number of vertices in the graph

    Graph g(V);


    // Add edges to the graph

    g.addEdge(0, 1, 10);

    g.addEdge(0, 2, 6);

    g.addEdge(0, 3, 5);

    g.addEdge(1, 3, 15);

    g.addEdge(2, 3, 4);


    // Find minimum spanning tree using Kruskal's algorithm

    g.KruskalMST();


    return 0;

}


  1. Edge Struct: Represents an edge in the graph with source, destination, and weight.
  2. Subset Struct: Represents a subset for the union-find operation, used to check for cycles.
  3. Graph Class: Represents a graph and contains methods for adding edges and finding the minimum spanning tree using Kruskal's algorithm.
  4. addEdge(): Adds an edge to the graph.
  5. find() and Union(): Helper functions for the union-find algorithm to detect cycles.
  6. KruskalMST(): Implements Kruskal's algorithm to find the minimum spanning tree. It sorts the edges by weight, then iterates through them, adding them to the MST if they don't form a cycle.
  7. main(): Creates a graph and adds edges to it, then calls KruskalMST() to find the minimum spanning tree and prints the result.


  1. Define structures: Define structures to represent edges (struct Edge) and subsets for the union-find operation (struct Subset).

  2. Graph Class: Define a Graph class with private member variables V (number of vertices) and a vector edges to store the graph's edges.

  3. addEdge(): Define a method addEdge(int src, int dest, int weight) to add an edge to the graph. Create an Edge structure with source, destination, and weight, and add it to the edges vector.

  4. Union-Find Operations: Define helper functions find() and Union() to perform the union-find operations. These are used to check for cycles in the graph.

  5. Kruskal's Algorithm: Define a method KruskalMST() to find the minimum spanning tree using Kruskal's algorithm.

    • Sort the edges in non-decreasing order of their weight.
    • Create subsets for each vertex.
    • Iterate through sorted edges.
    • For each edge, check if including it forms a cycle. If not, add it to the result and union the subsets of its source and destination vertices.
    • Continue until the number of edges in the result equals V - 1 (where V is the number of vertices).

  6. Main Function:

    • Create a graph object and add edges to it.
    • Call KruskalMST() to find the minimum spanning tree.
    • Print the edges of the minimum spanning tree.

Popular posts from this blog

krushnaaa

  import java . awt .* ; import java . awt . event .* ; public class SimpleAWTExample {     public static void main ( String [] args ) {         // Create a Frame         Frame frame = new Frame ( "Simple AWT Example" );         // Create a Button         Button button = new Button ( "Click Me!" );         // Set layout for the Frame         frame . setLayout ( new FlowLayout ());         // Add the Button to the Frame         frame . add ( button );         // Set size of the Frame         frame . setSize ( 300 , 200 ); // Width: 300 pixels, Height: 200 pixels         // Make the Frame visible         frame . setVisible ( true );         // Add a WindowListener to handle closing event     ...
Read more

Write a program to create a class Student2 along with two method getData (), printData () to get the value through argument and display the data in printData. Create the two objects s1, s2 to declare and access the values from class STtest.

 CODE: import java.util.Scanner; class Student2 {     private String name;     private int age;          // Method to set data     public void getData(String name, int age) {         this.name = name;         this.age = age;     }          // Method to print data     public void printData() {         System.out.println("Name: " + name);         System.out.println("Age: " + age);     } } public class STtest {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);                  // Creating objects of Student2 class         Student2 s1 = new Student2();         Student2 s2 = new Student2();              ...
Read more

Create an in-order threaded binary search tree and perform the traversals.(Double Thread)

 CODE: #include <iostream> using namespace std; struct Node {     int data;     Node* left;     Node* right;     bool leftThread;     bool rightThread; }; Node* createThreadedBST(int arr[], int n) {     Node* root = nullptr;     for (int i = 0; i < n; ++i) {         Node* newNode = new Node;         newNode->data = arr[i];         newNode->left = newNode->right = nullptr;         newNode->leftThread = newNode->rightThread = true;         if (root == nullptr) {             root = newNode;         } else {             Node* current = root;             Node* parent = nullptr;             while (true) {                ...
Read more