虽然以 BFS 顺序遍历图形会在 C++ 中出现分段错误（核心转储）

Question

我正在检查路径是否存在于两个顶点之间的无向图中。在这里，我使用邻接表制作了一个无向图。我正在 BFS 中从源顶点遍历到目标顶点，以检查是否存在路径并维护访问了哪些顶点。

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

// This class represents a undirected graph using adjacency list 
// representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    bool isReachable(int s, int d);  
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

// A BFS based function to check whether d is reachable from s.
bool Graph::isReachable(int s, int d)
{
    // Base case
    if (s == d)
      return true;

    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    list<int> queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);

    // it will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;

    while (!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
        queue.pop_front();

        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            // If this adjacent node is the destination node, then 
            // return true
            if (*i == d)
                return true;

            // Else, continue to do BFS
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }

    // If BFS is complete without visiting d
    return false;
}

// Driver program to test methods of graph class
int main()
{
    // Create a graph given in the above diagram
    int x,y,a,b;
    cin>>x>>y;
    Graph g(x);
    while(y--){
        cin>>a>>b;
        g.addEdge(a, b);
        g.addEdge(b, a);
    }
    int u, v;
    cin>>u>>v;
    if(g.isReachable(u, v))
        cout<<1<<endl;
    else
        cout<<0<<endl;

}

它给了我以下输入的 Segmentation fault (core dumped) 错误：-

我的输入格式：-
一行中的顶点数大于边数。
下一条边线中的边顶点。
在最后一行中，两个顶点之间是否存在路径。

上述输入的预期输出为 1。

我认为错误发生在 for (i = adj[s].begin(); i != adj[s].end(); ++i) 之后，但我无法更正它。
谁能帮我解决这个问题？

Answer 1

My input format:- the number of vertexes than the number of edges in

one line. Edge Vertices in the next number of edges lines. In last

lines two vertex between which path is present or not.

可能原因

您的输入节点范围是从 0 到 V - 1 吗？如果你的输入节点范围[1... V]，那么它会导致数组越界异常。为了快速检查，请尝试初始化 adj 和 visited 数组的大小 V + 100 并检查它是如何工作的。

Answer 2

问题是

你说的顶点数是4然后是adj = new list<int>[V]; 所以 adj[0] 到 adj[v-1] 是有效的。然后你尝试创建一条从 4 到 3 的边，并尝试访问 addEdge() 中的 adj[4]，这是越界的。

要么分配 V+1 lists，要么在添加边时从顶点号中减去 1。

虽然以 BFS 顺序遍历图形会在 C++ 中出现分段错误（核心转储）

While traversing graph in BFS order gives Segmentation fault (core dumped) in C++

c++

algorithm

graph-theory

breadth-first-search

可能原因