【正文】 DFS(int v,int n) //v 控制遞歸 n 為總?cè)藬?shù) { if (v==0)//如果是第一次使用 { for (int k=0。 i++) { if(z[i]yu) { return(i)。j++) z[i]=z[i]+arc[i][j]+arc[j][i]。 for(i=0。 t=temp。} coutendl。 jvertexnum。 } //———————— quanzi 查找交往圈子 ———————— 根據(jù)用戶輸入的一個(gè)人員的數(shù)字代碼，查找該人員的交往圈子，我認(rèn)為與指定人物之間有邊的人物就是與該人物有聯(lián)系的，這些人就構(gòu)成了一個(gè)交往圈子。 i++) { if(z[i]yu) { coutvertex[i] 。 //z[i]存放入度 +出度之和 cout— →邊緣人物是： 。ivertexnum。 9 templateclass T void MgraphT::bianyuan(int n) { vertexnum=n。 count++ 。 int yu=10。i++)//計(jì)算每個(gè)頂點(diǎn)的出度 for( j=0。 int i,j,count=0。 } } if(count==0) {cout無(wú) 。 //找度數(shù)大于域值的人物 , 域 =20 for(i=0。jvertexnum。 int x[maxsize]={0}。 coutendl。i++) { for(j=0。 //邊依附的兩個(gè)頂點(diǎn)的序號(hào) arc[i1][j1]=w。 for (k=0。 ivertexnum。 for (i=0。 //頂點(diǎn)數(shù) arum=e。 CreateHW(a,n,e)。 templateclass T MgraphT::Mgraph(T a[],int n,int e) { visited=new int[vertexnum]。//頂點(diǎn)數(shù)，邊數(shù) void CreateHW(T a[],int n,int e)。 //查找小團(tuán)體函數(shù)（深度優(yōu)先遍歷） void DFS2(int v,int n) 。//邊緣人物成員函數(shù) void quanzi(int v)。//構(gòu)造函數(shù)， a[]結(jié)點(diǎn)數(shù)組， n 頂點(diǎn)個(gè)數(shù)， e 邊數(shù) void PrintGraph()。 include include include const int maxsize=100。 后置條件：無(wú) ? Huoyue（活躍人物） 輸入：無(wú) 前置條件： 有向網(wǎng)已經(jīng) 建立 ，設(shè)定活躍人物的域值 yu=10 功能：找出社會(huì)網(wǎng)絡(luò)的活躍人物 （計(jì)算每個(gè)頂點(diǎn)的出度，找度數(shù)大于域值的人物） 輸出： 若找到則輸出 社會(huì)網(wǎng)絡(luò)的 活躍 人物 ，沒(méi)有找到則輸出“無(wú)”。 4. 能查找任何人的交往圈子。補(bǔ)充 ........................................................................................... 12 ?? 算法的時(shí)間空間復(fù)雜性分析 ......................................................................... 14 ?? 心得體會(huì) ......................................................................................................... 14 六、測(cè)試結(jié)果 .............................................................................................................. 15 七 、附錄：程序設(shè)計(jì)源代碼 ................................................................................... 16 1 一、 設(shè)計(jì)題目 社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn) 二、需求分析 1）運(yùn)行環(huán)境（軟、硬件環(huán)境） 軟件： Microsoft Visual C++ 硬件：能運(yùn)行 Microsoft Visual C++ 的硬件平臺(tái) 如 CPU:Intel 酷睿 i3 3217U；內(nèi)存 4G；操作系統(tǒng) Windows 7 2）輸入的形式和輸入值的范圍 數(shù)據(jù)類型： 整型（ int）、字符型 (char) 范圍： 1. 總?cè)藬?shù)（ 1~100） 2. 人員名稱（ A~Z） 3. 人員數(shù)字代碼（ 1~100） 4. 關(guān)系總數(shù)（ 1~100） 5. 某條關(guān)系（人員數(shù)字代碼 人員數(shù)字代碼 權(quán)值）注：權(quán)值（ 1~100）即 數(shù)據(jù) 舉例：總?cè)藬?shù) 8 個(gè)、人員名稱 ABCDEFGH、人員數(shù)字代碼 1234567關(guān)系總數(shù) 15 條、具體某一條關(guān)系 1 2 9。改進(jìn) amp。 3. 利用子圖概念，分析社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)，找出小團(tuán)體和聯(lián)系小團(tuán)體的橋接人物。 ? CreateHW（ 創(chuàng)建 有向網(wǎng)） 輸入： 圖的人數(shù)和關(guān)系數(shù)、存放圖中人的數(shù)組、存放圖中關(guān)系的數(shù)組 前置條件：構(gòu)造函數(shù)調(diào)用 功能：創(chuàng)建 有向網(wǎng) 3 輸出：無(wú) 后置條件： 有向網(wǎng) 建立 ? PrintGraph（輸出鄰接矩陣） 輸入：無(wú) 前置條件：有向網(wǎng)已經(jīng) 建立 功能：輸出鄰接矩陣 輸出：鄰接矩陣 后置條件：無(wú) ? Centre（核心人物） 輸入：無(wú) 前置條件： 有向網(wǎng)已經(jīng) 建立 ，設(shè)定核心人物的域值 yu=20 功能：找出社會(huì)網(wǎng)絡(luò)的核心人物 （計(jì)算每個(gè)頂點(diǎn)的入度，找度數(shù)大于域值的人物） 輸出： 若找到則輸出 社會(huì)網(wǎng)絡(luò)的核心人物 ，沒(méi)有找到則輸 出“無(wú)”。 輸出： 輸出 指定 人物 的交往圈子 后置條件：無(wú) ? ADD（計(jì)算人員兩兩間的關(guān)系數(shù)） 輸入： 無(wú) 前置條件： 有向網(wǎng)已經(jīng) 建立 ，給出兩個(gè)人物的數(shù)字代碼 功能： 計(jì)算指定人員兩兩間的聯(lián)系數(shù)并返回（為查找小團(tuán)體、橋接人做準(zhǔn)備） 輸出： 返回指定人員兩兩間的聯(lián)系數(shù) 后置條件：無(wú) ? BY（返回邊緣人物數(shù)字代碼） 輸入： 無(wú) 前 置條件： 有向網(wǎng)已經(jīng) 建立 功能： 找邊緣人物并返回該人物數(shù)字代碼（為查找小團(tuán)體、橋接人做準(zhǔn)備） 輸出： 返回邊緣人物的數(shù)字代碼 后置條件：無(wú) ? DFS（小團(tuán)體） 輸入：無(wú) 前置條件： 有向網(wǎng)、 ADD函數(shù)、 BY函數(shù)都已經(jīng) 建立 ，初始化頂點(diǎn)標(biāo)記矩陣（全部置 0） 功能： 查找小團(tuán)體， 從指定的頂點(diǎn)開(kāi)始進(jìn)行深度 優(yōu)先 遍歷 （如果當(dāng)前人物沒(méi)有被訪問(wèn)過(guò)，并且也不是邊緣人物，輸出該人物；再?gòu)脑撊宋镩_(kāi)始 進(jìn)行深度遍歷 ，如果找到與該人物交往密切的人物則輸出，繼續(xù)找下一個(gè)） 輸出：輸出 小團(tuán)體 后置條件：對(duì)訪問(wèn)過(guò)的頂點(diǎn)置 1 ? DFS2（橋接人） 輸入： 無(wú) 前置條件： 有向網(wǎng)、 ADD函數(shù)、 BY 函數(shù)都已經(jīng) 建立 功能： 查找橋接人， 從指定的頂點(diǎn)開(kāi)始進(jìn)行深度 優(yōu)先 遍歷 輸出： 兩個(gè)小團(tuán)體中，有聯(lián)系，但沒(méi)有達(dá)到域值的人物 后置條件：無(wú) end ADT Mgraph 5 2）功能模塊設(shè)計(jì)（如主程序模塊設(shè)計(jì)） 1. 主程序模塊：連接各種功能子模塊，完成程序的基本操作實(shí)現(xiàn)功能 2. 構(gòu)造社會(huì)網(wǎng)絡(luò)模塊：按照要求構(gòu)建有向網(wǎng) 3. 輸出鄰接矩陣模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，輸出該網(wǎng)絡(luò)圖的鄰接矩陣 4. 核心人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的核心人物 5. 活躍人物模 塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的活躍人物 6. 邊緣人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的邊緣人物 7. 交往圈子模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該網(wǎng)絡(luò)中指定人物的交往圈子 8. 人物兩兩聯(lián)系數(shù)模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)， 返回指定人員兩兩間的聯(lián)系數(shù) 9. 判斷邊緣人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)， 返回邊緣人物的數(shù)字代碼 10. 小團(tuán)體模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，深度優(yōu)先遍歷得出該網(wǎng)絡(luò)中的所有小團(tuán)體 11. 橋接人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，深度優(yōu)先遍歷得出小 團(tuán)體間的橋接人物 3）模塊層次調(diào)用關(guān)系圖 橋接人 DFS2 小團(tuán)體 DFS 交往圈子 quanzi 邊緣人物 bianyuan Main( ) Mgraph 活躍人物 huoyue 核心人物 centre 輸出鄰接矩陣PrintGraph 構(gòu)建有向網(wǎng)CreateHW 人員兩兩聯(lián)系數(shù)ADD 判斷邊緣