c++ - 在 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)