【正文】 (m)。 cout請輸入一個人員的數(shù)字代碼（用于查找該人員的交往圈子）：。 (1,n)。 coutendl。 cout—→小團體是：。 (n)。 cout******************社會網絡分析中******************：endl。 cout以下是該社會網絡對應的鄰接矩陣：endl。 cine。i++) {cina[i]。 for(int i=0。 char *a=new char[n]。 //n總人數(shù)，e總關系數(shù)，m某個人員的數(shù)字代碼 cout請輸入該社會網絡總人數(shù)：。 cout ————————————————————————————————endl。}//————————主函數(shù)————————void main(){ cout ————————————————————————————————endl。//輸出橋接人結點的值 DFS2(k+1,n)。amp。amp。amp。kn。 } }}//————————DFS2 查找橋接人————————template class Tvoid MgraphT::DFS2(int v,int n) //v控制遞歸 n為總人數(shù){ int yu=10。 DFS(v+1,n)。k++) { if (ADD(v1,k)yu)//如果兩個結點之間交往 密切 { DFS(k+1,n)。//將該結點置為訪問過！ for (int k=0。 //域值 coutvertex[v1] 。 //初始化頂點標記矩陣（全部置0 代表沒有訪問過） DFS(v+1,n)。kn。 } } if(count==0) return(99)。 i++) { if(z[i]yu) { return(i)。 // 域=5 for (i=0。j++) z[i]=z[i]+arc[i][j]+arc[j][i]。i++)//計算每個頂點的度數(shù) for(j=0。 for(i=0。}//————————BY 查找小團體中用來判斷邊緣人物————————templateclass Tint MgraphT::BY(int n){ int i,j,count=0。 t=temp。 if(st) {temp=s。} coutendl。 count++。 jvertexnum。 cout—→vertex[v1]的交往圈子是:。} coutendl。 count++ 。 ivertexnum。 int yu=5。j++) z[i]=z[i]+arc[i][j]+arc[j][i]。i++)//計算每個頂點的度數(shù) for(j=0。 for(i=0。 int i,j,count=0。} coutendl。 count++ 。 ivertexnum。 int yu=10。j++) y[i]+=arc[i][j]。i++)//計算每個頂點的出度 for( j=0。 for(i=0。 int i,j,count=0。} coutendl。 count++ 。ivertexnum。 int yu=20。j++)//計算每個頂點的入度 x[i]+=arc[j][i]。i++) for(j=0。 for(i=0。 int i,j,count=0。 coutendl。j++) coutarc[i][j]39。i++) { for(j=0。 for(i=0。 //ij邊依附的兩個頂點的序號，w權值 arc[i1][j1]=w。 k++) { //依次輸入每一條邊，并修改鄰接矩陣的相應元素 cout請輸入第k+1條邊:。 for (k=0。 jvertexnum。 ivertexnum。 i++) vertex[i]=a[i]。 for (i=0。 cout 注意！請將人名對應到數(shù)字代碼輸入endl。 //頂點數(shù) arum=e。 //創(chuàng)建}//————————CreateHW 構建有向網————————template class Tvoid MgraphT::CreateHW(T a[],int n,int e){ int w。i++) visited[i]=0。 for(int i=0。}。//頂點數(shù)，邊數(shù) void CreateHW(T a[],int n,int e)。//存放頂點 int arc[maxsize][maxsize]。 //查找小團體函數(shù)（深度優(yōu)先遍歷） void DFS2(int v,int n) 。//計算人員兩兩間聯(lián)系數(shù) int BY(int n) 。//邊緣人物成員函數(shù) void quanzi(int v)。 //核心人物成員函數(shù) void huoyue(int n)。//構造函數(shù)，a[]結點數(shù)組，n頂點個數(shù)，e邊數(shù) void PrintGraph()。const int INFINITY=0。通過這次數(shù)據(jù)結構課程設計，我對之前學習的C++內容更加熟悉了，更好地掌握與理解了模板的使用、二維數(shù)組、參數(shù)傳遞、函數(shù)調用等內容；對數(shù)據(jù)結構這門課程也有了更進一步的學習與掌握，處理問題的思路與方法也有所拓寬，能理解與運用圖的相關知識解決實際問題……在老師的指導下，不僅獨立完成了社會網絡分析系統(tǒng)的設計和實現(xiàn)，還從老師那里學到了很多書上沒有的技巧，比如C++程序調試中所使用“斷點”調試方法，之前我是完全不知道的。之后大量的時間都花在設計小團體和橋接人上了。好在回到寢室后的一整個下午加上一整個晚上的效率很高，終于將實現(xiàn)對數(shù)據(jù)的預處理、建立社會網絡的鄰接矩陣、找出社會網絡中核心人物、活躍人物和邊緣人物的函數(shù)都完成了。圖這一章老師講的沒有單鏈表和二叉樹那樣細致，因為快到期末了課時很緊張，但做相關實驗的時候，我就對圖這部分的內容產生了濃厚的興趣，因為社交網絡和我們的生活比較貼切，圖的應用在類似人人、微信朋友圈的社交網絡中都會用到。 算法的時間空間復雜性分析1. 本設計中算法的時間復雜度分為三類：O(1)——ADD 計算人員間兩兩間聯(lián)系數(shù)O(n)——Mgraph 構造函數(shù)O(n2)——CreateHW 構建有向網、PrintGraph 輸出鄰接矩陣、centre核心人物 、huoyue活躍人物、bianyuan邊緣人物、quanzi查找交往圈子、BY 判斷邊緣人物、DFS 查找小團體、DFS2 查找橋接人2. 本設計中算法的空間復雜度為：O(1)216。一開始也沒有想的這么全面，經過多次測試后發(fā)現(xiàn)這幾種情況也是存在的，原來的程序在這種情況下顯示的是空白，因此加以改進了一下——增加了count計數(shù)器，如果一個人物都沒有的話，就輸出“無”。【改進3】：存放小團體的數(shù)組其實不是必要的之前一直在糾結遞歸調用中存放數(shù)組的問題，但突然7號早上想到另一個更省事兒的方法，用排除法找橋接人！換個角度來看橋接人，就是分屬于兩個小團體，之間有聯(lián)系但是聯(lián)系不密切，另外，橋接人也不能是邊緣人物。 改進原因：按照原來的寫法，輸入兩個人員之間的關系（頂點與頂點之間的邊）要從0開始，由于和日常生活的數(shù)數(shù)習慣不同，因此加以改進，使之從1開始，方便使用。 之后改進為 ：arc[i1][j1]=1。主函數(shù)中，(0,n,team)； (0,n,team,0,0)頭文件中，改成void DFS(int v,int n,char team[20][20],int i,int j)【改進1】：createHW 構建有向網中，原本老師PPT上演示的是：arc[i][j]=1。