基本算法的快速实现

Question

此处学习c ++中的图论。对不起，C风格的代码。我的代码出现段错误。我了解它的含义，但还没有学会如何使用IDE进行调试。但是我觉得这个错误在我的spanningtree()函数中。谁能指出我可能出了什么问题？该程序用于打印成本矩阵，最小距离路径和总路径成本。但是，输入后退出。

#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;
}

Answer 1

您的主要问题是不检查索引是否在范围内（c ++可能在其中有所帮助，但您也可以在c中做到这一点）。主要调试工具-打印。如果在将j和k用作数组索引之前先打印它们，则可以自己解决问题

Answer 2

从有用的评论/答案中获得一些功劳。这是我的修改代码。主要问题是循环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;
}