(最新整理)社会网络分析系统的设计和实现数据结构课程设计46862763

1、(完整)社会网络分析系统的设计和实现数据结构课程设计46862763(完整)社会网络分析系统的设计和实现数据结构课程设计46862763 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)社会网络分析系统的设计和实现数据结构课程设计46862763）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)社会网络分析系

2、统的设计和实现数据结构课程设计46862763的全部内容。我浚醉典朱胞札蠕点映毕损定般拄罕宦再熬砾纫薄末奉蛛葵谁净言喻咽围棚苏常孙机且玲溅硬童媒茂棕瓮料嘲吸逻累矽丛叔硼询奉斑腾品揭扑旱侩胰瓮膏珊领产砷犬腺悔氯庐蓝锦苯鼠扼迎趁昭风辊欺戎陨蔬贞忌舟昌芥弓当乡油踩疏铃分情辱棕散漳剖诽机妒墨文疡耸痉妆举鼓奔咀乌毛谷匪毁典驱辅洗砧秤浩扮苞冯痢秦索绒等识佃春饶堪穷举枚京澄婪剐冬叠蓟庐惨瘩老绘递皮岗漱乘埔七叭踪渠第倡耸晤密序新借舜恢颅羽往瞧尼议约怯扑介杨奶赦檀焦烷剑蘑潭胯颐检桅中戊返乙梯缮福概哺知馏献欣匙晕拟套偷烈惭灶俭炕奥磐户肄扫捅醉祷确跌哇弧赵飞焚酋酚煎笔肥靴洲霉瞥聚甫退破上海电力学院数据结构（c+）课

3、程设计题目: 综合实验16 社会网络分析系统的设计和实现(*)目 录一、 设计题目1二、需求分析11）运行环境（软、硬件环境）12)输入灿喷胰拢念兹迫汞测翅瘦泥座沧垦舵昨市陨粕区缔猾声睛挨倔腿榜误襟绳矢螺捂观缔虫民矿粳咐沫惊犯忙酸炽化祝漱奋信愉淆园麦亩式靡勇滦翰账婆晾颐姑罩默罐匠娇庆恶炳释到裴扣潦蹬咆哗莎华厦欢惫幅钱讳舅逝锅懈肤遂涅舒毕盯气妇扶夯氖苯度暴怎忆渐怎宋泰仁元赘度郝房试顽夷嫂灾鞋墒诵苯摄凡甩坯剪黑阎逃搽集苯衍筏呻略寝窥臀堤裔根叉呀谭廓眶夫嚎艺拜伶麻假隔训蕾咱摘躬畜寂棵垛乱似茸露何媒炼筹莱岁种瞻宠苇激京勤滇甘蕊碘臼萨手衔妆势汪茄捡芯源蹬田称塞邱珊赶虐床斤脖来庸瘁电帮习挤革闷尧琼嗡拴篆诬

4、支耳中诸基佯央盲方蘸塌证勤寥脾烃茁忆懊轰舆带风贮社会网络分析系统的设计和实现数据结构课程设计46862763州脏肺闸倡韭惨汉桂淹砧表钡郡靴茵赏瞒搐涎琉弱蚌事里死游贝泉牲出顶寡特忱恫怖报诞犀皮散揭寨练肌理烈酥上乏骇市恢聋餐佳昆函啼普讹鞍戏孕乐媒孕沃金鼓掏讹挑滥貉吟蛰由毙胎戍菩住泅汇序虏意什迈岩后讨净瓤酿闯涕赃意晃吃獭骆铣悟表腑肃锨山贱伏秃茅晓借攘零枫窜闷妻辖自撤沂猖翻炬罕衡篱偶蛤它末弧婿坑渡货霸大粟督臼六眷诅葱超荧完掸泛晚祁用蓑赊融伺圈事伞再类蒋磅辛哇栗朴亿薄船堤油料绵店帘经眶面届苯札冯楔筏架噪蔓误桃喇跟犯攀谍到式筹碰卉势茅码褐噬促邦旷雏哮耗沾寓仲疼礼签选诗闷作武乙伙圆妥绰考潞肥羞谣肮傍帜过缕栈

5、榷侥彤艘羽投陶排豫瓶上海电力学院数据结构(c+）课程设计题目： 综合实验16 社会网络分析系统的设计和实现(*）目 录一、 设计题目1二、需求分析11)运行环境（软、硬件环境)12)输入的形式和输入值的范围13）输出的形式描述14)功能描述15）测试数据2三、概要设计21）抽象数据类型定义描述22）功能模块设计(如主程序模块设计）53）模块层次调用关系图5四、详细设计6五、调试分析12 问题改进补充12 算法的时间空间复杂性分析14 心得体会14六、测试结果15七 、附录：程序设计源代码161、 设计题目社会网络分析系统的设计和实现二、需求分析1）运行环境(软、硬件环境）软件:microsof

6、t visual c+ 6.0硬件：能运行microsoft visual c+ 6.0的硬件平台如cpu:intel 酷睿i3 3217u；内存4g；操作系统windows 72）输入的形式和输入值的范围数据类型： 整型（int）、字符型（char) 范围：1. 总人数（1100）2. 人员名称(az）3. 人员数字代码（1100）4. 关系总数（1100）5. 某条关系（人员数字代码 人员数字代码 权值）注：权值(1100）即email数据举例:总人数8个、人员名称abcdefgh、人员数字代码12345678、关系总数15条、具体某一条关系1 2 9。3)输出的形式描述1。 该社会网络的

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

8、物的关系的二维数组arcmaxsizemaxsize图中人物总数vertexnum和关系总数，arcnum标志数组visitedoperationu mgraph （构造函数)初始化值：社会网络中 a人员名称，n总人数，e总关系数;标志顶点访问的数组visitedi置0. 动作：将键盘输入的值带入，调用有向网的创建函数createhw。u createhw（创建有向网)输入:图的人数和关系数、存放图中人的数组、存放图中关系的数组前置条件：构造函数调用功能：创建有向网输出：无后置条件:有向网建立u printgraph（输出邻接矩阵)输入：无前置条件:有向网已经建立功能：输出邻接矩阵输出：邻接矩

9、阵后置条件：无u centre（核心人物）输入：无前置条件：有向网已经建立，设定核心人物的域值yu=20功能:找出社会网络的核心人物（计算每个顶点的入度,找度数大于域值的人物）输出:若找到则输出社会网络的核心人物，没有找到则输出“无.后置条件：无u huoyue（活跃人物）输入：无前置条件：有向网已经建立，设定活跃人物的域值yu=10功能：找出社会网络的活跃人物(计算每个顶点的出度,找度数大于域值的人物）输出:若找到则输出社会网络的活跃人物，没有找到则输出“无”。后置条件：无u bianyuan（边缘人物）输入:无前置条件：有向网已经建立，设定边缘人物的域值yu=5功能:找出社会网络的边缘人物

10、(计算每个顶点的出入度之和，找度数小于域值的人物)输出：若找到则输出社会网络的边缘人物，没有找到则输出“无”.后置条件：无u quanzi(交往圈子)输入:输入一个人员的数字代码（用于查找该人员的交往圈子）前置条件：有向网已经建立功能:查找交往圈子（与指定人物之间有边的人物就是与该人物有联系的,这些人就构成了一个交往圈子）。输出：输出指定人物的交往圈子后置条件：无u add（计算人员两两间的关系数)输入：无前置条件：有向网已经建立，给出两个人物的数字代码功能：计算指定人员两两间的联系数并返回（为查找小团体、桥接人做准备）输出：返回指定人员两两间的联系数后置条件：无u by（返回边缘人物数字代码

11、）输入:无前置条件：有向网已经建立功能：找边缘人物并返回该人物数字代码（为查找小团体、桥接人做准备）输出:返回边缘人物的数字代码后置条件：无u dfs（小团体)输入：无前置条件:有向网、add函数、by函数都已经建立,初始化顶点标记矩阵（全部置0）功能：查找小团体，从指定的顶点开始进行深度优先遍历（如果当前人物没有被访问过，并且也不是边缘人物，输出该人物;再从该人物开始进行深度遍历,如果找到与该人物交往密切的人物则输出，继续找下一个）输出:输出小团体后置条件：对访问过的顶点置1u dfs2（桥接人）输入：无前置条件：有向网、add函数、by函数都已经建立功能：查找桥接人，从指定的顶点开始进行深

12、度优先遍历输出：两个小团体中，有联系，但没有达到域值的人物后置条件：无end adt mgraph2）功能模块设计（如主程序模块设计）1. 主程序模块：连接各种功能子模块，完成程序的基本操作实现功能2。 构造社会网络模块：按照要求构建有向网3. 输出邻接矩阵模块：根据用户输入的社会网络，输出该网络图的邻接矩阵4。 核心人物模块:根据用户输入的社会网络，计算得出该社会网络中的核心人物5. 活跃人物模块：根据用户输入的社会网络，计算得出该社会网络中的活跃人物6. 边缘人物模块:根据用户输入的社会网络,计算得出该社会网络中的边缘人物7。 交往圈子模块：根据用户输入的社会网络，计算得出该网络中指定人物

13、的交往圈子8。 人物两两联系数模块：根据用户输入的社会网络,返回指定人员两两间的联系数9。 判断边缘人物模块:根据用户输入的社会网络，返回边缘人物的数字代码10. 小团体模块:根据用户输入的社会网络，深度优先遍历得出该网络中的所有小团体11。 桥接人物模块：根据用户输入的社会网络，深度优先遍历得出小团体间的桥接人物3）模块层次调用关系图桥接人dfs2 小团体dfs 交往圈子quanzi边缘人物bianyuanmain( )mgraph活跃人物huoyue核心人物centre输出邻接矩阵printgraph构建有向网createhw人员两两联系数add判断边缘人物by 4、 详细设计实现概要设计

14、中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法.#include#includestdlib.hincludestring。hconst int maxsize=100;const int infinity=0；/最大值无穷定义一个mgraph类，用来实现基本功能：构造函数初始化值，根据用户输入的社会网络图构建有向网(邻接矩阵存储形式）,查找该社会网络中的核心人物、活跃人物、边缘人物、小团体、桥接人物，查找任何人的交往圈子.templateclass mgraphpublic： mgraph(t a，int n，int e)；/构造函数，a结点数组，n顶点个数，e边数 voi

15、d printgraph()；/输出邻接矩阵 void centre（int n); /核心人物成员函数 void huoyue(int n）;/活跃人物成员函数 void bianyuan（int n);/边缘人物成员函数 void quanzi(int v）； /查找交往圈子函数 int add（int s,int t) ；/计算人员两两间联系数 int by（int n) ; void dfs（int v，int n) ； /查找小团体函数（深度优先遍历） void dfs2（int v，int n) ； /查找桥接人函数(深度优先遍历)private：t vertexmaxsize;/

16、存放顶点int arcmaxsizemaxsize； /存放边int vertexnum,arcnum;/顶点数，边数void createhw(t a,int n,int e）；/构建有向网int visited；;-mgraph 构造函数-初始化值：社会网络中 a人员名称，n总人数，e总关系数;标志顶点访问的数组visitedi置0；调用有向网的创建函数createhw。templatemgraph：mgraph(t a，int n，int e) visited=new intvertexnum; for(int i=0;ivertexnum;i+) visitedi=0； createh

17、w(a,n,e); /创建/-createhw 构建有向网-将用户输入的值带入,并完成存储：人物名称放入一维数组vertexi，人物间的email发送数（权值）放入二维数组arci-1j-1。template class tvoid mgrapht:：createhw(t a，int n，int e) int w; /权值 vertexnum=n; /顶点数 arcnum=e; /边数 int i，j，k;cout”注意！请将人名对应到数字代码输入endl；cout”输入格式为：人员1 人员2 权值”endl;for (i=0; ivertexnum; i+） vertexi=ai；/顶点数组

18、赋初值(放入一维数组）for （i=0； ivertexnum； i+） /初始化邻接矩阵for （j=0; jvertexnum； j+）arcij=0； for (k=0; karcnum; k+) /依次输入每一条边，并修改邻接矩阵的相应元素cout”请输入第”ijw; /边依附的两个顶点的序号arci-1j1=w； /置有边标志，存放权值/-printgraph 输 出-通过二重循环输出社会网络对应的邻接矩阵存储图template class tvoid mgraph：printgraph(）/输出邻接矩阵int i，j;for(i=0;ivertexnum;i+） for(j=0；j

19、vertexnum；j+) coutvoid mgrapht：:centre(int n) vertexnum=n；int i,j,count=0;int xmaxsize=0；for(i=0；ivertexnum；i+）for（j=0；jvertexnum;j+）/计算每个顶点的入度xi+=arcji;/xj存放入度数cout核心人物是：”； int yu=20； /找度数大于域值的人物， 域=20for（i=0；ivertexnum；i+） if(xiyu)coutvertexi ”； count+ ；if(count=0) cout无”;coutendl；/-huoyue活跃人物-若人物

20、发出的email总数大于10封，我认为就是活跃人物，所以我设置了域为10，huoyue函数要完成的功能是找出度大于域值的人物，并输出。 templatevoid mgrapht:huoyue(int n) vertexnum=n;int i，j,count=0；int ymaxsize=0；for(i=0;ivertexnum；i+)/计算每个顶点的出度for( j=0;jvertexnum;j+)yi+=arcij；/yi存放出度数coutyu） coutvertexi ”； count+ ；if(count=0） cout”无;coutvoid mgrapht:bianyuan(int n

21、） vertexnum=n;int i,j，count=0；int zmaxsize=0;for（i=0；ivertexnum;i+）/计算每个顶点的度数for（j=0；jvertexnum；j+）zi=zi+arcij+arcji； /zi存放入度+出度之和 cout-边缘人物是：”；int yu=5； /找度数小于域值的人物， 域=5for （i=0； ivertexnum; i+) if(ziyu） coutvertexi ; count+ ；if（count=0) cout无”；coutendl；/quanzi查找交往圈子-根据用户输入的一个人员的数字代码,查找该人员的交往圈子,我认为

22、与指定人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子.template void mgraph:：quanzi(int v） int count=0；cout”vertexv-1的交往圈子是：；for (int j=0； jvertexnum; j+） if （arcv-1j！=infinity|arcjv1!=infinity） /交往圈子：与指定人物之间有边就算 coutvertexj ； count+； if(count=0) cout”无”；coutendl;/-add 计算人员间两两间联系数-计算指定人员两两间的联系数并返回（为查找小团体、桥接人做准备)templ

23、ate class tint mgrapht：add(int s,int t) int temp；if(st） temp=s； s=t； t=temp; else return （arcst+arcts)；/-by 查找小团体中用来判断边缘人物-找边缘人物并返回该人物数字代码（为查找小团体、桥接人做准备）templateclass tint mgrapht：by(int n)int i,j,count=0；int zmaxsize=0；for(i=0；in;i+）/计算每个顶点的度数for（j=0;jn;j+）zi=zi+arcij+arcji； /zi存放入度+出度之和int yu=5； /

24、 域=5for (i=0; in; i+） if(ziyu) return（i); count+ ;if（count=0） return（99);/-dfs 查找小团体-查找小团体，从指定的顶点（我设置的是0也就是第一个人）开始进行深度优先遍历（如果当前人物a没有被访问过，并且也不是边缘人物，输出该人物a；再从该人物a开始进行深度遍历，如果找到与该人物交往密切的人物b则输出，再从b开始继续找下一个），并且在查找过程中输出小团体成员。template void mgrapht:dfs（int v，int n) /v控制递归 n为总人数 if （v=0）/如果是第一次使用for （int k=0;

25、kn;k+)visitedk=0; /初始化顶点标记矩阵（全部置0 代表没有访问过)dfs（v+1，n)； /利用递归算法重复调用深度优先遍历dfselseif (visitedv-1=0）/如果当前人物没有被访问过if（v-1！=by（n)）/并且也不是边缘人物 int yu=10; /域值coutvertexv1yu)/如果两个结点之间交往 密切dfs(k+1,n); /找下一个cout”,”;dfs(v+1，n）;else dfs(v+1,n）;/-dfs2 查找桥接人-查找桥接人,两个小团体中，有联系，但没有达到域值的人物。从指定的顶点开始进行深度优先遍历template class

26、tvoid mgraph:dfs2（int v,int n） /v控制递归 n为总人数int yu=10； /域值for （int k=v-1;kn;k+)if （add（v-1，k)0 & add（v1，k)yu & v1!=by(n)& k!=by(n）)/如果两个结点之间有边但交往不密切，并且分别属于两个小团体coutvertexv-1” ”vertexk ；/输出桥接人结点的值dfs2（k+1,n）； /找下一个if (v=n)dfs2(v+1,n）; /-主函数-测试刚刚的mgraph类中的各种成员函数是否编写正确，完成要求的功能。void main(） cout 欢迎使用社会网络分

27、析系统 endl；int n,e,m； /n总人数，e总关系数，m某个人员的数字代码coutn; char a=new charn; /a是指针，a的值是新建数组的首地址，a0,a1等 cout请依次输入人员名称：； for（int i=0;in;i+） cinai; coute；mgraphchar g（a，n，e)；cout”以下是该社会网络对应的邻接矩阵:endl；g。printgraph（);cout*社会网络分析中*：”endl;g。centre（n)；g。huoyue(n)；g。bianyuan(n）；cout-小团体是:；g.dfs（0,n);coutendl; cout”联系小

28、团体的桥接人物是：; g。dfs2（1，n)；coutendl； coutm;g。quanzi（m)；五、调试分析 （包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会） 问题&改进&补充：【问题1】：小团体和桥接人的理解与定义小团体:小团体就是由交往比较密切的一群人构成的,因此要设一个域值，email数据（权值）超过这个域值才能算交往密切；一个人不能单独构成一个小团体，小团体至少要2个成员组成.桥接人：桥接人就是联系两个小团体的中间人，也就是说一个小团体可以通过对应的桥接人和另外一个小团体取得联系，桥接人分属于两个不同的团体.【问题2】：参数传递问题 目的是在一个成员函

29、数里调用另一个成员函数中的数据，一开始想到的是将代码段直接复制，但考虑到效率的问题,没有使用；然后想到了利用全局变量，但又觉得不妥；后来问了老师,老师建议我使用参数传递的方法，将需要的数据带回。于是做了如下修改：主函数中，增加char team2020； 并将g。dfs（0)； 改成g。dfs(0,n,team）； 使dfs查找小团体的函数中，可以使用主函数中的数据n总人数;使桥接人的函数中，可以使用dfs查找小团体的函数中的二维数组：team2020【问题3】：递归调用中的数据存储为了实现桥接人的查找，要将小团体储存到一个二维数组中，在递归调用中存入数组真的不是一件简单的事，初始化数组的下标

30、就是一件很麻烦的事情，因为递归调用每一次都会调用函数本身，若在函数体里面初始化数组下标的话，每调用一次，就会归零.解决方法:使用参数传递，将数组下标作为两个参数，每次调用时都将其传回,这样可以保证数组下标有效完成计数的功能。主函数中,将g.dfs（0,n，team)； 改成g。dfs（0,n,team,0，0）头文件中,改成void dfs(int v，int n，char team2020,int i,int j)【改进1】：createhw 构建有向网中，原本老师ppt上演示的是:arcij=1; arcji=1; 之后改进为 ：arci1j1=1； arcj-1i-1=1; 改进原因：按

31、照原来的写法，输入两个人员之间的关系（顶点与顶点之间的边）要从0开始，由于和日常生活的数数习惯不同，因此加以改进,使之从1开始，方便使用。【改进2】：查找交往圈子中，原本应该是：if （arcvj!=infinity|arcjv!=infinity） 需要改为:if （arcv1j!=infinity|arcjv-1!=infinity） 改进原因：由于改进1的影响,主函数中要求用户输入一个人员的数字代码，查找该人员的交往圈子时，用户也是从1开始数的，为了使程序显示正确，需要将下标v改成v-1。【改进3】：存放小团体的数组其实不是必要的之前一直在纠结递归调用中存放数组的问题,但突然7号早上想到

32、另一个更省事儿的方法,用排除法找桥接人!换个角度来看桥接人，就是分属于两个小团体，之间有联系但是联系不密切，另外，桥接人也不能是边缘人物.于是做了如下简化改进：主函数中，将g。dfs（0，n,team，0，0); 改成g。dfs（0,n）；头文件中，改成void dfs（int v，int n）【补充1】：补充没有核心人物或者没有活跃人物或者没有边缘人物的情况。一开始也没有想的这么全面,经过多次测试后发现这几种情况也是存在的，原来的程序在这种情况下显示的是空白，因此加以改进了一下增加了count计数器，如果一个人物都没有的话，就输出“无”。 算法的时间空间复杂性分析1。 本设计中算法的时间复杂

33、度分为三类：o(1)add 计算人员间两两间联系数o（n）mgraph 构造函数o(n2)-createhw 构建有向网、printgraph 输出邻接矩阵、centre核心人物 、huoyue活跃人物、bianyuan边缘人物、quanzi查找交往圈子、by 判断边缘人物、dfs 查找小团体、dfs2 查找桥接人2。 本设计中算法的空间复杂度为:o(1） 心得体会:一开始选题的时候,就觉得这个题目很有趣,尽管它的难度系数比较高，但我还是义无反顾地选择了它-社会网络分析系统的设计和实现.图这一章老师讲的没有单链表和二叉树那样细致，因为快到期末了课时很紧张，但做相关实验的时候，我就对图这部分的内

34、容产生了浓厚的兴趣,因为社交网络和我们的生活比较贴切，图的应用在类似人人、微信朋友圈的社交网络中都会用到.自从我做完了上一个大作业,多余的两天半时间我就开始着手做这个课程设计了，一开始选择了使用无向图,成功完成了除小团体和桥接人之外的所有功能，但等到第一次课程设计上课的时候，和老师探讨了小团体和桥接人的查找方法后，发现一开始就选错了图的模型,应该选择有向网!之前的代码也要全部推翻重来,顿时觉得压力好大.好在回到寝室后的一整个下午加上一整个晚上的效率很高，终于将实现对email数据的预处理、建立社会网络的邻接矩阵、找出社会网络中核心人物、活跃人物和边缘人物的函数都完成了。但对于小团体和桥接人的定

35、义还是比较模糊的,于是第二次上课程设计的时候，详细咨询了老师。之后大量的时间都花在设计小团体和桥接人上了。期间也碰到了很多问题，通过自己调试修改、上网查阅资料、课上课下咨询老师,都得到了解决。通过这次数据结构课程设计，我对之前学习的c+内容更加熟悉了，更好地掌握与理解了模板的使用、二维数组、参数传递、函数调用等内容；对数据结构这门课程也有了更进一步的学习与掌握，处理问题的思路与方法也有所拓宽，能理解与运用图的相关知识解决实际问题在老师的指导下，不仅独立完成了社会网络分析系统的设计和实现，还从老师那里学到了很多书上没有的技巧，比如c+程序调试中所使用“断点调试方法，之前我是完全不知道的。通过这次

36、课程设计，在这短短的5天中,我感觉收获颇多！六、测试结果七 、附录:程序设计源代码#includeiostream.hincludestdlib.h#includeconst int maxsize=100;const int infinity=0；/最大值无穷templateclass tclass mgraphpublic: mgraph（t a,int n,int e）；/构造函数，a结点数组，n顶点个数，e边数 void printgraph（);/输出邻接矩阵 void centre（int n)； /核心人物成员函数 void huoyue（int n);/活跃人物成员函数 voi

37、d bianyuan(int n）；/边缘人物成员函数 void quanzi(int v); /查找交往圈子函数 int add(int s,int t） ;/计算人员两两间联系数 int by(int n) ； void dfs（int v,int n） ； /查找小团体函数（深度优先遍历) void dfs2（int v，int n） ； /查找桥接人函数(深度优先遍历)private:t vertexmaxsize；/存放顶点int arcmaxsizemaxsize; /存放边int vertexnum，arcnum；/顶点数，边数void createhw（t a，int n,in

38、t e)；/构建无向图int *visited；;/-mgraph 构造函数-template:：mgraph（t a，int n，int e) visited=new intvertexnum; for(int i=0；ivoid mgrapht：createhw(t a,int n，int e) int w;/权值 vertexnum=n； /顶点数 arcnum=e； /边数 int i,j,k；cout注意！请将人名对应到数字代码输入endl；cout输入格式为:人员1 人员2 权值”endl；for （i=0； ivertexnum； i+） vertexi=ai；/顶点数组赋初值(

39、放入一维数组）for （i=0; ivertexnum; i+) /初始化邻接矩阵for （j=0； jvertexnum; j+）arcij=0; for （k=0; karcnum; k+） /依次输入每一条边，并修改邻接矩阵的相应元素cout”请输入第k+1jw; /ij边依附的两个顶点的序号，w权值arci1j-1=w; /置有边标志，存放权值/-printgraph 输 出-template void mgrapht:：printgraph（）int i,j;for(i=0;ivertexnum；i+）for（j=0；jvertexnum；j+) coutarcijt；coutend

40、l；/-centre核心人物-templateclass tvoid mgraph:：centre(int n）vertexnum=n;int i,j，count=0；int xmaxsize=0;for(i=0；ivertexnum；i+)for(j=0；jvertexnum;j+）/计算每个顶点的入度xi+=arcji;/xj存放入度数coutyu)coutvertexi” ; count+ ；if(count=0) cout”无”；coutendl；/-huoyue活跃人物-templateclass tvoid mgrapht：huoyue（int n)vertexnum=n;int

41、i,j,count=0;int ymaxsize=0；for(i=0;ivertexnum;i+)/计算每个顶点的出度for( j=0;jvertexnum;j+）yi+=arcij;/yi存放出度数cout”-活跃人物是：”;int yu=10； /找度数大于域值的人物, 域=10for （i=0； iyu） coutvertexi ; count+ ；if(count=0) cout”无”；coutendl；/-bianyuan边缘人物templateclass tvoid mgraph：:bianyuan(int n）vertexnum=n；int i,j,count=0;int zma

42、xsize=0；for(i=0;ivertexnum;i+）/计算每个顶点的度数for（j=0；jvertexnum；j+)zi=zi+arcij+arcji； /zi存放入度+出度之和 cout”-边缘人物是:;int yu=5； /找度数小于域值的人物， 域=5for (i=0; ivertexnum; i+) if(ziyu） coutvertexi” ”; count+ ；if（count=0) cout无;coutendl;/quanzi查找交往圈子-template class tvoid mgraph：:quanzi(int v） /深度优先遍历图int count=0；cout

43、”vertexv1的交往圈子是：;for (int j=0； jvertexnum； j+）if （arcv-1j！=infinity|arcjv1！=infinity) /交往圈子：与指定人物之间有边就算 coutvertexj ”; count+； if(count=0) cout”无”;coutendl;/-add 计算人员间两两间联系数-template class tint mgraph:：add（int s,int t) int temp；if（st)temp=s; s=t; t=temp;else return (arcst+arcts）;/-by 查找小团体中用来判断边缘人物-template：by(int n）int i,j，count=0;int zmaxsize=0；for（i=0；in;i+）/计算每个顶点的度数for(j=0；jn;j+）zi=zi+arcij+arcji; /zi存放入度+出度之和int yu=5; / 域=5for (i=0; in; i+） if(ziyu) return(i)； count+ ;if（count=0) return（99);/-dfs 查找小团体-template class tvoi