【文章內(nèi)容簡介】 texnum。i++)//計算每個頂點的出度 for( j=0。jvertexnum。j++) y[i]+=arc[i][j]。//y[i]存放出度數(shù) cout— →活躍人物是： 。 int yu=10。 //找度數(shù)大于域值的人物 , 域 =10 for (i=0。 ivertexnum。 i++) { if(y[i]yu) { coutvertex[i] 。 count++ 。 } } if(count==0) {cout無 。} coutendl。 } //———————— bianyuan 邊緣人物 ———————— 若人物收到 和發(fā)出的 Email 總數(shù)小于 5 封，我認(rèn)為就是邊緣人物，所以我設(shè)置了域為 5， bianyuan 函數(shù)要完成的功能是找入度與出度之和小于域值的人物，并輸出。 9 templateclass T void MgraphT::bianyuan(int n) { vertexnum=n。 int i,j,count=0。 int z[maxsize]={0}。 for(i=0。ivertexnum。i++)//計算每個頂點的度數(shù) for(j=0。jvertexnum。j++) z[i]=z[i]+arc[i][j]+arc[j][i]。 //z[i]存放入度 +出度之和 cout— →邊緣人物是： 。 int yu=5。 //找度數(shù)小于域值的人物 , 域 =5 for (i=0。 ivertexnum。 i++) { if(z[i]yu) { coutvertex[i] 。 count++ 。 } } if(count==0) {cout無 。} coutendl。 } //———————— quanzi 查找交往圈子 ———————— 根據(jù)用戶輸入的一個人員的數(shù)字代碼，查找該人員的交往圈子，我認(rèn)為與指定人物之間有邊的人物就是與該人物有聯(lián)系的，這些人就構(gòu)成了一個交往圈子。 template class T void MgraphT::quanzi(int v) { int count=0。 cout— → vertex[v1]的交往圈子是 :。 for (int j=0。 jvertexnum。 j++) { if (arc[v1][j]!=INFINITY||arc[j][v1]!=INFINITY) //交往圈子：與指定人物之間有邊就算 { coutvertex[j] 。 count++。 } } if(count==0) {cout無 。} coutendl。 } //—————— ADD 計算人員間兩兩間聯(lián)系數(shù) ———————— 計算指定人員兩兩間的聯(lián)系數(shù)并返回（為查找小團體、橋接人做準(zhǔn)備） template class T int MgraphT::ADD(int s,int t) { int temp。 if(st) { temp=s。 s=t。 t=temp。 } 10 else return (arc[s][t]+arc[t][s])。 } //————— BY 查找小團體中用來判斷邊緣人物 —————— 找邊緣人物并返回該人物數(shù)字代碼（為查找小團體、橋接人做準(zhǔn)備） templateclass T int MgraphT::BY(int n) { int i,j,count=0。 int z[maxsize]={0}。 for(i=0。in。i++)//計算每個頂點的度數(shù) for(j=0。jn。j++) z[i]=z[i]+arc[i][j]+arc[j][i]。 //z[i]存放入度 +出度之和 int yu=5。 // 域 =5 for (i=0。 in。 i++) { if(z[i]yu) { return(i)。 count++ 。 } } if(count==0) return(99)。 } //———————— DFS 查找小團體 ———————— 查找小團體，從指定的頂點（我設(shè)置的是 0 也就是第一個人）開 始進(jìn)行深度優(yōu)先遍歷（如果當(dāng)前人物 A 沒有被訪問過，并且也不是邊緣人物，輸出該人物 A；再從該人物 A 開始進(jìn)行深度遍歷，如果找到與該人物交往密切的人物 B 則輸出，再從 B 開始繼續(xù)找下一個），并且在查找過程中輸出小團體成員。 template class T void MgraphT::DFS(int v,int n) //v 控制遞歸 n 為總?cè)藬?shù) { if (v==0)//如果是第一次使用 { for (int k=0。kn。k++) visited[k]=0。 //初始化頂點標(biāo)記矩 陣（全部置 0 代表沒有訪問過） DFS(v+1,n)。 //利用遞歸算法重復(fù)調(diào)用深度優(yōu)先遍歷 DFS } else { if (visited[v1]==0)//如果當(dāng)前人物沒有被訪問過 { if(v1!=BY(n))//并且也不是邊緣人物 { int yu=10。 //域值 11 coutvertex[v1] 。//輸出該結(jié)點的值 visited[v1]=1。//將該結(jié)點置為訪問過！ for (int k=0。kn。k++) { if (ADD(v1,k)yu)//如果兩個結(jié)點之間交往 密切 { DFS(k+1,n)。 }//找下一個 } cout,。 DFS(v+1,n)。 } else DFS(v+1,n)。 } } } //———————— DFS2 查找橋接人 ———————— 查找橋接人，兩個小團體中，有聯(lián)系，但沒有達(dá)到域值的人物。從指定的頂點開始進(jìn)行深度優(yōu)先遍歷 template class T void MgraphT::DFS2(int v,int n) //v 控制遞歸 n 為總?cè)藬?shù) { int yu=10。 //域值 for (int k=v1。kn。k++) { if (ADD(v1,k)0 amp。amp。 ADD(v1,k)yu amp。amp。 v1!=BY(n)amp。amp。 k!=BY(n))//如果兩個結(jié)點之間有邊但交往不密切，并且分別屬于兩個小團體 { coutvertex[v1] vertex[k] 。//輸出橋接人結(jié)點的值 DFS2(k+1,n)。 //找下一個 } } if (v=n) DFS2(v+1,n)。 } //———————— 主函數(shù) ———————— 測試剛剛的 Mgraph 類中的各種成員函數(shù)是否編寫正確，完成要求的功能。 void main() { cout| 歡迎使用社會網(wǎng)絡(luò)分析系統(tǒng) |endl。 int n,e,m。 //n 總?cè)藬?shù)， e 總關(guān)系數(shù)， m 某個人員的數(shù)字代碼 cout請輸入該社會網(wǎng)絡(luò)總?cè)藬?shù)： 。 cinn。 12 char *a=new char[n]。 //a 是指針， a 的值是新建數(shù)組的首地址， a[0],a[1]等 cout請依次輸入人員名稱： 。 for(int i=0。in。i++) {cina[i]。} cout請輸入該社會網(wǎng)絡(luò)的關(guān)系總數(shù)： 。 cine。 Mgraphchar G(a,n,e)。 cout以下是該社會網(wǎng)絡(luò)對應(yīng)的鄰接矩陣： endl。 ()。 cout******************社會網(wǎng)絡(luò)分析中 ******************： endl。 (n)。 (n)。 (n)。 cout— →小團體是： 。 (0,n)。 coutendl。 cout— →聯(lián)系小團體的橋接人物是： 。 (1,n)。 coutendl。 cout請輸入一個人員的數(shù)字代碼（用于查找該人員的交往圈子）： 。 cinm。 (m)。 } 五、調(diào)試分析 （包括調(diào)試過程中遇到的問題及解決的方法、算法的時間空間復(fù)雜性分析、經(jīng)驗體會） ? 問題 amp。改進(jìn) amp。補充： 【問題 1】：小團體和橋接人的理解與定義 小團體：小團體就是由交往比較密切的一群人構(gòu)成的，因此要設(shè)一個域值， 數(shù)據(jù)（權(quán)值）超過這個域值才能算交往密切；一個人不能單獨構(gòu)成一個小團體，小團體至少要 2 個成員組成。 橋接人：橋接人就是聯(lián)系兩個小團體的中間人，也就是說一個小團體可以通過對應(yīng)的橋接人和另外一個小團體取得聯(lián)系，橋接人分屬于兩個不同的團體。 【問題 2】：參數(shù)傳遞問題 目的是 在一個成員函數(shù)里調(diào)用另一個成員