7-2 六度空间 (30 分)

![题目](https://images.gitee.com/uploads/images/2021/0523/200415_34d7a853_8756800.png "屏幕截图.png")

```
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<queue>
using namespace std;
#define MAXV 1021
typedef struct
{
    int** edges;     //邻接矩阵
    long int n, e;
} MGraph;
void CreateMGraph(MGraph& g, long int n, long int e);//邻接矩阵建图 
void ShowGraph(MGraph& g);
int BFSTraverse(MGraph& g, int i);                                 // 广度遍历;
int visited[MAXV];
int main()
{
    long int M, N;
    double rate=0;
    MGraph G;

cin >> N >> M;
    CreateMGraph(G, N, M);
    //ShowGraph(G);
    for (int i = 1; i <= G.n; i++)
    {
        rate = 100.0 * BFSTraverse(G,i)/ G.n;
        printf("%d: %.2f%%\n",i,rate);
    }
    return 0;
}

void CreateMGraph(MGraph& g, long int n, long int e)//建图
{
    long int i, j, a, b;
    g.edges = (int**)malloc(sizeof(int*) * 1102);
    for (i = 0; i <= n; i++)
    {
        g.edges[i] = (int*)malloc(sizeof(int) * 1102);
        for (j = 0; j <= n; j++)
        {
            g.edges[i][j] = 0;
        }
    }
    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        g.edges[a][b] = 1;
        g.edges[b][a] = 1;
    }
    g.n = n;
    g.e = e;
}

int BFSTraverse(MGraph& g, int i)// 广度遍历;
{
    queue<int>q;
    int level = 0;//层数
    int j, k;  
    int last;//每层末尾结点
    int temp = 0;
    int count=1;
    int tail=0;//最后入队

for (j = 0; j <= g.n; j++)
    {
        visited[j] = 0;
    }
    visited[i] = 1;
    last = i;
    q.push(i);//入队
    while (!q.empty())
    {
        temp = q.front();
        q.pop();//出队
        for (j = 1; j <= g.n; j++)
        {
            if (g.edges[temp][j] && !visited[j])
            {
                visited[j] = 1;
                q.push(j);
                count++;
                tail = j;
            }
        }
        if (temp == last)
        {
            level++;
            last = tail;
        }
        if (level == 6)
        {
            break;
        }
    }
    return count;
}
void ShowGraph(MGraph& g)
{
    for (int i = 0; i <= g.n; i++)
    {
        for (int j = 0; j <= g.n; j++)
        {
            cout << g.edges[i][j]<<" ";
        }
        cout << endl;
    }
}
```

秣羽konjac/网络2011 博客代码

内容风险标识

评论 (0)

秣羽konjac/网络2011 博客代码 .gitee-modal { width: 500px !important; }

内容风险标识