Segmentation Fault, program works fine

Question

I'm implementing the Prim's Algorithm for Minimum Spanning Tree Problem. Program Just works fine and I get the desired output but I received a Segmentation Fault in the End. I checked my program for errors but the program is fine.

Here's Source Code

#include <iostream>
#include <cstdio>
#define INF 1000000
#define N 5

using namespace std;

class Graph
{
    int V;
    int adj[][N];

    public:
        Graph(int,int mat[][N]);
        void primsMST();
};

Graph::Graph(int v, int mat[][N])
{
   this->V = v;
   for(int i=0; i<v; i++)
   {
       for(int j=0; j<v; j++)
           adj[i][j] = mat[i][j];
   }
}

void Graph::primsMST()
{
    int i, j;

    int key[V];     // Key Value which is used to pick minimum weight vertex
    int parent[V];  // To store Tree
    bool mstSet[V];  // Mark Vertex included in MST

    // Initialize Key Values to infinite and mstSet to false
    for(i=0; i<V; i++)
    {
        key[i]=INF;
        mstSet[i] = false;
    }

    // Initialize initial vertex
    key[0] = 0;
    parent[0] = -1;

    int minm, min_i;
    for(int k=0; k<V-1; k++)
    {
        // Get min Key from all vertices
        minm = INF;
        for(i=0; i<V; i++) {
            if(!mstSet[i] && key[i]<minm)
            {
                minm = key[i];
                min_i = i;
            }
        }

        // Include min key vertex in MST
        mstSet[min_i] = true;

        // Update key values of vertices adjacent to min vertex
        for(j=0; j<V; j++)
        {
            if( adj[min_i][j] && !mstSet[j] && adj[min_i][j] < key[j])
            {
                key[j] = adj[min_i][j];
                parent[j] = min_i;
            }
        }
    }

    for(i=0; i<V; i++)
        cout<<i<<", "<<key[i]<<", "<<parent[i]<<endl;

    // Print Minimum spanning Tree
    cout<<"Edge\tWeight"<<endl;
    for(i=1; i<V; i++)
        cout<<i<<"--"<<parent[i]<<"\t"<<adj[i][parent[i]]<<endl;

    cout<<endl;
}

int main()
{

    int adjmat[][N] =  {{0, 2, 0, 6, 0},
                      {2, 0, 3, 8, 5},
                      {0, 3, 0, 0, 7},
                      {6, 8, 0, 0, 9},
                      {0, 5, 7, 9, 0},
                     };

    Graph g(N, adjmat);

    g.primsMST();

    cout<<endl;
    return 0;
}

Program is compiled using gcc version 4.7.2. When I run this program I got the desired output for the Graph but a Segmentation fault occurs in the end.

$ ./primsMST
0, 0, -1
1, 2, 0
2, 3, 1
3, 6, 0
4, 5, 1
Edge    Weight
1--0    2
2--1    3
3--0    6
4--1    5

Segmentation fault

Here's the debugging output using gdb

$ gdb primsMST
GNU gdb (GDB) 7.4.1-debian
Copyright (C) 2012 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/abhishek/myPrograms/geeksforgeeks/graphs/primsMST...done.
(gdb) set logging on
Copying output to gdb.txt.
(gdb) run
Starting program: /home/abhishek/myPrograms/geeksforgeeks/graphs/primsMST 
0, 0, -1
1, 2, 0
2, 3, 1
3, 6, 0
4, 5, 1
Edge    Weight
1--0    2
2--1    3
3--0    6
4--1    5



Program received signal SIGSEGV, Segmentation fault.
0x0000000000000002 in ?? ()
(gdb) backtrace
#0  0x0000000000000002 in ?? ()
#1  0x0000000800000003 in ?? ()
#2  0x0000000000000005 in ?? ()
#3  0x0000000000000003 in ?? ()
#4  0x0000000700000000 in ?? ()
#5  0x0000000800000006 in ?? ()
#6  0x0000000000000000 in ?? ()
(gdb) quit 

Can anyone explain why I'm getting this Error?

Answer 1

You don´t allocate memory for the rows of the ´adj´ matrix member of the of the graph class. This is teh most likely reason of the crash. This may help: This may help.

My understanding is the program runs by chance/because the the adj array is small.

Answer 2

The problem might be cause by the incorrect accesses to the stack allocated arrays (adjmat and/or Graph::adj). Since these arrays are allocated on stack, incorrect accesses might corrupt other data, stored there (like function return address or other variables), which can cause segmentation fault when the destructors are called or when invalid return address is used.