社会网络分析系统的设计和实现.doc

1、上海电力学院数据结构C+课程设计题目： 社会网络分析系统的设计和实现 学生姓名： 学 号: 院系： 计算机与信息工程学院 专业年级： 信息安全2010级 2012 年6月29 日一、设计题目社会网络分析系统的设计和实现二、需求分析1）运行环境(软、硬件环境）软件:Microsoft Visual C+硬件:Intel(R） Core(TM）2 Duo CPUT6670 2。20 GHz 2。00GB内存2)输入的形式和输入值的范围字符型数据 人数、关系数（0100)3）输出的形式描述1。 该社会网络的邻接矩阵2. 该社会网络中的核心人物、活跃人物、边缘人物3. 该社会网络中的小团体以及桥接人物

2、4。 查找任何人的交往圈子4）功能描述 （1）对email数据进行预处理,利用数据结构课程中图中的理论，建立社会网络的邻接矩阵.(2）利用度的概念,找出社会网络中核心人物、活跃人物和边缘人物.（3)利用子图概念分析社会网络的结构,找出小团体和联系小团体的桥接人物。（4）能查找任何人的交往圈子 5)测试数据52134三、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述,参见书或ppt及实验）ADT Mgraph isData存放图中社会网络人物的数组存放图中社会网络人物的关系的数组图中人物总数和关系总数标记数组OperationMgraph初始化值：图中的

3、人数关系数/存放图中的数组/标志顶点访问的数组动作:选择操作类型，调用图的创建函数。createUG输入：图中的顶点数（图中的人物数），图中的顶点的边（人员之间的相互联系)前置条件:构造函数调用功能：创建无向图输出：无后置条件：无向图建立Centre输入：无前置条件:无向图已经建立功能:找出社会网络的核心人物输出：社会网络的核心人物后置条件:无Huoyue输入：无前置条件：无向图建立功能:找出社会网络的活跃人物输出：社会网络的活跃人物后置条件:无Bianyuan输入：无前置条件：无向图的建立功能：找出社会网络的边缘人物输出:社会网络的边缘人物后置条件：无Pgraph输入:无前置条件：无向图建立

4、功能：输出邻接矩阵输出：输出邻接矩阵后置条件:无DFSTraverse输入：无前置条件：无向图的建立,对标志数组进行初始化为0功能：从指定的顶点开始深度遍历输出:深度遍历序列，找出指定点的交往圈子后置条件：无DFS输入:无前置条件：无向图的建立，重新对数组进行置0处理功能：从指定的顶点开始进行深度遍历输出：输出连通图的序列后置条件:对访问过的顶点置1DFS2输入：无前置条件：无向图的建立，已对访问过的顶点功能：从指定的顶点开始进行深度遍历输出:已标记为1的顶点后置条件：无文档为个人收集整理，来源于网络本文为互联网收集，请勿用作商业用途2）功能模块设计（如主程序模块设计）1. 主程序模块：连接各

5、种功能子模块，完成程序的基本操作实现功能2。 构造社会网络模块：按照要求构建无向图3. 邻接矩阵模块：根据用户输入社会网络，输出该网络图的邻接矩阵4. 核心人物模块：根据用户输入社会网络，计算得出该社会网络中的核心人物5。 活跃人物模块：根据用户输入社会网络，计算得出该社会网络中的活跃人物6。 边缘人物模块:根据用户输入社会网络，计算得出该社会网络中的边缘人物7。 交往圈子模块：根据用户输入社会网络，计算得出该网络中指定人物的交往圈子8. 桥接人物模块：根据用户输入社会网络，通过深度遍历方式得出两个小团体的桥接人物3)模块层次调用关系图Main()Mgraph()createUGDFS2cen

6、trehuoyuebianyuanPgraphDFS四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。/ 主程序模块const int maxsize=100;templateclass T>class Mgraphpublic: Mgraph(T a,int n，int e）;/构造函数,a表示数组，表示顶点的个数,e表示边数 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;/顶点数组int arcmaxsizemaxsize；/边数int vertexnum,arcnum；/定点数，边数void createUG（T a，int n，int e)；int *visited;；/构造函数template<class T>MgraphT：:Mgraph（T a，int n，int e) visited=new intvertexnum； for(int i=0;ivertexnum；i+） visitedi=0；cout<<”该系统创建的图

8、类型为：”<<endl;cout<”-1.无向图-"<endl; createUG（a,n, e)；break;/构建无向图template class T>void MgraphT：createUG(T a,int n,int e）/创建无向图 vertexnum=n； /顶点数 arcnum=e； /边数 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+) /依次输入每一条边，并修改邻接矩阵的相应元素cout<”请输入第”<<k+1<”条关系(格式:顶点1 顶点2）："cin>>ij； /边依附的两个顶点的序号 arci-1j1=1; /置有边标志 arcj-1i-1=1; /该网络的核心人物，活跃人物，边缘人物template<class Tvoid MgraphT>:：centre（int n) vertexnum=n;int i,j；int k=0；int amaxsize=0;for（i=0;ivertexnum；i+）/计算

10、每个顶点的度数for( j=0;j<vertexnum；j+）ai+=arcij； int b=a0；for (i=0; i<vertexnum； i+） if(aib)b=ai;k=i;cout<”该社会网络的核心人物是:"<vertexk<endl；templateclass T>void MgraphT：:huoyue(int n） vertexnum=n；int i,j;int amaxsize=0；for（i=0；i<vertexnum;i+)/计算每个顶点的度数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+）/计算每个顶点的度数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) /深度优先遍历图 cout<”该人员是"ver

13、texv” "endl； cout<"与该人员交往的圈子是：" for （int j=0; jvertexnum； j+） if (arcv-1j=1arcjv1=1) / DFSTraverse（j) cout<<vertexj” ”; /团体查找template class T>void Mgraph<T>:DFS(int v) /深度优先遍历图(无向图)if (v=0)/判断是不是初始使用是的话初始化顶点标记矩阵，代表没有访问过for (int i=0；i<maxsize;i+）visitedi=0;DFS(1)；e

14、lseif （visitedv-1=0）/判断当前结点是否被访问过,没有访问过才继续进行操作visitedv-1=1;/立刻将该结点置为访问过cout<vertexv-1<" "for (int i=v1；ivertexnum；i+）if （arcv1i=1)/判断两个结点之间是否连通，连通则进入其中进行遍历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）；五、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。选择了这个社会网络分析系统的设计和实现这个课题，我觉得这个设计题是比较难的一道题目，在课堂中，老师对于图这一章的算法设计分析只是草草的讲过。经过对题目的分析，我发现这道题目需要掌握图的一些基础算法。首先是无向图的创建，再者就是利用度的概念,通过邻接矩阵的方式找出社会网络中核心人物、活跃人物和边缘人物.求桥接点是通过深度优先遍历找到桥接点。属于两个连通子图的公共点就是两个小团体的桥接

16、点。通过深度遍历即可实现这一功能。最后，就是求小团体了。这个可以通过图的深度优先遍历来完成。通过上课的课件，我将深度优先遍历的算法运用在求小团体中.在程序运行测试过程中，我也遇到了许多的困难,最大的困难就是求桥接点了,我通过许多数据测试结果都不正确。最后我知道了，通过两次深度优先遍历将遍历过的点都置为1,通过两次遍历后，重复为一的点，就是这两个连通图的桥接点。 DFS 算法时间复杂度为O（n2）六 用户使用说明详细列出每一步的操作说明。1。 输入社会网络人数2。 输入社会网络人员名称3。 输入社会网络的关系数4. 依次输入关系5. 输入指定一人的关系代码七、 测试结果八、附录：程序设计源代码#

17、include<iostreamusing namespace std；const int maxsize=100；template<class Tclass Mgraphpublic: Mgraph(T a，int n,int e）;/构造函数，a表示数组，表示顶点的个数，e表示边数 void centre（int n)； /核心人物成员函数 void Pgraph(）；/输出邻接矩阵 void huoyue（int n）；/活跃人物成员函数 void DFSTraverse（int v)； void bianyuan（int n);/边缘人物成员函数 void DFS(int

18、v)； void DFS2(int n）;private:T vertexmaxsize；/顶点数组int arcmaxsizemaxsize；/边数int vertexnum,arcnum;/顶点数，边数void createUG(T a,int n，int e）；/构建无向图int visited;/构造函数template<class TMgraph<T:：Mgraph（T a,int n，int e) visited=new intvertexnum; for(int i=0；i<vertexnum；i+） visitedi=0;cout<"该系统创建

19、的图类型为:”<<endl；cout”-1。无向图-”<endl； createUG(a,n, e);/构建无向图template <class T>void Mgraph<T：:createUG（T a,int n,int e)/创建无向图 vertexnum=n； /顶点数 arcnum=e； /边数 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+) /依次输入每一条边，并修改邻接矩阵的相应元素cout<"请输入第”<k+1<<”条关系(格式：顶点1 顶点2）:”;cin>>i>j; /边依附的两个顶点的序号 arci-1j-1=1； /置有边标志 arcj-1i-1=1; /该网络的核心人物,活跃人物,边缘人物templateclass Tvoid Mgraph<T>:：centre(int n） vertexnum=n；int i,j;int k=0；int amaxsize=0；for(i=0；ivertexnum;i+)/

21、计算每个顶点的度数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<<”该社会网络的核心人物是:”<<vertexkendl;templateclass T>void Mgraph<T>：huoyue(int n) vertexnum=n；int i，j;int amaxsize=0；for(i=0；i<vertexnum；i+）/计算每个顶点的度数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+）/计算每个顶点的度数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、/深度优先遍历图 cout<<”该人员是"<<vertexv<" ”<endl; cout<”与该人员交往的圈子是：" for (int j=0； jvertexnum； j+) if （arcv1j=1arcjv-1=1) coutvertexj<<" ”; /团体查找template class T>void Mgraph<T>:：DFS（int v） /深度优先遍历图(无向图)if （v=0）/判断是不是初始使用是的话初始化顶点标记矩阵，代表没有访问过for (int i=0;i<maxsize；i+）visitedi=0；DFS（1）;elseif （visitedv1=0）/判断当前结点是否被访问过,没有访问过才继续进行操作visitedv1=1；/立刻将该结点置为访问过cout<vertexv1” ”；/输出该节点的值for (int i=v1;i<vertexnum；i+)if （arcv-1i=1）/判断两个结点之间是否连通，连通则进入其中进行遍历DFS(i+1);else；else