c++ - 特定值的段错误

我编写了一个代码，该代码首先将矩阵的Dimensions（n X m）作为输入，然后将其元素分别为0 s和1 s。现在，我正在尝试使用此矩阵构建图（邻接列表表示），以使所有1都连接到它们相邻的所有其他1（即，垂直，水平或对角线）。矩阵的元素以行主方式编号，以便将它们表示为图形的顶点。

这是代码：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <list>
#include <deque>

using namespace std;

class Graph
{
 public:

    list<int> *adjlist;
    int v;

    Graph(int v)
    {
        this->v=v;
        adjlist=new list<int> [v];
    }

    void add_edge(int src, int dest)
    {
        cout<<src<<" "<<dest<<"\n";
        adjlist[src].push_back(dest);
    }

    void dfs_util(int src, bool *visited)
    {
        if(!visited[src])
        {
            cout<<src<<" ";
            visited[src]=true;
            list<int>::iterator i;
            for(i=adjlist[src].begin(); i!=adjlist[src].end(); i++)
            {
                if(!visited[*i])
                {
                    dfs_util(*i, visited);
                }
            }
        }
    }

    void dfs(int src)
    {
        bool visited[v];
        int i;
        for(i=0; i<v; i++)
            visited[i]=false;
        dfs_util(src, visited);
    }

    void bfs(int src)
    {
        int j;
        bool visited[v];
        for(j=0; j<v; j++)
        {
            visited[j]=false;
        }

        int front;
        deque<int> q;
        q.push_back(src);
        list<int>::iterator i;
        visited[src]=true;


        while(!q.empty())
        {
            front=q.front();
            q.pop_front();
            cout<<front<<" ";

            for(i=adjlist[front].begin(); i!=adjlist[front].end(); i++)
            {
                cout<<*i<<"\n";
                if(!visited[*i])
                {
                    visited[*i]=true;
                    q.push_back((*i));
                }
            }
        }
    }

    void display()
    {
        list<int>::iterator it;
        int i;
        //list<int>::iterator it;

        for(i=0; i<v; i++)
        {
            cout<<"Adj list for "<<i<<"\n";
            for(it=adjlist[i].begin(); it != adjlist[i].end(); ++it)
            {
                cout<<*it<<"->";
            }
            cout<<"\n";
        }
    }
};


int main() {
    int arr[11][11], n, m, i, j, node;
    cin>>n;
    cin>>m;

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            cin>>arr[i][j];
        }
    }

    Graph g(n*m-1);

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            node=m*i+j;
            if(arr[i][j]==1)
            {
                if((i-1)>=0 && arr[i-1][j]==1)
                    g.add_edge(node, m*(i-1)+j);

                if((i-1)>=0 && (j+1)<m && arr[i-1][j+1]==1)
                    g.add_edge(node, m*(i-1)+(j+1));

                if((j+1)<m && arr[i][j+1]==1)
                    g.add_edge(node, m*(i)+(j+1));

                if((i+1)<n && (j+1)<m && arr[i+1][j+1]==1)
                    g.add_edge(node, m*(i+1)+(j+1));

                if((i+1)<n && arr[i+1][j]==1)
                    g.add_edge(node, m*(i+1)+(j));

                if((i+1)<n && (j-1)>=0 && arr[i+1][j-1]==1)
                    g.add_edge(node, m*(i+1)+(j-1));

                if((j-1)>=0 && arr[i][j-1]==1)
                    g.add_edge(node, m*(i)+(j-1));

                if((i-1)>=0 && (j-1)>=0 && arr[i-1][j-1]==1)
                    g.add_edge(node, m*(i-1)+(j-1));
            }
        }
    }

    //g.bfs(0);
    //g.dfs(0);
    g.display();
    return 0;
}

现在，这段代码在调用segmentation fault或g.bfs(0)时给了我g.dfs(0)。因此，我编写了一个简单的显示函数来缩小错误的范围，但是即使调用g.display()也会给我segmentation fault。

但是，当我将display()函数中的外循环更改为：

for(i=1; i<n; i++)

它工作得很好，并且不给出segmentation fault。

我不明白为什么要得到这些segmentation fault，以及如何将外循环的初始化更改为1来防止这种情况。谁能解释原因？

这是我使用的示例输入：

5
5
1 1 0 0 0
0 1 1 0 0
0 0 1 0 1
1 0 0 0 1
0 1 0 1 1

最佳答案

问题

您的邻接列表是一个数组，而不是列表或向量：

list<int> *adjlist;

您可以在构造函数中基于参数v对其进行初始化：

adjlist=new list<int> [v];

因此，在构建图形时，您需要预先提供多少个邻接表？最好不要犯错！

不幸的是，在main()中，您使用缺少的项对其进行了初始化

Graph g(n*m - 1);   //  <----- why -1 ?  Don't you have n*m nodes ?

解

只需以正确的大小调用构造函数

Graph g(n*m);   //  n*m nodes !

您可以通过添加一些边界检查来帮助自己解决此类问题：

void add_edge(int src, int dest)   // src should be smaller than v
{
    if (src>=v) {         // nice diagnostic message in case of problem
       cout <<"FAILURE: "<<src<<" out of bound ("<<v<<")"<<endl;
    }
    else {
        cout<<src<<" "<<dest<<"\n";
        adjlist[src].push_back(dest);
    }
}

在没有总是执行类似的错误消息的情况下，应该至少反映assert满足前提条件：

assert (src<v && dest<v);

最好将邻接列表adjlist设置为矢量或地图，并使其动态增长。