Kruskal's Algorithm

[John Linux]

/************************************************************

-> This Program is to implement Kruskal algorithm.

-> This program is to find minimum spanning tree
for undirected weighted graphs

-> Data Structers used:
Graph:Adjacency Matrix

-> This program works in microsoft vc++ 6.0 environment.

**************************************************************/

#include <iostream>
#include <fstream>

using namespace std;

class kruskal
{
    private:
    int n; //no of nodes
    int noe; //no edges in the graph
    int graph_edge[100][4];

    int tree[10][10];

    int sets[100][10];
    int top[100];
    public:
    int read_graph();
    void initialize_span_t();
    void sort_edges();
    void algorithm();
    int find_node(int );
    void print_min_span_t();
};

int kruskal::read_graph()
{
cout<<"This program implements the kruskal algorithm\n";
cout<<"Enter the no. of nodes in the undirected weighted graph";
cin>>n;
noe=0;

cout<<"Enter the weights for the following edges ::\n";

for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
        cout<<i<<" , "<<j;
        int w;
        cin>>w;
            if(w!=0)
            {
            noe++;

            graph_edge[noe][1]=i;
            graph_edge[noe][2]=j;
            graph_edge[noe][3]=w;
            }
        }
    }

// print the graph edges

cout<<"\n\nThe edges in the given graph are::\n";
for(int i=1;i<=noe;i++)
{
    cout<<" < "<<graph_edge[i][1]
    <<" , "<<graph_edge[i][2]
    <<" > "<<graph_edge[i][3]<<endl;

}
}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
    for(int j=1;j<=noe-i;j++)
    {
        if(graph_edge[j][3]>graph_edge[j+1][3])
        {
        int t=graph_edge[j][1];
        graph_edge[j][1]=graph_edge[j+1][1];
        graph_edge[j+1][1]=t;

        t=graph_edge[j][2];
        graph_edge[j][2]=graph_edge[j+1][2];
        graph_edge[j+1][2]=t;

        t=graph_edge[j][3];
        graph_edge[j][3]=graph_edge[j+1][3];
        graph_edge[j+1][3]=t;
        }
    }
}

// print the graph edges

cout<<"\n\nAfter sorting the edges in the given graph are::\n";
for(int i=1;i<=noe;i++)
cout<<""<< graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}

void kruskal::algorithm()
{
    // ->make a set for each node
    for(int i=1;i<=n;i++)
    {
    sets[i][1]=i;
    top[i]=1;
    }

cout<<"\nThe algorithm starts ::\n\n";

    for(int i=1;i<=noe;i++)
    {
    int p1=find_node(graph_edge[i][1]);
    int p2=find_node(graph_edge[i][2]);

        if(p1!=p2)
        {
            cout<<"The edge included in the tree is ::"
            <<" < "<<graph_edge[i][1]<<" , "
            <<graph_edge[i][2]<<" > "<<endl<<endl;

            tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
            tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

            // Mix the two sets

            for(int j=1;j<=top[p2];j++)
            {
                top[p1]++;
                sets[p1][top[p1]]=sets[p2][j];
            }

            top[p2]=0;
        }
        else
        {
            cout<<"Inclusion of the edge "
            <<" < "<<graph_edge[i][1]<<" , "
            <<graph_edge[i][2]<<" > "<<"forms a cycle so it is removed\n\n";
        }
    }
}

int kruskal::find_node(int n)
{
    for(int i=1;i<=noe;i++)
    {
        for(int j=1;j<=top[i];j++)
        {
        if(n==sets[i][j])
            return i;
        }
    }

    return -1;
}

void kruskal::print_min_span_t()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<tree[i][j]<<"\t";
cout<<endl;
}
}

int main()
{
    kruskal obj;
    obj.read_graph();
    obj.sort_edges();
    obj.algorithm();
    obj.print_min_span_t();
    return 0;
}

I found this code on google which is helping me to understand the kruskal algorithm. However I do not understand the following:

# What is the sets array for?
# What is the top array for?
# What does the find_node method actually do

[TheBear]

Hi,

to answer your question: The set and top arrays are an implementation of a union-find datastructure. It is implemented as follows:

Each set is represented as an array a[10] and a number k saying how many elements are in the set. The actual elements of the set are stored in a[1..k], and a value of k = 0 implies an empty set. This implementation is very limited, as every set can contain 9 elements at maximum.

As the implementation needs at most 100 sets, so there are 100 arrays, which gives the array set[100][10]. The top array contains the respective number of elements for each set.

find_node returns the number (index) of the set, which contains the node given as parameter. It finds the set which contains a given node.


This should answer your questions. Now to the real problem. This code is a mess and not eligible to use for any purpose, especially for learning kruskals algorithm. Its a mess, because
a) It will probably crash or give wrong results for graphs with more than 9 nodes.
b) It is far far away from the ideal of "self-explaining code" (Your questions are a result of that).
c) ... (there are much more points like use of highly inefficient data structures, bad encapsulation etc.)

Please drop it and read a book (e.g. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein) or search for some better code.

I hope this helps;
TheBear

[John Linux]

Very good explanations, and yes, I agree this code is horribly written. I just wanted to understand it so that I could re-write it myself. I could not even get it onto a paper algorithm.

The majority of code I found on google was rubbish and didn't run, or was based on this exact code. The graphs given to us are very simple for this, so I shouldn't need more than 9 sets as far as I'm aware.

Thanks for the help though, highly appreciated.