【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;
    // 初始化邻接矩阵所有元素为0
    for (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;   // 层数加1
                enqueue(&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;
}