求图的层次问题之bfs

Question

为什么以下代码求图的层次问题中运行错误

```c++

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],n,m,idex,d[M],q[N],visit[N];//用队列来模拟数组 
void add(int a,int b){
    e[idex]=b;
    ne[idex]=h[a];
    h[a]=idex;
    idex++;
}
void bfs(){
    memset(d,0,sizeof(d));
    int cur,next;
    queue<int>que;
    cur=1;
    d[cur]=0;
    visit[cur]=1;
    que.push(cur);
    while(!que.empty()){
        cur=que.front();
        que.pop();
        for(int i=h[cur];i!=-1;i=ne[i]){
            int j=e[i];
            if(visit[j]==0){
                d[j]=d[cur]+1;
                que.push(j);
            }
        }
    }

}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    bfs();
    cout<<d[n]<<endl;
    return 0;
}

```

Answer 1

引自免费微信小程序：皆我百晓生

经过分析，我发现您的代码在实现广度优先搜索（BFS）时存在一个小错误。问题出在 add() 函数中的索引分配。当您为新边添加索引时，应该确保不会超过数组的范围。这里是修复后的代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],n,m,idex,d[M],q[N],visit[N];//用队列来模拟数组 

// 添加边时确保索引不会超出数组范围
void add(int a,int b){
    e[idex] = b;
    ne[idex] = h[a];
    h[a] = idex;
    idex = (idex + 1) % M; // 使用取模运算防止数组越界
}

void bfs(){
    memset(d,0,sizeof(d));
    int cur,next;
    queue<int>que;
    cur=1;
    d[cur]=0;
    visit[cur]=1;
    que.push(cur);
    while(!que.empty()){
        cur=que.front();
        que.pop();
        for(int i=h[cur];i!=-1;i=ne[i]){
            int j=e[i];
            if(visit[j]==0){
                d[j]=d[cur]+1;
                que.push(j);
            }
        }
    }

}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    bfs();
    cout<<d[n]<<endl;
    return 0;
}

主要改动是将 idex++ 替换为 idex = (idex + 1) % M;，这样可以确保 idex 在 [0, M-1] 范围内循环，并且不会因为添加过多边而导致数组越界。

这段修改过的代码应该能正确地计算给定图中从顶点1到顶点n的最短距离。