在 C++ 中使用邻接表实现广度优先搜索时出错

Question

我正在尝试使用 C++ 中的邻接表实现广度优先搜索代码。但它显示分段错误。我不知道我的代码在哪里做错了什么。我尝试了我所知道的一切来解决这个问题，但我做不到。如果有人帮助解决我代码中的错误，这对我来说真的很有用。

只有当我输入一个复杂的图形时它才会给出错误，但是当我输入一个简单的图形时它会给出答案，我不知道出了什么问题。

代码如下：

#include<iostream>
#include<list>
#include<iterator>
using namespace std;


class graph 
{ 
    int v;    // No. of vertices 
    list<int> *adj; //pointer to the list    
public: 
    graph(int v);  // Constructor 
    void addedge(int s, int d);  
    void BFS(int s);
    void s_d(int v);
};


graph::graph(int vertice) 
{ 
    this->v=vertice; 
    adj = new list<int>[v]; //adj is list pointer which is now pointing to the first list in an array of lists 
} 


void graph::addedge(int s, int d) 
{ 
    adj[s].push_back(d); // Add value d to list number s. 
//  adj[d].push_back(s);
}


void graph::BFS(int s)
{
 bool *visited = new bool[v];   //created a bool arr of size same that of vertices v(v declared in class)
 for(int i=0;i<v;i++)           //make all vertices as not visited at first
    {
     visited[i]=false;
    }
 list<int> queue;       //create a list queue to store all to visit nodes
 visited[s]=true;       //mark the current node as visited bcoz we are on that node currently
 queue.push_back(s);    //put current node in queue 
 list<int>::iterator i; //make an iterator i which will iterate through the list

 while(!queue.empty())
    {
     s=queue.front();
     cout<<s<<' ';       //printing in ur visited order
     queue.pop_front();  //pop and display the visited vertice
     //down here in for loop we iterating through the elements inside the lists first list,second ,third...
     for(i=adj[s].begin(); i != adj[s].end();i++) //iterate i(iterator) from pointer adj current list number fully till <NULL
        {
         if(!visited[*i])  
            {
             visited[*i] = true;   //if the roots adjacent we looking at now aint visited then make it visited and put into queue 
             queue.push_back(*i);
            }
        }
    }
}


void graph::s_d(int v)  //source and destination for edges input
{
 int s,d,source,edges;      //s is source and "source" is starting vertice for bfs
 cout<<"enter the number of edges present : ";
 cin>>edges;
 cout<<"enter the source and destinations for your vertices : "<<'\n';
 for(int i=0;i<edges;i++)
    {
     cout<<"edge number "<<i+1<<" enter : "<<'\n';
     cin>>s>>d;
     addedge(s,d);
    }
 cout<<"enter the starting source : ";
 cin>>source;
 BFS(source);
} 


int main()
{
    int v;
    cout<<"enter the number of vertices for your graph : ";
    cin>>v;
    graph g(v);
    g.s_d(v);
    cout<<'\n';
    return 0;
}

这是给出答案的输入：

vertices 5 and edges 7

inputs |0 1|0 4|1 4|1 3|1 2|4 3|3 2| 给出答案：0 1 4 3 2 (source start 0)

给出分段错误的输入：

vertices 6 edges 8 (source start 1)

inputs |1 2|1 6|2 3|2 5|3 4|3 5|5 4|5 6| error segmentation fault(core dumped)

Answer 1

正如其他人所指出的，这是索引问题。

adj = new list<int>[v + 1]; // add + 1

在 graph::graph() 函数的第 21 行中，将 v 更改为 v + 1 使您的输入有效。

发生分段错误是因为您分配了 V 个元素（从索引 0 到索引 V-1）并试图访问第 (V+1) 个元素（索引为 V）

在 C++ 中使用邻接表实现广度优先搜索时出错

Error Implementing Breadth First Search using adjacency list In C++

c++

breadth-first-search

adjacency-list