社会网络分析系统的设计和实现
上海电力学院数据结构 C+课程设计题 目: 社会网络分析系统的设计和实现 学生姓名： 学 号： 院 系： 计算机与信息工程学院 专业年级： 信息安全 2010 级 2012 年 6 月 29 日一、设计题目一、设计题目社会网络分析系统的设计和实现二、需求分析二、需求分析1 1）运行环境（软、硬件环境）运行环境（软、硬件环境）软件：Microsoft Visual C+硬件：Intel(R) Core(TM)2 Duo CPUT6670 2.20 GHz 2.00GB 内存2 2）输入的形式和输入值的范围）输入的形式和输入值的范围字符型数据 人数、关系数（0100）3 3）输出的形式描述）输出的形式描述1. 该社会网络的邻接矩阵2. 该社会网络中的核心人物、活跃人物、边缘人物3. 该社会网络中的小团体以及桥接人物4. 查找任何人的交往圈子4 4）功能描述）功能描述 （1）对 email 数据进行预处理,利用数据结构课程中图中的理论，建立社会网络的邻接矩阵。（2）利用度的概念,找出社会网络中核心人物、活跃人物和边缘人物。（3）利用子图概念分析社会网络的结构，找出小团体和联系小团体的桥接人物。（4）能查找任何人的交往圈子5 5）测试数据）测试数据1 12 23 34 45 5三、概要设计三、概要设计1 1）抽象数据类型定义描述）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或 ppt 及实验）ADT Mgraph isData存放图中社会网络人物的数组存放图中社会网络人物的关系的数组图中人物总数和关系总数标记数组OperationMgraph初始化值：图中的人数关系数/存放图中的数组/标志顶点访问的数组动作：选择操作类型，调用图的创建函数。createUG输入：图中的顶点数（图中的人物数），图中的顶点的边（人员之间的相互联系）前置条件：构造函数调用功能：创建无向图输出：无后置条件：无向图建立Centre输入：无前置条件：无向图已经建立功能：找出社会网络的核心人物输出：社会网络的核心人物后置条件：无Huoyue输入：无前置条件：无向图建立功能：找出社会网络的活跃人物输出：社会网络的活跃人物后置条件：无Bianyuan输入：无前置条件：无向图的建立功能：找出社会网络的边缘人物输出：社会网络的边缘人物后置条件：无Pgraph输入：无前置条件：无向图建立功能：输出邻接矩阵输出：输出邻接矩阵后置条件：无DFSTraverse输入：无前置条件：无向图的建立，对标志数组进行初始化为 0功能：从指定的顶点开始深度遍历输出：深度遍历序列，找出指定点的交往圈子后置条件：无DFS输入：无前置条件：无向图的建立，重新对数组进行置 0 处理功能：从指定的顶点开始进行深度遍历输出：输出连通图的序列后置条件：对访问过的顶点置 1DFS2输入：无前置条件：无向图的建立，已对访问过的顶点功能：从指定的顶点开始进行深度遍历输出：已标记为 1 的顶点后置条件：无2 2）功能模块设计（如主程序模块设计）功能模块设计（如主程序模块设计）1. 主程序模块：连接各种功能子模块，完成程序的基本操作实现功能2. 构造社会网络模块：按照要求构建无向图3. 邻接矩阵模块：根据用户输入社会网络，输出该网络图的邻接矩阵4. 核心人物模块：根据用户输入社会网络，计算得出该社会网络中的核心人物5. 活跃人物模块：根据用户输入社会网络，计算得出该社会网络中的活跃人物6. 边缘人物模块：根据用户输入社会网络，计算得出该社会网络中的边缘人物7. 交往圈子模块：根据用户输入社会网络，计算得出该网络中指定人物的交往圈子8. 桥接人物模块：根据用户输入社会网络，通过深度遍历方式得出两个小团体的桥接人物3 3）模块层次调用关系图）模块层次调用关系图Main()Main()Mgraph()Mgraph()createUGcreateUGDFS2DFS2centrecentrehuoyuehuoyuebianyuanbianyuanPgraphPgraphDFSDFS四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。/ 主程序模块const int maxsize=100;templateclass 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 v);void DFS2(int n);private:T vertexmaxsize;/顶点数组int arcmaxsizemaxsize;/边数int vertexnum,arcnum;/定点数，边数void createUG(T a,int n,int e);int *visited;/构造函数templateMgraph:Mgraph(T a,int n,int e) visited=new intvertexnum;for(int i=0;ivoid Mgraph:createUG(T a,int n,int e)/创建无向图vertexnum=n; /顶点数arcnum=e; /边数int i,j,k;for (i=0; i>i>>j; /边依附的两个顶点的序号arci-1j-1=1; /置有边标志arcj-1i-1=1; /该网络的核心人物，活跃人物，边缘人物templatevoid Mgraph:centre(int n) vertexnum=n;int i,j;int k=0;int amaxsize=0;for(i=0;ib)b=ai;k=i;coutvoid Mgraph:huoyue(int n) vertexnum=n;int i,j;int amaxsize=0;for(i=0;ivertexnum/2)coutvoid Mgraph:bianyuan(int n) vertexnum=n;int i,j;int amaxsize=0;for(i=0;ivoid Mgraph:Pgraph()/输出邻接矩阵int i,j;for(i=0;ivoid Mgraph:DFSTraverse(int v) /深度优先遍历图coutvoid Mgraph:DFS(int v) /深度优先遍历图(无向图)if (v=0)/判断是不是初始使用是的话初始化顶点标记矩阵，代表没有访问过for (int i=0;ivoid Mgraph:DFS2(int n)visitedn=1;for(int j=0;j#include usingusing namespacenamespace std;std; constconst intint maxsize=100;maxsize=100; templateT> classclass MgraphMgraph public:public:Mgraph(TMgraph(T a,inta,int n,intn,int e);/e);/构造函数，构造函数，aa表示数组，表示顶点的表示数组，表示顶点的 个数，个数，e e 表示边数表示边数voidvoid centre(intcentre(int n);n); /核心人物成员函数核心人物成员函数voidvoid Pgraph();/Pgraph();/输出邻接矩阵输出邻接矩阵voidvoid huoyue(inthuoyue(int n);/n);/活跃人物成员函数活跃人物成员函数voidvoid DFSTraverse(intDFSTraverse(int v);v); voidvoid bianyuan(intbianyuan(int n);/n);/边缘人物成员函数边缘人物成员函数voidvoid DFS(intDFS(int v);v);voidvoid DFS2(intDFS2(int n);n); private:private: T T vertexmaxsize;/vertexmaxsize;/顶点数组顶点数组 intint arcmaxsizemaxsize;/arcmaxsizemaxsize;/边数边数 intint vertexnum,arcnum;/vertexnum,arcnum;/顶点数，边数顶点数，边数 voidvoid createUG(TcreateUG(T a,inta,int n,intn,int e);/e);/构建无向图构建无向图 intint *visited;*visited; /构造函数构造函数 templateT> Mgraph:Mgraph(TMgraph:Mgraph(T a,inta,int n,intn,int e)e) visited=newvisited=new intvertexnum;intvertexnum;for(intfor(int i=0;iT> voidvoid Mgraph:createUG(TMgraph:createUG(T a,inta,int n,intn,int e)e) /创建无向图创建无向图vertexnum=n;vertexnum=n; /顶点数顶点数arcnum=e;arcnum=e; /边数边数intint i,j,k;i,j,k;forfor (i=0;(i=0; i>i>>j;cin>>i>>j; /边依附的两个顶点的序号边依附的两个顶点的序号arci-1j-1=1;arci-1j-1=1; /置有边标志置有边标志arcj-1i-1=1;arcj-1i-1=1; /该网络的核心人物，活跃人物，边缘人物该网络的核心人物，活跃人物，边缘人物 templateT> voidvoid Mgraph:centre(intMgraph:centre(int n)n) vertexnum=n;vertexnum=n; intint i,j;i,j; intint k=0;k=0; intint amaxsize=0;amaxsize=0; for(i=0;ib)if(ai>b) b=ai;b=ai; k=i;k=i; coutT> voidvoid Mgraph:huoyue(in
