【PTA数据结构 | C语言版】验证六度空间理论

本专栏持续输出数据结构题目集，欢迎订阅。

题目

所谓“六度空间理论”是指：在世界上任何两个陌生人之间所间隔的人数不会超过 6 个。本题就请你编写程序，根据输入的人与人之间的关系，统计以某个人为起点的所有满足该理论（即与该起点之间间隔的人数不超过 6 个）的人数，并且计算这个人数在总人数中的占比。

输入格式：
输入首先在第一行给出可能参与统计的最大人数，即正整数 kMaxVertex（≤10^3）。
第二行给出两个正整数，依次为当前参与统计的人数 n 和人际关系数 m（保证 n 至少为 2 且不超过最大人数，m 不超过 33n）。
随后 m 行，每行给出两个直接认识的人的编号（从 0 开始）。
最后给出起点人的编号 v。
同行数字、字符均以一个空格分隔。

输出格式：
在一行中输出以 v 为起点的所有满足“六度空间理论”的人数在总人数中的占比，格式为 x.yy%，即输出小数点后 2 位。

输入样例：
20
20 19
0 1
0 2
2 3
4 5
5 6
6 7
7 8
8 9
9 10
10 11
4 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
5 14
4

输出样例：
70.00%

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_VERTEX 1000// 图结构定义 - 使用邻接矩阵表示
typedef struct {int adj[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵int n;                           // 顶点数
} Graph;// 队列结构 - 用于广度优先搜索
typedef struct {int data[MAX_VERTEX];int front, rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = q->rear = 0;
}// 检查队列是否为空
int isQueueEmpty(Queue *q) {return q->front == q->rear;
}// 入队操作
void enqueue(Queue *q, int v) {q->data[q->rear++] = v;
}// 出队操作
int dequeue(Queue *q) {return q->data[q->front++];
}// 初始化图
void initGraph(Graph *g, int n) {g->n = n;// 初始化邻接矩阵所有元素为0for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {g->adj[i][j] = 0;}}
}// 添加无向边
void addEdge(Graph *g, int u, int v) {g->adj[u][v] = 1;g->adj[v][u] = 1;
}// BFS实现 - 计算从顶点v出发，距离不超过6的顶点数
int bfs(Graph *g, int v) {int visited[MAX_VERTEX] = {0}; // 标记顶点是否被访问int level[MAX_VERTEX] = {0};   // 记录顶点距离起点的层数Queue q;initQueue(&q);visited[v] = 1;      // 标记起点为已访问enqueue(&q, v);      // 起点入队int count = 1;       // 至少包含起点自身while (!isQueueEmpty(&q)) {int u = dequeue(&q); // 取出队首顶点// 如果当前层数已经达到6，不再继续扩展if (level[u] >= 6) continue;// 逆序遍历邻接顶点 - 确保与输入顺序一致for (int i = g->n - 1; i >= 0; i--) {// 如果存在边且未被访问if (g->adj[u][i] && !visited[i]) {visited[i] = 1;            // 标记为已访问level[i] = level[u] + 1;   // 层数加1enqueue(&q, i);            // 入队count++;                   // 计数加1}}}return count; // 返回距离不超过6的顶点总数
}int main() {int kMaxVertex;scanf("%d", &kMaxVertex);int n, m;scanf("%d %d", &n, &m);Graph g;initGraph(&g, n);// 读取边信息，构建邻接矩阵for (int i = 0; i < m; i++) {int u, v;scanf("%d %d", &u, &v);addEdge(&g, u, v);}int v;scanf("%d", &v); // 读取起点编号// BFS计算满足条件的顶点数int count = bfs(&g, v);// 计算比例并输出，保留两位小数double ratio = (double)count / n * 100;printf("%.2f%%\n", ratio);return 0;
}