Kruskal C implementation

Question

I have implemented the Kruskal algorithm in C using an adjacency matrix graph representation, the problem is, it keeps popping up segmentation fault error, I've been trying to figure out what is wrong for quite a while and I can't seem to find the problem, could anyone else take a look please? Thanks.

Here is my code:

#include <stdio.h>
#include <stdlib.h>

#define MAXVERT 10
#define MAXEDGES 20
#define INF 100000

/*graph representation using an Adjacency matrix*/
typedef struct AdjMatrix
{
    int nodes;
    int adjMat[MAXVERT][MAXVERT];
} graph;

/*function prototypes*/
int find(int node, int *trees);
void merge(int i, int j, int *trees);
void printminimal(int min[][3], int n);

/*main algorithm*/
void kruskal(graph *g)
{
    int EDGES[MAXEDGES][3]; /*graph edges*/
    int MINEDGES[MAXVERT-1][3]; /*edges already in the minimal spanning tree*/
    int nextedge=0;
    int numedges=0;
    int trees[MAXVERT]; /*tree subsets*/
    int i, j, k;
    int temp;

    for(i=0;i<g->nodes;i++)
        trees[i]=i;
    k=0;

    for(i=0; i<g->nodes; i++)
        for(j=0; j<g->nodes; j++)
        {
            if(i<j)
            {
                EDGES[k][0]=i;
                EDGES[k][1]=j;
                EDGES[k][2]=g->adjMat[i][j];
                k++;
            }
            else
                break;
        }

    /*Bubblesort*/
    for(i=0; i<g->nodes; i++)
        for(j=0; j<i; j++)
        {
            if(EDGES[j][2] > EDGES[j+1][2])
            {
                temp=EDGES[j][0];
                EDGES[j][0]=EDGES[j+1][0];
                EDGES[j+1][0]=temp;
                temp=EDGES[j][1];
                EDGES[j][1]=EDGES[j+1][1];
                EDGES[j+1][1]=temp;
                temp=EDGES[j][2];
                EDGES[j][2]=EDGES[j+1][2];
                EDGES[j+1][2]=temp;
            }
        }

    while(numedges < (g->nodes-1))
    {
        i=find(EDGES[nextedge][0], trees);
        j=find(EDGES[nextedge][1], trees);
        if((i!=j)&&(EDGES[nextedge][2]!=-1))    /*check if the nodes belong to the same subtree*/
        {
            merge(i,j,trees);
            MINEDGES[numedges][0]=EDGES[nextedge][0];
            MINEDGES[numedges][1]=EDGES[nextedge][1];
            MINEDGES[numedges][2]=EDGES[nextedge][2];
            numedges++;
        }
        nextedge++;
    }
}

int find(int node, int *trees)   
{
    if(trees[node]!=node)
        return trees[node];
    else
        return node;
}
void merge(int i, int j, int *trees)
{
    if(i<j)
        trees[j]=i;
    else
        trees[i]=j;
}
void printminimal(int min[][3], int n)
{
    int i, weight=0;
    printf("Minimal tree:\n(");
    for(i=0;i<n;i++)
    {
        printf("(V%d,V%d), ", min[i][0],min[i][1]);
        weight+=min[i][2];
    }
    printf(")\n Total weight sum of the minimal tree is: %d", weight);
}
int main(void)
{
    int i,j;
    graph *g=(graph *)malloc(sizeof(graph));
    /*int adjMat[8][8] = {0,INF,INF,11,INF,1,7,
                          INF,0,INF,3,INF,4,8,INF,
                          INF,INF,0,INF,INF,INF,12,INF,
                          INF,3,INF,0,15,INF,INF,INF,
                          11,INF,INF,INF,0,20,INF,INF,
                          INF,4,INF,INF,20,0,INF,INF,
                          1,8,12,INF,INF,INF,0,5,
                          7,INF,INF,INF,INF,INF,5,0};*/
    for(i=0;i<4;i++)
        for(j=0;j<i;j++)
        {
            if(i==j)
            {
                g->adjMat[i][j]=0;
                continue;
            }
            printf("%d-%d= ", i, j);
            scanf("%d", &(g->adjMat[i][j]));
            g->adjMat[j][i]=g->adjMat[i][j];
        }
    g->nodes=4;
    kruskal(g);
}

Answer 1

In the kruskal function, where you intend to populate the EDGES array, you don't:

for(i=0; i<g->nodes; i++)
    for(j=0; j<g->nodes; j++)
    {
        if(i<j)
        {
            EDGES[k][0]=i;
            EDGES[k][1]=j;
            EDGES[k][2]=g->adjMat[i][j];
            k++;
        }
        else
            break;
    }

For j == 0, i is never < j, so you immediately break out of the inner loop. I suspect it should be i > j in the condition.

Since EDGES is uninitialised, find tries to access an unspecified element of trees.

Answer 2

I had to add the following to get this to kruskal to get it to compile from gcc:

int *dvra = trees;

You can then compile it with debug information:

gcc -g -o kruskal kruskal.c

and run it through gdb:

gdb kruskal

You can then type run and enter to start the program. I entered 1,2,3,... when prompted for values.

This then gives:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a92 in find (node=32767, trees=0x7fffffffe110) at test.c:86
86      if(trees[node]!=node)

Hmm, that's curious. Trees holds only 10 items (value of the MAXVERT define), so accessing node 32767 goes out of bounds. If you enter 32767 in the calculator program and go to the programming (hexadecimal) mode, you will find it is 7FFF (or MAX_SHORT, the maximum 16-bit signed integer value). That's also interesting.

NOTE: You can investigate variable values by using the print command (e.g. print node) and the backtrace using the bt command.

These are coming from the while loop in kruskal (the only place that is calling find), so we need to investigate where that value is coming from. Lets quit out of gdb (press 'q' and enter then confirm with 'y' and enter).

Add the following to the while loop and run the resulting program:

printf("%d: nextedge=%d EDGES[nextedge][0]=%d EDGES[nextedge][1]=%d\n", numedges, nextedge, EDGES[nextedge][0], EDGES[nextedge][1]);

which gives:

0: nextedge=0 EDGES[nextedge][0]=-557487152 EDGES[nextedge][1]=32767

So it looks like EDGES[0] is not being initialized, which points to the if(i<j) condition in the initialization loop above the bubblesort. OK, so lets trace what is happening in the initialization loop by adding the following inside the if loop:

printf("EDGES[%d]: 0=%d 1=%d\n", k, i, j);

Rerunning this, we see that there are no lines associated with this statement, so it is not getting executed.

Changing the if condition to:

if(i<=j)

causes the statement to be executed and the segment fault to go away.