Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Minimum Spanning Tree

    Uploaded by

    सतीश पाण्डेय (पाण्डेय जी)
    The document describes C++ code to find the minimum spanning tree of a graph using Kruskal's and Prim's algorithms. It includes code for implementing Kruskal's algorithm using disjoint sets and union by rank. It also includes code for implementing Prim's algorithm using an adjacency matrix representation of the graph and tracking the vertices included in the minimum spanning tree.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Minimum Spanning Tree

    Uploaded by

    सतीश पाण्डेय (पाण्डेय जी)
    28 views10 pages
    The document describes C++ code to find the minimum spanning tree of a graph using Kruskal's and Prim's algorithms. It includes code for implementing Kruskal's algorithm using disjoint sets and union by rank. It also includes code for implementing Prim's algorithm using an adjacency matrix representation of the graph and tracking the vertices included in the minimum spanning tree.

    Original Description:

    C++

    Original Title

    minimum spanning tree

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes C++ code to find the minimum spanning tree of a graph using Kruskal's and Prim's algorithms. It includes code for implementing Kruskal's algorithm using disjoint sets and union by rank. It also includes code for implementing Prim's algorithm using an adjacency matrix representation of the graph and tracking the vertices included in the minimum spanning tree.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    28 views10 pages

    Minimum Spanning Tree

    Uploaded by

    सतीश पाण्डेय (पाण्डेय जी)
    The document describes C++ code to find the minimum spanning tree of a graph using Kruskal's and Prim's algorithms. It includes code for implementing Kruskal's algorithm using disjoint sets and union by rank. It also includes code for implementing Prim's algorithm using an adjacency matrix representation of the graph and tracking the vertices included in the minimum spanning tree.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 10

    WAP in C++ to find the minimum spanning tree using

    Kruskal’s Algorithm and Prim’s Algorithm.

    • Kruskal’s Algorithm:
    Input:
    #include <stdio.h>

    #include <stdlib.h>

    #include <string.h>

    #include <iostream>

    using namespace std;

    struct Edge

    int src, dest, weight;

    };

    struct Graph

    int V, E;

    struct Edge* edge;

    };

    struct Graph* createGraph(int V, int E)

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

    return graph;

    struct subset

    int parent;

    int rank;

    };

    int find(struct subset subsets[], int i)

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

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

    return subsets[i].parent;

    void Union(struct 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++;

    int myComp(const void* a, const void* b)

    struct Edge* a1 = (struct Edge*) a;

    struct Edge* b1 = (struct Edge*) b;

    return a1->weight > b1->weight;

    void KruskalMST(struct Graph* graph)

    int V = graph->V;

    struct Edge result[V];

    int e = 0;

    int i = 0;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);

    struct subset *subsets = (struct subset*) malloc(V * sizeof(struct subset));

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

    subsets[v].parent = v;
    subsets[v].rank = 0;

    while (e < V - 1)

    struct Edge next_edge = graph->edge[i++];

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

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

    if (x != y)

    result[e++] = next_edge;

    Union(subsets, x, y);

    cout<<"Following are the edges in the constructed MST\n";

    for (i = 0; i < e; ++i)

    printf("%d -- %d == %d\n", result[i].src, result[i].dest,

    result[i].weight);

    return;

    int main()

    int V = 4;

    int E = 5;
    struct Graph* graph = createGraph(V, E);

    graph->edge[0].src = 0;

    graph->edge[0].dest = 1;

    graph->edge[0].weight = 10;

    graph->edge[1].src = 0;

    graph->edge[1].dest = 2;

    graph->edge[1].weight = 6;

    graph->edge[2].src = 0;

    graph->edge[2].dest = 3;

    graph->edge[2].weight = 5;

    graph->edge[3].src = 1;

    graph->edge[3].dest = 3;

    graph->edge[3].weight = 15;

    graph->edge[4].src = 2;

    graph->edge[4].dest = 3;

    graph->edge[4].weight = 4;

    KruskalMST(graph);

    return 0;

    }
    output:
    • Prim’s Algorithm:

    Input:

    #include <iostream>

    #include <cstring>

    using namespace std;

    #define INF 9999

    #define V 5

    int G[V][V] = {

    {0, 3, 0, 3, 0},

    {3, 0, 0, 0, 4},

    {0, 0, 0, 2, 1},

    {3, 3, 2, 0, 0},

    {0, 4, 1, 0, 0}};

    int main () {

    int num_edge;
    int mst_vertex[V];

    memset (mst_vertex, false, sizeof (mst_vertex));

    num_edge = 0;

    mst_vertex[0] = true;

    int x;

    int y;

    cout<<"The Minimum Spanning Tree as per Prim's Algorithm:"<<endl;

    cout << "Edge" << " : " << "Weight";

    cout << endl;

    while (num_edge < V - 1) {

    int min = INF;

    x = 0;

    y = 0;

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

    if (mst_vertex[i]) {

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

    if (!mst_vertex[j] && G[i][j]) {


    if (min > G[i][j]) {

    min = G[i][j];

    x = i;

    y = j;

    cout << x << " - " << y << " : " << G[x][y];

    cout << endl;

    mst_vertex[y] = true;

    num_edge++;

    return 0;

    }
    output:

    You might also like