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

我正在尝试使用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 7inputs |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)

最佳答案

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

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

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

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

关于c++ - 在C++中使用邻接表实现广度优先搜索时出错，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60797845/