7-2 六度空間(30 分)
“六度空間”理論又稱作“六度分隔(Six Degrees of Separation)”理論。這個理論可以通俗地闡述為：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個人你就能夠認識任何一個陌生人。”如圖1所示。
圖1 六度空間示意圖
“六度空間”理論雖然得到廣泛的認同，并且正在得到越來越多的應用。但是數十年來，試圖驗證這個理論始終是許多社會學家努力追求的目标。然而由于曆史的原因，這樣的研究具有太大的局限性和困難。随着當代人的聯絡主要依賴于電話、短信、微信以及網際網路上即時通信等工具，能夠展現社交網絡關系的一手資料已經逐漸使得“六度空間”理論的驗證成為可能。
假如給你一個社交網絡圖，請你對每個節點計算符合“六度空間”理論的結點占結點總數的百分比。
輸入格式:
輸入第1行給出兩個正整數，分别表示社交網絡圖的結點數N(1
輸出格式:
對每個結點輸出與該結點距離不超過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
#include
#define MAX 10001//最大頂點數
int BFS(int i, int N, int ** snap)
{// 隊列 周遊登記 隊頭 隊尾 計數器 層數
int q[MAX], visit[MAX], front, rear, count, level, last, tail, v, j;
for (j = 0; j < 10001; j++)//初始化數組
visit[j] = 0;
visit[i] = 1;//開始結點
front = rear = -1;//隊列初始化
count = 1;//計算六度空間的個數
level = 0;//level計算層數，等于6時跳出
last = i;//last為上一層最後的頂點
q[++rear] = i;//入隊 目前頂點所在層數
while (front
{
v = q[++front]; //出隊
for (j = 1; j <= N; j++)//周遊
if (!visit[j] && snap[v][j] == 1)
{//當結點沒有記錄而且此處結點為頂點時
q[++rear] = j;//入隊列
visit[j] = 1;//記錄對應位置
count++;//計數器
tail = j;//tail是目前層的最後一個頂點
}
if (v == last)
{
level++;//層數加一
last = tail;//記錄最後一個頂點
}
if (6 == level)//等于六層時，退出循環
break;
}
return count;//傳回六度空間内所有頂點數
}
int main(void)
{
int N, M;
int count = 0;
scanf("%d %d", &N, &M);
int **snap;//實作動态配置設定二維數組
snap = (int**)malloc(sizeof(int*) * (N + 1));
if (snap == NULL)
return -1;
//動态配置設定記憶體存在失敗的可能，是以
//在進行動态配置設定記憶體後
//應該進行對應的指針是否為空指針的判斷
int i, x, y, j;
for (i = 0; i <= N; i++)
{
*(snap + i) = (int *)malloc(sizeof(int) * (N + 1));
if (*(snap + i) == NULL)
return -1;
}
for (i = 0; i < M; i++)
{
scanf("%d %d", &x, &y);//無向圖對角線對稱
snap[x][y] = snap[y][x] = 1;//關系對等
}
for (i = 1; i <= N; i++)
{
count = BFS(i, N, snap);
printf("%d: %.2f%%\n", i, (float)count / N * 100);
}
//直接進行頭指針的記憶體釋放不全等于所有指針記憶體的釋放
//free(snap);
for (i = 0; i < N; i++)
{
free(*(snap + i));
*(snap + i) = NULL;
}
free(snap);
snap = NULL;
return 0;
}