0

learning graph theory in c++ here. Sorry for the C-style codes. I got an segmentation fault of my codes. I understand the meaning of it but have not learnt how to debug with IDE yet. However I feel the bug is somewhere in my spanningtree() function. Could anyone point me out what could went wrong? The program is meant to print out the cost matrix, the minimum distance path and the total path cost. However, it exited after inputting.

#include <iostream>
using namespace std;
class prims
{
private:
    int no_of_edges, no_of_nodes;
    int graph[10][10],visited[10],mindist[10];
public:
    void input();
    void output();
    void spanningtree();

    prims()
    {
        no_of_edges = no_of_nodes = 0;
        for (int i = 0; i<10; i++)
        {
            //assign visited minimum distance array to 0
            visited[i] = mindist[i] = 0;
            for (int j = 0; j<10; j++)
            {
                graph[i][j] = 0;
            }

        }
    }
};

void prims::input()
{
    int vertex1, vertex2, cost;
    cout << "Enter no_of_nodes  ";
    cin >> no_of_nodes;
    cout << "Enter the no_of_edges  ";
    cin >> no_of_edges;
    for (int i = 0; i< no_of_edges; i++)
    {
        cout << "Enter vertex1   ";
        cin >> vertex1;
        cout << "Enter vertex2   ";
        cin >> vertex2;
        cout << "Enter the cost of " << vertex1 << " and " << vertex2 << "  ";
        cin >> cost;
        graph[vertex1][vertex2]=graph[vertex2][vertex1]=cost;
    }
}

void prims::output()
{
    for (int i = 0; i < no_of_nodes; i++)
    {
        cout << endl;
        for (int j = 0; j< no_of_nodes; j++)
        {
            cout.width(4);
            cout << graph[i][j];
        }
    }
}

void prims::spanningtree()
{
    int min = 9999, row, col, index = 0;
    for (int i = 0; i < no_of_nodes; i++)
    {
        for(int j = i; j < no_of_nodes; j++)
        {
            if(graph[i][j]<min&&graph[i][j]!=0)
            {
                min = graph[i][j];
                row = i;
                col = j;
            }
        }
    }
    visited[row]=visited[col]=1;
    mindist[index++]=min;

    for (int i = 0; i < no_of_nodes - 2; i++)
    {
       min = 9999;

        for (int j = 0; j < no_of_nodes; j++)
        {
            if(visited[j]==1)
            {
                for(int k = 0; j < no_of_nodes; k++)
                {
                    if(graph[j][k]<min&&graph[j][k]!=0 && visited[k]==0)
                    {
                        min = graph[j][k];
                        row = j;
                        col = k;
                    }
                }
            }
        }
        mindist[index++]=min;
        visited[row]=visited[col]=1;
    }
    int total = 0;
    cout << endl;
    cout << "Minimum distance path is ";
    for (int i=0; i < no_of_nodes-1; i++)
    {
        cout << " " << mindist[i] << " ";
        total = total + mindist[i];
    }
    cout << endl << "Total path cost is    " << total;
}




int main()
{
    prims obj;
    obj.input();
    obj.spanningtree();
    obj.output();
    return 0;
}
6
  • 2
    Please read How to Ask and tour and minimal reproducible example. The purpose of this site is not to be a code-dump-debugging service, but rather a repository of interesting questions that might help future searchers. Not to be rude, but the best answer I have to "have not learnt how to debug with IDE yet" is "Learn how. Preferably now." Commented Jun 4, 2020 at 22:18
  • Links rot and when they do anything at the link is lost. If your question depends too much on a link, and this question does, it will become useless. Godbolt I trust enough to visit, so I've copied your code over. I haven't inspected it closely, but it probably isn't a valid minimal reproducible example. Commented Jun 4, 2020 at 22:18
  • "but have not learnt how to debug with IDE yet" Now is a good time to learn. Read this article for some tips to get started. Commented Jun 4, 2020 at 22:23
  • 1
    Typo in your for(int k = 0; j < no_of_nodes; k++) for loop. The comparison should be k < no_of_nodes. Commented Jun 4, 2020 at 22:29
  • 1
    @JohnFilleau and others. Thank you for the suggestions from all. I am planning to learn asap how to debug in the IDE I have been using, Qt. Commented Jun 4, 2020 at 23:25

2 Answers 2

1

Taking some credits from the helpful comments/answers. Here is my revised codes. The main issue was the typo in one of the loop for(int k = 0; j < no_of_nodes; k++).

using namespace std;
class prims
{
private:
    int no_of_edges, no_of_nodes;
    int graph[10][10],visited[10],mindist[10];
public:
    void input();
    void output();
    void spanningtree();
    prims()
    {
        no_of_edges = no_of_nodes = 0;
        for (int i = 0; i<10; i++)
        {
            //assign visited minimum distance array to 0
            visited[i] = mindist[i] = 0;
            for (int j = 0; j<10; j++)
            {
                graph[i][j] = 0;
            }
        }
    }
};
void prims::input()
{
    int vertex1, vertex2, cost;
    cout << "Enter no_of_nodes  ";
    cin >> no_of_nodes;
    cout << "Enter the no_of_edges  ";
    cin >> no_of_edges;
    for (int i = 0; i< no_of_edges; i++)
    {
        cout << "Enter vertex1   ";
        cin >> vertex1;
        cout << "Enter vertex2   ";
        cin >> vertex2;
        cout << "Enter the cost of " << vertex1 << " and " << vertex2 << "  ";
        cin >> cost;
        graph[vertex1][vertex2]=graph[vertex2][vertex1]=cost;
    }
}
void prims::output()
{
    for (int i = 0; i < no_of_nodes; i++)
    {
        cout << endl;
        for (int j = 0; j< no_of_nodes; j++)
        {
            cout.width(4);
            cout << graph[i][j]<<" ";
        }
    }
}
void prims::spanningtree()
{
    int min = 9999, row, col, index = 0;
    for (int i = 0; i < no_of_nodes; i++)
    {
        for(int j = i; j < no_of_nodes; j++)
        {
            if(graph[i][j]<min&&graph[i][j]!=0)
            {
                min = graph[i][j];
                row = i;
                col = j;
            }
        }
    }
    visited[row]=visited[col]=1;
    mindist[index++]=min;
    for (int i = 0; i < no_of_nodes - 2; i++)
    {
       min = 9999;
        for (int j = 0; j < no_of_nodes; j++)
        {
            if(visited[j]==1)
            {
                for(int k = 0; k < no_of_nodes; k++)
                {
                    if(graph[j][k]<min&&graph[j][k]!=0 && visited[k]==0)
                    {
                        min = graph[j][k];
                        row = j;
                        col = k;
                    }
                }
            }
        }
        mindist[index++]=min;
        visited[row]=visited[col]=1;
    }
    int total = 0;
    cout << endl;
    cout << "Minimum distance path is ";
    for (int i=0; i < no_of_nodes-1; i++)
    {
        cout << " " << mindist[i] << " ";
        total = total + mindist[i];
    }
    cout << endl << "Total path cost is    " << total << endl;
}
int main()
{
    prims obj;
    obj.input();
    obj.spanningtree();
    obj.output();
   // return 0;
}
Sign up to request clarification or add additional context in comments.

Comments

0

Your primary problem is not checking that indexes are in range (there is where c++ might help, but you can do it in c as well). Primary debugging tool - print. If you would print j and k before using them as array indexes you would solve your problem yourself

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.