在 C++ 中使用 BFS 获取 2 个顶点之间的路径

Question

我已经为此编写了代码，但它给出了断开连接的图的分段错误。它适用于连接的图形。我该如何克服这个错误？

vector<int> getPathBFS(int V, int** edges,int v1, int v2, int* visited, unordered_map<int,int> t)
{
    queue<int> q;
    q.push(v1);
    visited[v1]=1;
    int done=0;
    while(!q.empty() && done==0)
    {
        for(int i=0;i<V;i++)
        {
            int front=q.front();
            q.pop();
            if(edges[front][i]==1 && visited[i]!=1)
            {
                q.push(i);
                t[i]=front;
                visited[i]=1;
                if(i==v2)
                {
                    done=1;
                    break;
                }
            }
        }
    }
    vector<int> a;
    if(done==0)
        return a;
    else
    {
        int k=v2;
        a.push_back(v2);
        while(k!=v1)
        {
            k=t[k];
            a.push_back(k);
        }
        return a;
    }
}

int main()
{
    int V, E;
    cin >> V >> E;   
    int** edges=new int*[V];
    for(int i=0;i<V;i++)
    {
        edges[i]=new int[V];
        for(int j=0;j<V;j++)
        {
            edges[i][j]=0;
        }
    }

    for(int i=0;i<E;i++)
    {
        int f,s;
        cin>>f>>s;
        edges[f][s]=1;
        edges[s][f]=1;
    }
    int v1,v2;
    cin>>v1>>v2;

    int* visited=new int[V];
    for(int i=0;i<V;i++)
        visited[i]=0;
    unordered_map<int,int> t;
    t[v2]=0;
    vector<int> ans=getPathBFS(V,edges,v1,v2,visited,t);
    for(int i=0;i<ans.size();i++ && !ans.empty())
    {
        cout<<ans[i]<<" ";
    }

    delete [] visited;
    for(int i=0;i<V;i++)
    {
        delete [] edges[i];
    }

    delete [] edges;

    return 0;
}

我干了一段运行代码。它将首先创建邻接矩阵边并标记其中的所有边。 Visited 数组用于跟踪到目前为止已经访问过的所有顶点，因此不会出现无限循环。对于下面给出的测试用例，它会工作直到队列包含 1，然后它会弹出 1 并且循环将结束，因为没有剩余的边连接到 1 并且未被访问。在此之后，while 循环应该理想地中断并且作为 done==0 它应该 return 一个空向量。不明白为什么会出现segmentation fault

地图用于跟踪哪个顶点被哪个顶点放入队列。

不适用于测试用例：

下面是上述测试用例的图形图像：

这里我们需要找到从顶点0到顶点3的路径。输入格式为：图中的顶点数，边数

顶点之间的边（对于 E 线），

我们需要找到路径的顶点。

Answer 1

您错误地弹出了 BFS 队列。您应该在外循环中弹出队列，而不是为队列中的每个条目执行 |V| 次的内部 for 循环，它为队列中的每个元素执行一次。

vector<int> getPathBFS(int V, int** edges,int v1, int v2, int* visited, unordered_map<int,int> t)
{
    queue<int> q;
    q.push(v1);
    visited[v1]=1;
    int done=0;
    while(!q.empty() && done==0)
    {
        int front=q.front();
        q.pop();

        for(int i=0;i<V;i++)
        {
            if(edges[front][i]==1 && visited[i]!=1)
            {
                q.push(i);
                t[i]=front;
                visited[i]=1;
                if(i==v2)
                {
                    done=1;
                    break;
                }
            }
        }
    }
    vector<int> a;
    if(done==0)
        return a;
    else
    {
        int k=v2;
        a.push_back(v2);
        while(k!=v1)
        {
            k=t[k];
            a.push_back(k);
        }
        return a;
    }
}

此外，在您代码的 main 函数中，您打印答案的 for 循环中有一个冗余表达式 !ans.empty()。

在 C++ 中使用 BFS 获取 2 个顶点之间的路径

Get path between 2 vertices using BFS in C++

c++

algorithm

graph-theory

graph-algorithm

breadth-first-search