“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:
输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤103,表示人数)、边数M(≤33×N,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。
输出格式:
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
输入样例:
10 9 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
讯享网
输出样例:
讯享网1: 70.00% 2: 80.00% 3: 90.00% 4: 100.00% 5: 100.00% 6: 100.00% 7: 100.00% 8: 90.00% 9: 80.00% 10: 70.00%
代码
#include <stdio.h> #include <malloc.h> #define MAX 1001 int count(int num, int N, int relation) { //对第num个人进行六度空间内有关联的人的计数 int queue[MAX]; // queue数组模拟一个队列,记录需要遍历其关系的人(需要遍历第num个人认识的人) int front = -1, rear = -1; // front和rear模拟头尾指针,分别是queue的队列头和尾。 int sum = 1; //记录所有在六度内认识的人。 int level = 0; //记录当前的层数,便于按层遍历,当层数为6时,退出 int levellast = num; //记录每一层最后的一个人的编号,当遍历到这个编号时,层数加1. int visit[MAX] = {0}; //记录对每个人是否已经访问过的情况,防止出现重复遍历,初始状态为全都没有遍历 int last; visit[num] = 1; queue[++rear] = num; //参数num为queue第一个元素,是第一个需要遍历其关系的人 while (front < rear) { //对待遍历队列进行遍历 int t = queue[++front]; // t为第一个需要遍历其关系的人 for (int i = 1; i <= N; i++) { //开始遍历该人的关系(即数组的第二维) if (!visit[i] && relation[t][i] == 1) { //如果第num个人和第i个人有关系且i尚未访问 queue[++rear] = i; //将该第i个人记录进入待访问数组,在下层进行访问 visit[i] = 1; //将该点记录已经访问 sum += 1; //认识的总人数加1 last = i; //记录下当层的最后一个结点 } } if (t == levellast) { //如果已经到了一层的最后一个结点 level += 1; //层数加1 levellast = last; } if (level == 6) break; } return sum; //返回总人数 } int main(void) { int num1, num2; //人数,关系数 scanf("%d", &num1); //输入人数 scanf("%d", &num2); //输入关系数 int relation; //二维数组,记录两个人之间的关系矩阵 relation = (int )malloc(sizeof(int *) * (num1 + 1)); //分配空间 for (int i = 0; i <= num1; i++) { //分配空间 *(relation + i) = (int *)malloc(sizeof(int) * (num1 + 1)); } for (int i = 0; i <= num2 - 1; i++) { //记录一个关系的两端的结点 int x, y; //记录一个关系的两端的结点 scanf("%d", &x); scanf("%d", &y); relation[x][y] = relation[y][x] = 1; //无向图的关系矩阵一定是对称的 } //关系录入完成 for (int i = 1; i <= num1; i++) { //循环输出每个人的六度内的认识的人的比 printf("%d: %.2f%%\n", i, ((float)count(i, num1, relation) / num1) * 100); } }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82813.html