7-7 六度空間 (30 分)

一：題目：

六度空間”理論又稱作“六度分隔（Six Degrees of Separation）”理論。這個理論可以通俗地闡述為：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個人你就能夠認識任何一個陌生人。”如圖1所示。

圖1 六度空間示意圖
“六度空間”理論雖然得到廣泛的認同，并且正在得到越來越多的應用。但是數十年來，試圖驗證這個理論始終是許多社會學家努力追求的目標。然而由于歷史的原因，這樣的研究具有太大的局限性和困難。隨著當代人的聯絡主要依賴于電話、短信、微信以及因特網上即時通信等工具，能夠體現社交網絡關系的一手數據已經逐漸使得“六度空間”理論的驗證成為可能。

假如給你一個社交網絡圖，請你對每個節點計算符合“六度空間”理論的結點占結點總數的百分比。

輸入格式:
輸入第1行給出兩個正整數，分別表示社交網絡圖的結點數N（1<N≤10
?3
?? ，表示人數）、邊數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%

二：思路解析：

用BFS遍歷點時其實也就是，層序遍歷 ，這里的deep是記錄層數的 由題目得知 最大層數不得超過六層 ，而在設計層數時 是將每次入隊的鄰接點全部出隊 代表一層遍歷結束，然后記錄鄰接點的個數 即是可以到達目標結點的結點個數

三：上碼（鄰接矩陣存儲數據）

//不用考慮與目標點的距離小于6的多條路徑問題，因為已經記錄下 這個結點了。當大于6時 也就是當遞歸結束時 將 返回 上一個結點 訪問其未訪問過的 記錄 //路徑權值相加 小于 6 的結點個數 同時 也就是 到達目標結點路徑長度小于六的 的結點 總數； // dfs 當中的遞歸次數 也就是 到達目標結點的路徑長度 小于六的結點次數； #include<bits/stdc++.h> using namespace std;//int visited[1001] = {0}; int N,M; int cnt; typedef struct GNode* Ptrgraph; typedef struct GNode{int Nv;int Ne;int Data[10001][10001]; }gnode;//創建圖(用臨界矩陣來表示) void CreateGraph( Ptrgraph G) {cin >> N >> M;G->Nv = N;G->Ne = M;for(int i = 1; i <= G->Nv; i++){for(int j = 1; j <= G->Nv; j++){G->Data[i][j] = 0;}}for( int k = 0; k < G->Ne; k++){int i,j;cin >> i >> j;G->Data[i][j] = 1;G->Data[j][i] = 1;} }//BFS遍歷 void BFS_Graph(Ptrgraph G,int a,int visited[]){int Queue[1001];int head = 0,last = 0;Queue[last++] = a;visited[a] = 1;cnt++;for(int deep = 0; deep < 6; deep++) //deep表示層數 {vector<int>v; while(head - last) //將每次入隊的元素全部出隊 也就是代表這一層的鄰接點訪問完了；準備從 { //的deep = 0 向deep++靠近 int temp = Queue[head++];v.push_back(temp); }for(int i = 0; i < v.size(); i++){ int temp2 = v[i]; for(int i = 1; i <= G->Nv; i++){ if( visited[i] != 1 && G->Data[temp2][i] == 1){ Queue[last++] = i;cnt++;// 統計每個可以到達 目標結點的鄰接點個數 visited[i] = 1;} } } } } int main(){Ptrgraph G;G = (Ptrgraph)malloc(sizeof(struct GNode));CreateGraph(G);for(int i = 1; i <= N; i++ ){ int visited[1001] = {0};cnt = 0;BFS_Graph(G,i,visited);double temp3 = (double)cnt * 100.00/ N;printf("%d: %0.2f%%\n",i,temp3);}}

四：DFS遍歷（最后一個點過不去）

自己做的時候先用的是DFS遍歷，也就是一個遞歸， 在形參上添加了一個記錄路徑長度的sum ,在設置遞歸失敗條件上選擇 sum<6; 說的是容易 但自己在用遞歸的時候 不知走了多少彎路，尤其在設置遞歸失敗條件上 ，而且遞歸及其難理解，本題當中的因為當遍歷到鄰接點都被訪問過了便就返回上一層 ，所以要將所記錄的路徑長度 也要對應返回，因此要將sum設置在形參上，這樣便可以將路徑長度也返回。還有一個點，因為是要輸出多個點，所以初始化的時候要將visited這個數組放到for循環里頭。用DFS過不去原因我是從網上看的，講的是因為當遍歷的最后一個點返回到初始點時 ，還有一條可以直達最后一個點的路徑，但因為已經標記過了，所以便不在訪問（我不懂 大家可以再看看 可以打評論，即便這道題沒過，但我又對遞歸又有了更深的認識，重要的是自己學習的過程，加油陌生人。

//不用考慮與目標點的距離小于6的多條路徑問題，因為已經記錄下 這個結點了。當大于6時 也就是當遞歸結束時 將 返回 上一個結點 訪問其未訪問過的 記錄 //路徑權值相加 小于 6 的結點個數 同時 也就是 到達目標結點路徑長度小于六的 的結點 總數； // dfs 當中的遞歸次數 也就是 到達目標結點的路徑長度 小于六的結點次數； #include<bits/stdc++.h> using namespace std;//int visited[1001] = {0}; int N,M; int cnt; typedef struct GNode* Ptrgraph; typedef struct GNode{int Nv;int Ne;int Data[10001][10001]; }gnode;//創建圖(用臨界矩陣來表示) void CreateGraph( Ptrgraph G){cin >> N >> M;G->Nv = N;G->Ne = M;for(int i = 1; i <= G->Nv; i++){for(int j = 1; j <= G->Nv; j++){G->Data[i][j] = 0;}}for( int k = 0; k < G->Ne; k++){int i,j;cin >> i >> j;G->Data[i][j] = 1;G->Data[j][i] = 1;} }//DFS遍歷 // 遇到遞歸失敗條件后 依次返回到 上一層 對應的 a 和sum2; void DFS_Graph(Ptrgraph G,int a,int sum2,int visited[]){ // sum2表示路徑長度 if(sum2 > 6){return ;}cnt++;//每一次遞歸就是一個可以到達目標結點的距離小于6的結點；visited[a] = 1;for(int j = 1 ; j <= G->Nv; j++){if( visited[j] != 1 && G->Data[a][j] != 0){//sum2 += G->Data[a][j]; //記錄路徑長度小于6的//cout << sum2 << endl;DFS_Graph( G,j,sum2+1,visited); }}} int main(){Ptrgraph G;G = (Ptrgraph)malloc(sizeof(struct GNode));CreateGraph(G);for(int i = 1; i <= N; i++){int visited[10001] = {0};cnt = 0;int sum1 =0;//表示路徑長度DFS_Graph(G,i,sum1,visited);//cout << "-----"<<endl;// cout << ::count << endl;double temp = (double)cnt*100.00 / N;printf("%d: %0.2f%%\n",i,temp);//visited[10001] = {0};}}

總結

以上是生活随笔為你收集整理的7-7 六度空间 (30 分)(BFS遍历详解)（DFS最后一个点过不去）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。