社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn).doc

1、上海電力學(xué)院數(shù)據(jù)結(jié)構(gòu)C+課程設(shè)計(jì)題目： 社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn) 學(xué)生姓名： 學(xué) 號(hào): 院系： 計(jì)算機(jī)與信息工程學(xué)院 專(zhuān)業(yè)年級(jí)： 信息安全2010級(jí) 2012 年6月29 日一、設(shè)計(jì)題目社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)二、需求分析1）運(yùn)行環(huán)境(軟、硬件環(huán)境）軟件:Microsoft Visual C+硬件:Intel(R） Core(TM）2 Duo CPUT6670 2。20 GHz 2。00GB內(nèi)存2)輸入的形式和輸入值的范圍字符型數(shù)據(jù) 人數(shù)、關(guān)系數(shù)（0100)3）輸出的形式描述1。 該社會(huì)網(wǎng)絡(luò)的鄰接矩陣2. 該社會(huì)網(wǎng)絡(luò)中的核心人物、活躍人物、邊緣人物3. 該社會(huì)網(wǎng)絡(luò)中的小團(tuán)體以及橋接人物

2、4。 查找任何人的交往圈子4）功能描述 （1）對(duì)email數(shù)據(jù)進(jìn)行預(yù)處理,利用數(shù)據(jù)結(jié)構(gòu)課程中圖中的理論，建立社會(huì)網(wǎng)絡(luò)的鄰接矩陣.(2）利用度的概念,找出社會(huì)網(wǎng)絡(luò)中核心人物、活躍人物和邊緣人物.（3)利用子圖概念分析社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu),找出小團(tuán)體和聯(lián)系小團(tuán)體的橋接人物。（4）能查找任何人的交往圈子 5)測(cè)試數(shù)據(jù)52134三、概要設(shè)計(jì)1）抽象數(shù)據(jù)類(lèi)型定義描述（對(duì)各類(lèi)的成員及成員函數(shù)進(jìn)行抽象描述,參見(jiàn)書(shū)或ppt及實(shí)驗(yàn)）ADT Mgraph isData存放圖中社會(huì)網(wǎng)絡(luò)人物的數(shù)組存放圖中社會(huì)網(wǎng)絡(luò)人物的關(guān)系的數(shù)組圖中人物總數(shù)和關(guān)系總數(shù)標(biāo)記數(shù)組OperationMgraph初始化值：圖中的

3、人數(shù)關(guān)系數(shù)/存放圖中的數(shù)組/標(biāo)志頂點(diǎn)訪(fǎng)問(wèn)的數(shù)組動(dòng)作:選擇操作類(lèi)型，調(diào)用圖的創(chuàng)建函數(shù)。createUG輸入：圖中的頂點(diǎn)數(shù)（圖中的人物數(shù)），圖中的頂點(diǎn)的邊（人員之間的相互聯(lián)系)前置條件:構(gòu)造函數(shù)調(diào)用功能：創(chuàng)建無(wú)向圖輸出：無(wú)后置條件：無(wú)向圖建立Centre輸入：無(wú)前置條件:無(wú)向圖已經(jīng)建立功能:找出社會(huì)網(wǎng)絡(luò)的核心人物輸出：社會(huì)網(wǎng)絡(luò)的核心人物后置條件:無(wú)Huoyue輸入：無(wú)前置條件：無(wú)向圖建立功能:找出社會(huì)網(wǎng)絡(luò)的活躍人物輸出：社會(huì)網(wǎng)絡(luò)的活躍人物后置條件:無(wú)Bianyuan輸入：無(wú)前置條件：無(wú)向圖的建立功能：找出社會(huì)網(wǎng)絡(luò)的邊緣人物輸出:社會(huì)網(wǎng)絡(luò)的邊緣人物后置條件：無(wú)Pgraph輸入:無(wú)前置條件：無(wú)向圖建立

4、功能：輸出鄰接矩陣輸出：輸出鄰接矩陣后置條件:無(wú)DFSTraverse輸入：無(wú)前置條件：無(wú)向圖的建立,對(duì)標(biāo)志數(shù)組進(jìn)行初始化為0功能：從指定的頂點(diǎn)開(kāi)始深度遍歷輸出:深度遍歷序列，找出指定點(diǎn)的交往圈子后置條件：無(wú)DFS輸入:無(wú)前置條件：無(wú)向圖的建立，重新對(duì)數(shù)組進(jìn)行置0處理功能：從指定的頂點(diǎn)開(kāi)始進(jìn)行深度遍歷輸出：輸出連通圖的序列后置條件:對(duì)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)置1DFS2輸入：無(wú)前置條件：無(wú)向圖的建立，已對(duì)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)功能：從指定的頂點(diǎn)開(kāi)始進(jìn)行深度遍歷輸出:已標(biāo)記為1的頂點(diǎn)后置條件：無(wú)文檔為個(gè)人收集整理，來(lái)源于網(wǎng)絡(luò)本文為互聯(lián)網(wǎng)收集，請(qǐng)勿用作商業(yè)用途2）功能模塊設(shè)計(jì)（如主程序模塊設(shè)計(jì)）1. 主程序模塊：連接各

5、種功能子模塊，完成程序的基本操作實(shí)現(xiàn)功能2。 構(gòu)造社會(huì)網(wǎng)絡(luò)模塊：按照要求構(gòu)建無(wú)向圖3. 鄰接矩陣模塊：根據(jù)用戶(hù)輸入社會(huì)網(wǎng)絡(luò)，輸出該網(wǎng)絡(luò)圖的鄰接矩陣4. 核心人物模塊：根據(jù)用戶(hù)輸入社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的核心人物5。 活躍人物模塊：根據(jù)用戶(hù)輸入社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的活躍人物6。 邊緣人物模塊:根據(jù)用戶(hù)輸入社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的邊緣人物7。 交往圈子模塊：根據(jù)用戶(hù)輸入社會(huì)網(wǎng)絡(luò)，計(jì)算得出該網(wǎng)絡(luò)中指定人物的交往圈子8. 橋接人物模塊：根據(jù)用戶(hù)輸入社會(huì)網(wǎng)絡(luò)，通過(guò)深度遍歷方式得出兩個(gè)小團(tuán)體的橋接人物3)模塊層次調(diào)用關(guān)系圖Main()Mgraph()createUGDFS2cen

6、trehuoyuebianyuanPgraphDFS四、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的類(lèi)的定義及類(lèi)中成員函數(shù)，并對(duì)主要的模塊寫(xiě)出偽碼算法。/ 主程序模塊const int maxsize=100;templateclass T>class Mgraphpublic: Mgraph(T a,int n，int e）;/構(gòu)造函數(shù),a表示數(shù)組，表示頂點(diǎn)的個(gè)數(shù),e表示邊數(shù) void centre（int n); void Pgraph();/輸出 void huoyue（int n）; void DFSTraverse（int v); void bianyuan(int n）； void D

7、FS（int v）； void DFS2(int n）；private:T vertexmaxsize;/頂點(diǎn)數(shù)組int arcmaxsizemaxsize；/邊數(shù)int vertexnum,arcnum；/定點(diǎn)數(shù)，邊數(shù)void createUG（T a，int n，int e)；int *visited;；/構(gòu)造函數(shù)template<class T>MgraphT：:Mgraph（T a，int n，int e) visited=new intvertexnum； for(int i=0;ivertexnum；i+） visitedi=0；cout<<”該系統(tǒng)創(chuàng)建的圖

8、類(lèi)型為：”<<endl;cout<”-1.無(wú)向圖-"<endl; createUG（a,n, e)；break;/構(gòu)建無(wú)向圖template class T>void MgraphT：createUG(T a,int n,int e）/創(chuàng)建無(wú)向圖 vertexnum=n； /頂點(diǎn)數(shù) arcnum=e； /邊數(shù) int i,j,k; for （i=0； i<vertexnum； i+） vertexi=ai; for (i=0; i<vertexnum； i+) /初始化鄰接矩陣for (j=0； j<vertexnum; j+）arci

9、j=0; for (k=0； karcnum； k+) /依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素cout<”請(qǐng)輸入第”<<k+1<”條關(guān)系(格式:頂點(diǎn)1 頂點(diǎn)2）："cin>>ij； /邊依附的兩個(gè)頂點(diǎn)的序號(hào) arci-1j1=1; /置有邊標(biāo)志 arcj-1i-1=1; /該網(wǎng)絡(luò)的核心人物，活躍人物，邊緣人物template<class Tvoid MgraphT>:：centre（int n) vertexnum=n;int i,j；int k=0；int amaxsize=0;for（i=0;ivertexnum；i+）/計(jì)算

10、每個(gè)頂點(diǎn)的度數(shù)for( j=0;j<vertexnum；j+）ai+=arcij； int b=a0；for (i=0; i<vertexnum； i+） if(aib)b=ai;k=i;cout<”該社會(huì)網(wǎng)絡(luò)的核心人物是:"<vertexk<endl；templateclass T>void MgraphT：:huoyue(int n） vertexnum=n；int i,j;int amaxsize=0；for（i=0；i<vertexnum;i+)/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for( j=0;jvertexnum；j+）ai+=arcij；co

11、ut"活躍人物是："for(i=0；i<vertexnum;i+）if（aivertexnum/2) cout<vertexi" ”endl；templateclass Tvoid MgraphT：:bianyuan(int n) vertexnum=n;int i，j；int amaxsize=0;for（i=0；i<vertexnum；i+）/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for（ j=0;j<vertexnum;j+）ai+=arcij； cout<<”邊緣人物是："for（i=0;ivertexnum;i+)if(ai&l

12、t;vertexnum/2)cout<<vertexi<<” ”<<endl;；/輸出鄰接矩陣template class Tvoid MgraphT>：Pgraph（)/輸出鄰接矩陣int i，j;for（i=0；ivertexnum;i+）for（j=0;jvertexnum；j+） cout<arcij<ends;cout<<endl；/查找任意人的交往圈子template class Tvoid MgraphT>：:DFSTraverse（int v) /深度優(yōu)先遍歷圖 cout<”該人員是"ver

13、texv” "endl； cout<"與該人員交往的圈子是：" for （int j=0; jvertexnum； j+） if (arcv-1j=1arcjv1=1) / DFSTraverse（j) cout<<vertexj” ”; /團(tuán)體查找template class T>void Mgraph<T>:DFS(int v) /深度優(yōu)先遍歷圖(無(wú)向圖)if (v=0)/判斷是不是初始使用是的話(huà)初始化頂點(diǎn)標(biāo)記矩陣，代表沒(méi)有訪(fǎng)問(wèn)過(guò)for (int i=0；i<maxsize;i+）visitedi=0;DFS(1)；e

14、lseif （visitedv-1=0）/判斷當(dāng)前結(jié)點(diǎn)是否被訪(fǎng)問(wèn)過(guò),沒(méi)有訪(fǎng)問(wèn)過(guò)才繼續(xù)進(jìn)行操作visitedv-1=1;/立刻將該結(jié)點(diǎn)置為訪(fǎng)問(wèn)過(guò)cout<vertexv-1<" "for (int i=v1；ivertexnum；i+）if （arcv1i=1)/判斷兩個(gè)結(jié)點(diǎn)之間是否連通，連通則進(jìn)入其中進(jìn)行遍歷DFS（i+1）;else；else;/templateclass T>void Mgraph<T:：DFS2(int n）visitedn=1；for(int j=0;j<vertexnum;j+） if(visitedj=1）cout&

15、lt;<vertexj<<" ”；if(arcnj=1&visitedj=0）DFS2(j）；五、調(diào)試分析包括調(diào)試過(guò)程中遇到的問(wèn)題及解決的方法、算法的時(shí)間空間復(fù)雜性分析、經(jīng)驗(yàn)體會(huì)。選擇了這個(gè)社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)這個(gè)課題，我覺(jué)得這個(gè)設(shè)計(jì)題是比較難的一道題目，在課堂中，老師對(duì)于圖這一章的算法設(shè)計(jì)分析只是草草的講過(guò)。經(jīng)過(guò)對(duì)題目的分析，我發(fā)現(xiàn)這道題目需要掌握?qǐng)D的一些基礎(chǔ)算法。首先是無(wú)向圖的創(chuàng)建，再者就是利用度的概念,通過(guò)鄰接矩陣的方式找出社會(huì)網(wǎng)絡(luò)中核心人物、活躍人物和邊緣人物.求橋接點(diǎn)是通過(guò)深度優(yōu)先遍歷找到橋接點(diǎn)。屬于兩個(gè)連通子圖的公共點(diǎn)就是兩個(gè)小團(tuán)體的橋接

16、點(diǎn)。通過(guò)深度遍歷即可實(shí)現(xiàn)這一功能。最后，就是求小團(tuán)體了。這個(gè)可以通過(guò)圖的深度優(yōu)先遍歷來(lái)完成。通過(guò)上課的課件，我將深度優(yōu)先遍歷的算法運(yùn)用在求小團(tuán)體中.在程序運(yùn)行測(cè)試過(guò)程中，我也遇到了許多的困難,最大的困難就是求橋接點(diǎn)了,我通過(guò)許多數(shù)據(jù)測(cè)試結(jié)果都不正確。最后我知道了，通過(guò)兩次深度優(yōu)先遍歷將遍歷過(guò)的點(diǎn)都置為1,通過(guò)兩次遍歷后，重復(fù)為一的點(diǎn)，就是這兩個(gè)連通圖的橋接點(diǎn)。 DFS 算法時(shí)間復(fù)雜度為O（n2）六 用戶(hù)使用說(shuō)明詳細(xì)列出每一步的操作說(shuō)明。1。 輸入社會(huì)網(wǎng)絡(luò)人數(shù)2。 輸入社會(huì)網(wǎng)絡(luò)人員名稱(chēng)3。 輸入社會(huì)網(wǎng)絡(luò)的關(guān)系數(shù)4. 依次輸入關(guān)系5. 輸入指定一人的關(guān)系代碼七、 測(cè)試結(jié)果八、附錄：程序設(shè)計(jì)源代碼#

17、include<iostreamusing namespace std；const int maxsize=100；template<class Tclass Mgraphpublic: Mgraph(T a，int n,int e）;/構(gòu)造函數(shù)，a表示數(shù)組，表示頂點(diǎn)的個(gè)數(shù)，e表示邊數(shù) void centre（int n)； /核心人物成員函數(shù) void Pgraph(）；/輸出鄰接矩陣 void huoyue（int n）；/活躍人物成員函數(shù) void DFSTraverse（int v)； void bianyuan（int n);/邊緣人物成員函數(shù) void DFS(int

18、v)； void DFS2(int n）;private:T vertexmaxsize；/頂點(diǎn)數(shù)組int arcmaxsizemaxsize；/邊數(shù)int vertexnum,arcnum;/頂點(diǎn)數(shù)，邊數(shù)void createUG(T a,int n，int e）；/構(gòu)建無(wú)向圖int visited;/構(gòu)造函數(shù)template<class TMgraph<T:：Mgraph（T a,int n，int e) visited=new intvertexnum; for(int i=0；i<vertexnum；i+） visitedi=0;cout<"該系統(tǒng)創(chuàng)建

19、的圖類(lèi)型為:”<<endl；cout”-1。無(wú)向圖-”<endl； createUG(a,n, e);/構(gòu)建無(wú)向圖template <class T>void Mgraph<T：:createUG（T a,int n,int e)/創(chuàng)建無(wú)向圖 vertexnum=n； /頂點(diǎn)數(shù) arcnum=e； /邊數(shù) int i，j,k； for (i=0； i<vertexnum; i+） vertexi=ai； for （i=0; i<vertexnum； i+） /初始化鄰接矩陣for （j=0； j<vertexnum； j+）arcij=0；

20、 for (k=0; karcnum； k+) /依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素cout<"請(qǐng)輸入第”<k+1<<”條關(guān)系(格式：頂點(diǎn)1 頂點(diǎn)2）:”;cin>>i>j; /邊依附的兩個(gè)頂點(diǎn)的序號(hào) arci-1j-1=1； /置有邊標(biāo)志 arcj-1i-1=1; /該網(wǎng)絡(luò)的核心人物,活躍人物,邊緣人物templateclass Tvoid Mgraph<T>:：centre(int n） vertexnum=n；int i,j;int k=0；int amaxsize=0；for(i=0；ivertexnum;i+)/

21、計(jì)算每個(gè)頂點(diǎn)的度數(shù)for（ j=0；j<vertexnum;j+）ai+=arcij； int b=a0；for (i=0； i<vertexnum; i+) if(ai>b)b=ai;k=i；cout<<”該社會(huì)網(wǎng)絡(luò)的核心人物是:”<<vertexkendl;templateclass T>void Mgraph<T>：huoyue(int n) vertexnum=n；int i，j;int amaxsize=0；for(i=0；i<vertexnum；i+）/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for（ j=0;j<vertexnum

22、；j+）ai+=arcij;cout<<"活躍人物是：”；for（i=0；ivertexnum;i+)if（aivertexnum/2) coutvertexi<” "<endl；templateclass T>void Mgraph<T>：:bianyuan(int n) vertexnum=n；int i，j;int amaxsize=0；for（i=0；ivertexnum；i+）/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for（ j=0;jvertexnum;j+)ai+=arcij; cout<<"邊緣人物是："

23、for（i=0;i<vertexnum;i+)if(ai<vertexnum/2）cout<<vertexi<<" "<endl；template class Tvoid Mgraph<T>：Pgraph()/輸出鄰接矩陣int i,j；for(i=0；ivertexnum;i+)for（j=0;jvertexnum;j+) cout<arcijends;cout<<endl;/查找任意人的交往圈子template class Tvoid MgraphT>:：DFSTraverse(int v）

24、/深度優(yōu)先遍歷圖 cout<<”該人員是"<<vertexv<" ”<endl; cout<”與該人員交往的圈子是：" for (int j=0； jvertexnum； j+) if （arcv1j=1arcjv-1=1) coutvertexj<<" ”; /團(tuán)體查找template class T>void Mgraph<T>:：DFS（int v） /深度優(yōu)先遍歷圖(無(wú)向圖)if （v=0）/判斷是不是初始使用是的話(huà)初始化頂點(diǎn)標(biāo)記矩陣，代表沒(méi)有訪(fǎng)問(wèn)過(guò)for (int i=0;i<maxsize；i+）visitedi=0；DFS（1）;elseif （visitedv1=0）/判斷當(dāng)前結(jié)點(diǎn)是否被訪(fǎng)問(wèn)過(guò),沒(méi)有訪(fǎng)問(wèn)過(guò)才繼續(xù)進(jìn)行操作visitedv1=1；/立刻將該結(jié)點(diǎn)置為訪(fǎng)問(wèn)過(guò)cout<vertexv1” ”；/輸出該節(jié)點(diǎn)的值for (int i=v1;i<vertexnum；i+)if （arcv-1i=1）/判斷兩個(gè)結(jié)點(diǎn)之間是否連通，連通則進(jìn)入其中進(jìn)行遍歷DFS(i+1);else；else