6-2 邻接表存储图的广度优先遍历 代码实现

好的，我理解了。以下是一个 C++ 实现的邻接表存储图的广度优先遍历代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=100005,maxm=500005;
int n,m;
int head[maxn],ver[maxm],nxt[maxm],edge[maxm],tot=1;
int d[maxn],vis[maxn],ans[maxn];

void add(int x,int y,int z){
    ver[++tot]=y;
    nxt[tot]=head[x];
    edge[tot]=z;
    head[x]=tot;
}

void bfs(int s){
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(ans,0,sizeof(ans));
    queue<int> q;
    q.push(s);
    d[s]=0,vis[s]=1,ans[d[s]]++;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                if(!vis[y]){
                    q.push(y);
                    vis[y]=1;
                    ans[d[y]]++;
                }
            }
        }
        vis[x]=0;
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); // 无向图需要反向建边 
    }
    bfs(1);
    for(int i=0;i<n;i++){
        if(ans[i]!=0){ // 输出到达每个点的最短路径的数量 
            printf("%d:%d\n",i,ans[i]);
        }
    }
    return 0;
}

这个代码实现了邻接表存储的无向图的广度优先遍历，并输出了到达每个点的最短路径的数量。当然，具体实现时要根据题目的具体要求来修改。