Блог

Я написал код, который сначала принимает размеры ( 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 amp;amp; arr[i-1][j]==1)
                    g.add_edge(node, m*(i-1) j);

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

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

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

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

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

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

                if((i-1)>=0 amp;amp; (j-1)>=0 amp;amp; 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) or 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 (src<v amp;amp; dest<v);   
  

Лучше было бы сделать ваш список смежности adjlist вектором или картой и позволить ему динамически расти.