7-10 六度空间（30 分）（bfs）

思路：找出每个点到其他点距离小于等于六的路径有多少条，求其占全部路径的百分比。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int map[1010][1010],vis[1010],cnt[1010];
int n,m;
int num,sum;
queue<int>q;
void bfs(int x)
{
    if(cnt[x]<6)
    {
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&map[x][i])
            {
                cnt[i] = cnt[x]+1;//起始层数为0,当不超过6的时候可以加一
                vis[i] = 1;
                sum++;
                q.push(i);

            }
        }
    }
    if(!q.empty())
    {
        x = q.front();
        q.pop();
        bfs(x);
    }
}
void slove()
{
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        sum = 1;
        cnt[i] = 0;
        vis[i] = 1;
        bfs(i);
        printf("%d: %.2lf%%\n",i,(sum*1.0)/(n*1.0)*100.0);
    }
}
int main()
{
    int u,v;
    scanf("%d %d",&n,&m);
    memset(map,0,sizeof(map));
    while(m--)
    {
        scanf("%d %d",&u,&v);
        map[u][v] = map[v][u] = 1;
    }
    slove();
    return 0;
}

方法二：

#include<iostream>
#include<queue>
using namespace std;
int g[10001][10001],v,e,x,y,i;
int bfs(int z)
{
    int i,vis[10001]={0};
    int last=z;//记录每层的最后一个元素：该层压入之后弹出之前更新：last=temp；
    int tail;//用于记录每层压入时的结点
    int level=0;
    int count=1;
    queue<int>q;
    q.push(z);
    vis[z]=1;
    while(!q.empty())
    {
        z=q.front();
        q.pop();
        for(i=1;i<=v;i++)
        {
            if(g[z][i]==1 && vis[i]==0)
            {
                count++;
                vis[i]=1;
                q.push(i);
                tail=i;
            }
        }
        if(last==z)//一层全部弹出，准备开始弹下一层：弹出的(x)=当前层最后一个元素(last) 
        {
            level++;
            last=tail;//一层全都压入完后，更新last
        }
        if(level==6) break;
    }
    return count;
}
int main()
{
    cin>>v>>e;
    while(e--)
    {
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }
    for(i=1;i<=v;i++)
    {
        double n=v;
        double m=bfs(i);
        printf("%d: %.2f%%\n",i,m/n*100);
    }
    return 0;
}