在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）