Ошибка сегментации для определенного значения

Question

Я написал код, который сначала принимает размеры (n X m) матрицы в качестве входных данных, а затем ее элементы, которые являются 0 s и 1 s. Теперь я пытаюсь построить граф (представление списка смежности), используя эту матрицу так, чтобы все 1 s были связаны со всеми остальными 1 s, которые находятся рядом с (то есть по вертикали, по горизонтали или по диагонали). Элементы матрицы пронумерованы в строчном порядке, чтобы представить их как вершины графа.

Вот код:

#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 

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 вектор или карту, и пусть она динамически растет.