特定值的分割錯誤

Question

我寫了一個代碼，它首先將矩陣的維（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 s以及如何將外環的初始化更改爲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 

Answer 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載體或地圖，並讓它動態增長。