“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:
输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤10
,表示人数)、边数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%
考察图的遍历
边数 M 最大是顶点数 N 的 33 倍,很容易成为"稀疏图",为了节省空间,采用邻接表方式存储,用数组存每个顶点的头指针,且头指针的值为自己的下标,作为邻接表
BFS 适合统计步数,选用 BFS 对图遍历
为了节省空间,统计步数采用三个变量:
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<queue> #define MaxVertex 10005 typedef int vertex; typedef struct Node *AdjList; struct Node{ vertex Adjv; // 当前下标 AdjList Next; // 下一个 }; AdjList G[MaxVertex]; bool visit[MaxVertex]; // 是否访问 int N; // 结点数 int M; // 边数 using namespace std; // 初始化访问状态 void InitVisit(){ for(int i=1;i<=N;i++) visit[i] = false; } // 初始化 void Init(){ vertex v1,v2; AdjList NewNode; cin>>N>>M; // 初始化点,从 1—N for(int i=1;i<=N;i++){ G[i] = (AdjList)malloc(sizeof(struct Node)); G[i]->Adjv = i; G[i]->Next = NULL; } // 初始化边 for(int i=0;i<M;i++){ cin>>v1>>v2; NewNode = (AdjList)malloc(sizeof(struct Node)); NewNode->Adjv = v2; NewNode->Next = G[v1]->Next; G[v1]->Next = NewNode; NewNode = (AdjList)malloc(sizeof(struct Node)); NewNode->Adjv = v1; NewNode->Next = G[v2]->Next; G[v2]->Next = NewNode; } } int BFS(vertex v){ queue<vertex> q; vertex tmp; int level = 0; int last = v; // 该层最后一次访问的结点 int tail = v; // 每次在变的结点 AdjList node; visit[v] = true; int count = 1; // 统计关系数 q.push(v); while(!q.empty()){ tmp = q.front(); q.pop(); // G[i]第一个结点存自己的下标 node = G[tmp]->Next; while(node){ if(!visit[node->Adjv]){ visit[node->Adjv] = true; q.push(node->Adjv); count++; tail = node->Adjv; // 每次更新该结点 } node = node->Next; } // 如果该当前结点是这层最后一个结点 if(tmp == last){ level++; // 层数 +1 last = tail; // 更改 last } // 层数够了结束 if(level==6) break; } return count; } void output(double result,int i){ printf("%d: %.2f%%\n",i,result); } void SDS(){ int count; for(int i=1;i<=N;i++){ // 每次初始化访问数组 InitVisit(); count = BFS(i); output((100.0*count)/N,i); } } int main(){ Init(); SDS(); return 0; }