Kruskal's Minimum Spanning Tree Algorithm in C++

This C++ program displays the minimum spanning tree formed by implementation of Kruskal’s algorithm.
Here is the source code of the C++ program to implement Kruskal’s algorithm.
This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```

 * C++ Program to Find MST(Minimum Spanning Tree) using Kruskal's Algorithm

```
 */
```
```
#include<iostream>
```
```
#include<conio.h>
```
```
using namespace std;
```
```
int flag = 0, v[7];
```
```
struct node_info
```
```
{
```
```
    int no;
```
```
}*q = NULL, *r = NULL;
```
```
struct node
```
```
{
```
```
    node_info *pt;
```
```
    node *next;
```
```
}*top = NULL, *p = NULL, *np = NULL;
```
```
void push(node_info *ptr)
```
```
{
```
```
    np = new node;
```
```
    np->pt = ptr;
```
```
    np->next = NULL;
```
```
    if (top == NULL)
```
```
    {
```
```
        top = np;
```
```
    }
```
```
    else
```
```
    {
```
```
        np->next = top;
```
```
        top = np;
```
```
    }
```
```
}
```
```
node_info *pop()
```
```
{
```
```
    if (top == NULL)
```
```
    {
```
```
        cout<<"underflow\n";
```
```
    }
```
```
    else
```
```
    {
```
```
        p = top;
```
```
        top = top->next;
```
```
        return(p->pt);
```
```
        delete(p);
```
```
    }
```
```
}
```

int back_edges(int *v,int am[][7],int i,int k)

```
{
```
```
    q = new node_info;
```
```
    q->no = i;
```
```
    push(q);
```
```
    v[i] = 1;
```
```
    for (int j = 0; j < 7; j++)
```
```
    {
```
```
        if (am[i][j] == 1 && v[j] == 0)
```
```
        {
```
```
            back_edges(v, am, j, i);
```
```
        }
```
```
        else if (am[i][j] == 0)
```
```
            continue;
```

        else if ((j == k) && (am[i][k] == 1 && v[j] == 1))

```
            continue;
```
```
        else
```
```
        {
```
```
            flag = -1;
```
```
        }
```
```
    }
```
```
    r = pop();
```
```
    return(flag);
```
```
}
```
```
void init()
```
```
{
```
```
    for (int i = 0; i < 7; i++)
```
```
        v[i] = 0;
```
```
    while (top != NULL)
```
```
    {
```
```
        pop();
```
```
    }
```
```
}   
```
```
void kruskals(int am[][7], int wm[][7])
```
```
{
```
```
    int ve = 1, min, temp, temp1;
```

    cout<<"/n/nEDGES CREATED AS FOLLOWS:-/n/n";

```
    while (ve <= 6)
```
```
    {
```
```
        min = 999, temp = 0, temp1 = 0;
```
```
        for (int i = 0; i < 7; i++)
```
```
        {
```
```
            for (int j = 0; j < 7; j++)
```
```
            {
```

                if ((wm[i][j] < min) && wm[i][j]!=0)

```
                {
```
```
                    min = wm[i][j];
```
```
                    temp = i;
```
```
                    temp1 = j;
```
```
                }
```
```
                else if (wm[i][j] == 0)
```
```
                    continue;
```
```
            }
```
```
        }
```

        wm[temp][temp1]=wm[temp1][temp] = 999;

        am[temp][temp1]=am[temp1][temp] = 1;

```
        init();
```

        if (back_edges(v, am, temp, 0) < 0)

```
        {
```

            am[temp][temp1]=am[temp1][temp] = 0;

```
            flag = 0;
```
```
            continue;
```
```
        }
```
```
        else
```
```
        {
```

            cout<<"edge created between "<<temp<<" th node and "<<temp1<<" th node"<<endl;

```
            ve++;
```
```
        }            
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int am[7][7], wm[7][7];
```
```
    for (int i = 0; i < 7; i++)
```
```
        v[i] = 0;
```
```
    for (int i = 0; i < 7; i++)
```
```
    {
```
```
        for(int j = 0; j < 7; j++)
```
```
        {
```
```
            am[i][j] = 0;
```
```
        }
```
```
    }
```
```
    for (int i = 0; i < 7; i++)
```
```
    {
```

        cout<<"enter the values for weight matrix row:"<<i + 1<<endl;

```
        for(int j = 0; j < 7; j++)
```
```
        {
```
```
            cin>>wm[i][j];
```
```
        }
```
```
    }
```
```
    kruskals(am,wm);
```
```
    getch();
```
```
}
```

 
Output
enter the values for weight matrix row:1
0
3
6
0
0
0
0
enter the values for weight matrix row:2
3
0
2
4
0
0
0
enter the values for weight matrix row:3
6
2
0
1
4
2
0
enter the values for weight matrix row:4
0
4
1
0
2
0
4
enter the values for weight matrix row:5
0
0
4
2
0
2
1
enter the values for weight matrix row:6
0
0
2
0
2
0
1
enter the values for weight matrix row:7
0
0
0
4
1
1
0
EDGES CREATED AS FOLLOWS:-edge created between 2 th node and 3 th node
edge created between 4 th node and 6 th node
edge created between 5 th node and 6 th node
edge created between 1 th node and 2 th node
edge created between 2 th node and 5 th node
edge created between 0 th node and 1 th node

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Traveling Salesman Problem using Nearest Neighbour Algorithm

» Next - Bubble Sort in C++

Related Posts:

Recommended Articles: