C语言六度空间理论代码,要求:“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。 输入格式: 多组数据,每组数据m+1行。第一行有两个数字n和m,代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b,代表这两个人互相认识。当n和m都等于0时,输入结束。 输出格式: 每组数据输出n行,对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
时间: 2024-02-17 15:02:41 浏览: 86
这里提供一份 C 语言的六度空间理论代码,希望能对您有所帮助:
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAXN 1000 // 最大结点数
int n, m, ans[MAXN+1], g[MAXN+1][MAXN+1];
// ans数组用于记录每个结点距离不超过6的结点数
// g数组用于存储图的邻接矩阵表示
void dfs(int u, int d) {
if (d > 6) return; // 超过六度空间,退出
for (int v = 1; v <= n; v++) {
if (g[u][v] == 1 && ans[v] == -1) { // 如果v与u相连且未被访问
ans[v] = 1; // 标记为已访问
dfs(v, d+1); // 继续向下搜索
}
}
}
int main() {
while (scanf("%d %d", &n, &m) == 2 && n != 0) {
memset(g, 0, sizeof(g));
memset(ans, -1, sizeof(ans)); // 初始化
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g[u][v] = g[v][u] = 1; // 建立双向边
}
for (int i = 1; i <= n; i++) {
ans[i] = 0; // 初始化为0
dfs(i, 0); // 从结点i开始搜索
for (int j = 1; j <= n; j++) {
if (ans[j] != -1) ans[i]++; // 统计距离不超过6的结点数
}
ans[i] = ans[i] * 100 / n; // 计算百分比
}
for (int i = 1; i <= n; i++) {
printf("%d: %d%%\n", i, ans[i]);
}
}
return 0;
}
```
注意:这份代码使用了邻接矩阵来表示图,如果数据较大,可能会导致空间不足。此时可以考虑使用邻接表或者其他数据结构来存储图。同时,如果数据较大,可能会导致程序运行时间较长,需要优化算法或者使用并行计算来提高效率。
阅读全文