广度优先搜索陷入死循环

Question

我正在尝试实施广度优先搜索算法，但由于某些原因它陷入了无限循环。

我尝试通过输出各种值来调试它，但仍然没有成功。

我的 Bfs 代码


    int s=0;
    bool vis[n];
    int dist[n];

    for(int i=0;i<n;i++){
        vis[i]=false;
        dist[i]=INT_MAX;
    }

    dist[s]=0;
    vis[s]=true;
    q_push(s);



    while(!q_isEmpty()){
        int u = queu[0];
        for(int v=0;v<n;v++){
            if(adjMat[u][v]==1){
                if(vis[v]==false){
                    vis[v] == true;
                    dist[v]=dist[u]+1;
                    q_push(v);
                    cout<<v;
                }
            }
        }

        q_pop();


    }

我的队列已全局声明其代码

vector <int> queu;

void q_push(int d){
    queu.insert(queu.end(),d);

}

void q_pop(){
    queu.erase(queu.begin());
}

bool q_isEmpty(){
    return queu.empty();
}

我将邻接矩阵作为其代码的输入。

int n;
cin>>n;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        int temp;
        cin>>temp;
        adjMat[i][j]=temp;
    }
}

Answer 1

改变这个：

vis[v] == true;

对此：

vis[v] = true;

由于您想将相邻节点 v 标记为已访问，通过为其赋值 true - 您错误地使用了比较运算符而不是赋值运算符，因此您保留并继续访问您已经访问过的节点遍历一遍又一遍，进入死循环..

PS：不是无限循环的原因，但正如@PaulMcKenzie 评论的那样，您 could/should 使用 std::queue.

广度优先搜索陷入死循环

Breadth first search stuck in infinite loop

c++

graph-theory

breadth-first-search

graph-traversal