BFS遍历图节点两次

Question

我很难在我的这段代码中找到图形中出现节点的错误 twice.I 使用向量来存储边之间的关系。非常感谢任何帮助。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> v[n+1];
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    std::queue<int>q ;
    q.push(1);
    cout<<"And the traversal is:\n";
    bool visited[n+1]={false};
    for(;!q.empty();){
        int curr=q.front();
        q.pop();
        cout<<curr<<endl;
        for(int i=0;i<v[curr].size();++i){
            if(!visited[v[curr][i]]){
                q.push(v[curr][i]);
                visited[curr]=true;
            }
        }
    }
}

我检查的输入：

输出：

And the traversal is:
1
3
2
5
4
4

Answer 1

您需要区分节点可能处于的三种状态：

未处理（未见）
发现（排队）
处理（遍历，输出）

使用 visited 布尔数组，您可以在发现节点或遍历节点时标记节点。虽然术语 "visited" 通常指的是后者，但使用前者意味着节点不会多次添加到队列中并且不需要额外的 if (visited[curr]) continue; 检查。

因此，要做到这一点，您需要在代码中修复两件事：

初始化队列的起始节点(1)已被定义发现
在当前节点的邻居循环中，您不能将邻居标记为visited[curr]，而是在将其添加到队列时将其实际标记为"discovered"

cout<<"And the traversal is:\n";
std::queue<int>q;
bool visited[n+1]={false};
q.push(1);
visited[1] = true;
while(!q.empty()){
    int curr=q.front();
    q.pop();
    cout<<curr<<endl;
    for(int i=0;i<v[curr].size();++i){
        int target = v[curr][i]; // opposite node on edge 
        if(!visited[target]){
            q.push(target);
            visited[target]=true;
        }
    }
}

下面的旧（不完整）答案
~~您想将 current 节点设置为 visited always，不仅是当它有一个尚未访问的邻居时（4事实上没有任何邻居）。将其移出循环：~~

~~for(int i=0;i<v[curr].size();++i){ if(!visited[v[curr][i]]){ q.push(v[curr][i]); } } visited[curr]=true;~~

~~也许你甚至应该把它移到循环前面，以防万一有自循环边缘。~~

BFS遍历图节点两次

BFS traverses graph node twice

c++

breadth-first-search