无向图的连通分支问题
?问题描述：
试设计用并查集来计算一个无向图的连通分支的算法。
?编程任务：
对于给定的无向图G，用并查集编程计算无向图G的连通分支。
?数据输入：
由文件input.txt给出输入数据。第一行有3个正整数n，k和m，分别表示无向图G有n个顶点和k条边，m是查询顶点对个数。接下来的k+m行，每行有2个正整数。前k行给出图G的k条边（可能重复）；后m行是查询顶点对。
?结果输出:
对于每个查询顶点对(i,j)，将计算结果依次输出到文件output.txt。如果顶点i和顶点j 属于图G的同一连通分支，则输出“Yes”，否则输出“No”。
输入文件示例输出文件示例
input.txt output.txt
10 3 3 1 2
3 4
1 3
2 3
1 4
5 6 Yes Yes No
数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 图的遍历和生成树求解实现 年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日 完成时间: 2012 年 12 月 26 日 课程设计成绩： 指导教师签名：年月日
目录 摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)
摘要 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词：计算机；图；算法。
实习三求无向连通图的生成树 1?需求分析 问题描述： 若要在n个城市之间建设通信网络，只需要架设n-1条路线即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 基本要求： (1) 利用克鲁斯卡尔算法求网的最小生成树，其中，以课本8.7节中的等 价类表示构造生成树过程中的连通分量。 (2) 利用普里姆算法求网的最小生成树。 (3) 以文本文件形式输出生成树中各条边以及他们的权值。 2.设计 (1) 设计思想：创建邻接矩阵存储结构。本程序主要分为两个模块：创建邻接矩阵模块，最小生成树模块。创建邻接矩阵模块：以邻接矩阵的存储形式创建无向网。最小生成树模块：生成最小生成树，输出其各条边及权值。 (2) 概要设计：int型LocateVex函数判断权值在矩阵的位置；声明CraeteGraph 函数创建邻接矩阵；声明kruskal函数用于生成最小生成树；声明main函数为程序调用步骤。 (3) 设计详细：a.将程序分为两个模块： B. 主函数流程图:
C. 最小生成树流程图 (4) 调试分析：--变量没定义就使用 --子函数嵌套定义； --使用数组是越界； (5) 用户手册：a.主页面： 解决：定义完变量在使用。 解决：子函数单独定义，可调用。 解决：注意数组的值，注意不能越界 b.输入顶点数及边数的信息:
d.输入顶点及权值 c.输入顶点信息 （6）测试结果：输出最小生成树及 权值 #i nclude
第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵
C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历
7.4.1无向图的连通分量和生成树。
void DFSForest(Graph G,CSTree &T) //建立无向图G的深度优先生成森林的 //（最左）孩子（右）兄弟链表T。 { T=NULL; for(v=0;v
《数据结构》实验报告 实验内容：（一）判断一个图有无回路 （二）求一个无向图G的连通分量的个数 一、目的和要求（需求分析）： 1、了解图的定义和图的存储结构。 2、熟悉掌握图的邻接矩阵和邻接表。 3、理解图的遍历算法---深度优先搜索和广度优先搜索。 4、学会编程处理图的连通性问题。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 判断一个图有无回路： 在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。 在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。 无向图则可以转化为： 如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度>=2。 第一步：删除所有度<=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。 第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。 如果最后还有未删除的顶点，则存在回路，否则没有。 求一个无向图G的连通分量的个数： 用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。 三、调试和运行程序过程中产生的问题及采取的措施： 在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块 void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)， 而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。 四、源程序及注释：
#include
int *visit=(int *)malloc((n+1)*sizeof(int)); int **a=(int **)malloc((n+1)*sizeof(int*)); int e,f; for(e=0;e<=n;e++){ a[e]=(int *)malloc(sizeof(int)*(n+1)); } for(e=1;e<=n;e++) for(f=1;f<=n;f++) a[e][f]=0; for(e=1;e<=n;e++) visit[e]=0; for(i=1;i<=m;i++){ scanf("%d %d",&e,&f); a[e][f]=1; a[f][e]=1; } int k=0; int sum=0; int *b=(int *)malloc((n+1)*sizeof(int)); DFS(a,1,&k,n,visit); sum++; b[0]=k; e=1; int v; for(v=1;v<=n;v++){ k=0; if(visit[v]==0){ DFS(a,v,&k,n,visit); sum++; b[e]=k; e++; } } printf("%d\n",sum); int t; for(i=0;i 有向图的强连通分量 分类：C/C++程序设计2009-04-15 16:50 2341人阅读评论(1) 收藏举报最关键通用部分：强连通分量一定是图的深搜树的一个子树。 一、Kosaraju算法 1.算法思路 基本思路： 这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图G T。(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是E AB存在于反图G T)，能遍历到的顶点就是一个强连通分量。余下部分和 原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。7 改进思路： 当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于G T来说)到其他树上的 呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于G T来说)就可以了。每次深搜都得到一个强连通分量。 隐藏性质: 分析到这里，我们已经知道怎么求强连通分量了。但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z， 〉，Z是整数集， 定义为x xy=xy, ?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 求无向连通图的生成树 ————————————————————————————————作者：————————————————————————————————日期: 求无向连通图的生成树 一、实验目的 ⑴掌握图的逻辑结构 ⑵掌握图的邻接矩阵存储结构 ⑶验证图的邻接矩阵存储及其遍历操作的实现 二、实验内容 （1)建立无向图的邻接矩阵存储 (2)对建立的无向图,进行深度优先遍历 (3)对建立的无向图进行广度优先遍历 三、设计与编码 (1)本实验用到的理论知识 （2)算法设计 (３)编码 ／/ 图抽象类型及其实现．cpｐ : Defｉnes ｔhe enｔry poiｎt for the coｎｓｏle aｐplication. /／ #include"ｓtdafｘ.ｈ" #ｉｎclude"Graｐh.h" #incluｄe"ｉｏｓtream．h＂ int Grａｐｈ：:Ｆinｄ(int keｙ,int &ｋ) { ?iｎt flａg＝0; ?foｒ(iｎt i=0;i＜VｅrtexLｅn;ｉ++) ?if(Ａ[ｉ].ｄata.kｅy＝=ｋeｙ){k=ｉ;flaｇ=1;bｒeａk;}; ｒetuｒn fｌag; }; int Graｐh::CｒeａteGraph(inｔ vertexnuｍ,Edgｅ *E,inｔ edgeｎum) ｛／/由边的集合E(E[0]~Ｅ［VｅrtｅｘNum-1]）,生成该图的邻接表 表示 if(veｒtｅxnum<１）reｔurｎ(－１）;//参数vｅrtｅxnum非法ｉnt i,frｏｎt，reａr,k； ?Eｎode *ｑ; ?//先生成不带边表的顶点表--即顶点为孤立顶点集 ?A=newＶnode［verｔexnuｍ］; if(!A)return（0）;//堆耗尽 ?fｏｒ(i=０;i 《数据结构》实验报告 ◎实验题目:无向图的存储和遍历 ◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法； 2、掌握图的邻接表存储结构和深度优先遍历的非递归算法。 3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。 ◎实验内容：建立有10个顶点的无向图的邻接表存储结构，然后对其进行深度优先遍历，该无向图可以是无向连通图或无向非连通图。 一、需求分析 1、输入的形式和输入值的范围：根据提示，首先输入图的所有边建立邻接表存储结构，然后输入遍历的起始顶点对图或非连通图的某一连通分量进行遍历。 2、输出的形式：输出对该图是连通图或非连通图的判断结果，若是非连通图则输出各连通分量的顶点，之后输出队连通图或非连通图的某一连通分量的遍历结果。 3、程序所能达到的功能：输入图的所有边后，建立图的邻接表存储结构，判断该图是连通图或非连通图，最后对图进行遍历。 4、测试数据： 输入10个顶点（空格分隔）:A B C D E F G H I J 输入边的信息（格式为x y）:AB AC AF CE BD DC HG GI IJ HJ EH 该图为连通图,请输入遍历的起始顶点:A 遍历结果为:A F C D B E H J I G 是否继续？（是,输入1;否,输入0）:1 输入10个顶点（空格分隔）:A B C D E F G H I J 输入边的信息（格式为xy）:AB AC CE CA AF HG HJ IJ IG 该图为非连通图,各连通分量中的顶点为: < A F C E B > < D > < G I J H > 输入第1个连通分量起始顶点:F 第1个连通分量的遍历结果为:F A C E B 输入第2个连通分量起始顶点:I 第2个连通分量的遍历结果为:I G H J 输入第3个连通分量起始顶点:D 第3个连通分量的遍历结果为:D 是否继续？（是,输入1;否,输入0）:0 谢谢使用! Press any key to continue 二概要设计 1、邻接表是图的一种顺序存储与链式存储结构结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对图G中的每个顶点Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表，再将所有邻接表的表头放到数组中，就构成了图的邻接表，邻接表表示中的两种结点结构如下所示。 第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑ 求无向连通图的生成树 一、实验目的 ⑴掌握图的逻辑结构 ⑵掌握图的邻接矩阵存储结构 ⑶验证图的邻接矩阵存储及其遍历操作的实现 二、实验内容 （1）建立无向图的邻接矩阵存储 （2）对建立的无向图，进行深度优先遍历 （3）对建立的无向图进行广度优先遍历 三、设计与编码 （1）本实验用到的理论知识 （2）算法设计 （3）编码 // 图抽象类型及其实现.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include"Graph.h" #include"iostream.h" int Graph::Find(int key,int &k) { int flag=0; for(int i=0;i if(vertexnum<1)return(-1);//参数vertexnum非法 int i,front,rear,k; Enode *q; //先生成不带边表的顶点表--即顶点为孤立顶点集 A=new Vnode[vertexnum]; if(!A)return(0);//堆耗尽 for(i=0;i 求无向连通图得生成树 一、实验目得 ⑴掌握图得逻辑结构 ⑵掌握图得邻接矩阵存储结构 ⑶验证图得邻接矩阵存储及其遍历操作得实现 二、实验内容 (１)建立无向图得邻接矩阵存储 (2)对建立得无向图,进行深度优先遍历 (３)对建立得无向图进行广度优先遍历 三、设计与编码 (１)本实验用到得理论知识 (2)算法设计 (３)编码 ／/ 图抽象类型及其实现、ｃpp : Defiｎｅs the ｅntｒy poｉnt ｆor the cｏｎｓoｌe apｐｌicａtｉon、 // #incluｄｅ”stｄafx。h” #include”Gｒaph.h＂ ＃inｃlude”ioｓｔrｅaｍ。h” inｔＧraｐh::Fｉnd(int key,ｉnt＆ｋ) ｛ iｎt flag=0; fｏr(intｉ=０;i〈ＶertｅxＬeｎ;ｉ+＋) ?iｆ(A[ｉ］、dａta。kｅy==key){k＝i;fｌag=１;breａk;｝; ?return flag; ｝; int Gｒapｈ::CreateGraph(ｉnt verｔexnuｍ,Ｅdｇe ＊E,int edge ｎｕｍ) {?/／由边得集合E(E[0]~E［VertexNum—1]),生成该图得邻接表表示?if(veｒｔexｎｕm<1)reｔurn(—１);//参数verｔｅxnuｍ非法 ?ｉnt i,ｆronｔ,rｅar,k; Enode *ｑ; //先生成不带边表得顶点表-—即顶点为孤立顶点集 A=ｎew Vnｏde[vertexnｕm］; ?if(!Ａ)return(0);/／堆耗尽 for(ｉ=０;ｉ〈ｖｅrtexnum;ｉ++) { ?A[i］、data、kｅy＝i; ?A[i]、tａg=0; ??A［i]、ｄata.ＩｎDegree＝A[i]、ｄatａ。OutＤegｒee=A[i]、ｔaｇ＝0; ?A[i]、firｓt=０; ｝; VerｔexLen=veｒｔｅxｎum; ／/在生成边表 ?iｆ(edgenum〈0)return(1);//无边得图 for(i＝0;i＜edｇenuｍ;i++) { ? front＝E［i]。Heaｄ;ｒｅaｒ＝E[i]。Taｉl; ?iｆ(!Ｆiｎd(reaｒ,ｋ) ｜｜!Find(front,k))ｒeｔurn(－2);//参数E非法 ?q=new Enoｄｅ; ?if(！q)return(０); ??q-＞ｋｅy=frｏnt; q->Weigｈt=Ｅ[i]、weｉgｈt; ? q—>next=A［rear］。first; A［rear]、ｆｉｒsｔ=q; Ａ［rear]、data.ＯuｔＤegreｅ++; ? A［fｒｏnt］、datａ。InＤeｇreｅ＋+; if(Ｔype>2) ?｛ ?q=ｎew Enode; if(!q)retuｒn(０); ??q—〉key=ｒear; ???q-〉nexｔ=A［fｒｏnt]、ｆirst; ??A［fｒont］。fｉrst=ｑ; 实习三求无向连通图的生成树 1.需求分析 问题描述: 若要在n个城市之间建设通信网络，只需要架设n-1条路线即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 基本要求: (1)利用克鲁斯卡尔算法求网的最小生成树，其中，以课本8.7节中的等 价类表示构造生成树过程中的连通分量。 (2)利用普里姆算法求网的最小生成树。 (3)以文本文件形式输出生成树中各条边以及他们的权值。 2.设计 (1)设计思想：创建邻接矩阵存储结构。本程序主要分为两个模块：创建邻接矩阵模块，最小生成树模块。创建邻接矩阵模块：以邻接矩阵的存储形式创建无向网。最小生成树模块：生成最小生成树，输出其各条边及权值。 (2)概要设计：int型LocateVex函数判断权值在矩阵的位置；声明CraeteGraph 函数创建邻接矩阵；声明kruskal函数用于生成最小生成树；声明main函数为程序调用步骤。 (3)设计详细：a.将程序分为两个模块： B.主函数流程图： c.最小生成树流程图 (4)调试分析：--变量没定义就使用解决：定义完变量在使用。 --子函数嵌套定义；解决：子函数单独定义，可调用。 --使用数组是越界；解决：注意数组的值，注意不能越界。 (5)用户手册：a.主页面： b.输入顶点数及边数的信息： c.输入顶点信息： d.输入顶点及权值： (6)测试结果：输出最小生成树及权值： (7)源程序： #include 实验项目：图的先深、先广遍历生成树 实验目的： 1、学会把图转化为程序能识别的邻接矩阵 2、透彻理解图的两种遍历方法及对应的生成树。 涉及的知识点：图的表示法、生成树的概念、图的深度优先、广度优先遍历算法 实验内容： 该程序是对树进行先深、先广遍历，请在此基础上，改为处理指定图，求该图从指定结点出发的先深、先广遍历生成树。 // AdjMWGraph.h : Defines the entry point for the console application. #include "SeqList.h" #include "SeqQueue.h" const int MaxVertices=10; const int Max Weight=10000; //表示无穷大 class AdjMWGraph { private: SeqList Vertices; // 顶点信息的线性表 int Edge[MaxVertices][MaxVertices]; //边的权信息矩阵 int numOf E dges; //当前的边数 public: AdjMWGraph(const int sz=MaxVertices);//构造函数，参数是顶点数目 int GraphEmpty()const { return Vertices.ListEmpty(); } int NumOfVertices(void)//当前结点个数 { return Vertices.ListSize(); } int NumOf E dges(void)//边数 { return numOf E dges; } VerT GetValue(const int i); //取结点i的值 int GetWeight(const int v1, const int v2); //取弧的权重; //插入顶点vertex void InsertVertex(const VerT &vertex); //插入弧 第七章：图练习题 一、选择题 1、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（）条边。 A、6 B、12 C、16 D、20 5、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点 A、6 B、7 C、8 D、9 6、存储稀疏图的数据结构常用的是（）。 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。 222n D、(n-1)、C、(n+1)A、n B8、设连通图G的顶点数为n，则G的生成树的边数为（）。 A、n-1 B、n C、2n D、2n-1 9、n个顶点的无向图的邻接表中结点总数最多有（）个。 A、2n B、n C、n/2 D、n(n-1) 10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。 A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数 12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（） （1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。 v1,v4,v3,v5,v2、v1,v2,v3,v5,v4 D、v1,v3,v2,v4,v5 C、v1,v2,v3,v4,v5 B、 A． 第7章图 一、选择题 1．图中有关路径的定义是（）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 15. 下列说法不正确的是（）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 二、判断题 1.树中的结点和图中的顶点就是指数据结构中的数据元素。（） 2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（） 4. 有e条边的无向图，在邻接表中有e个结点。（） 5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（） 6．强连通图的各顶点间均可达。（） 7．强连通分量是无向图的极大强连通子图。（） 8．连通分量指的是有向图中的极大连通子图。（） 11.无向图的邻接矩阵可用一维数组存储。（） 12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（） 13．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（） 14. 有向图的邻接矩阵是对称的。（） 15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使有向图的强连通分量算法
数据结构 第六章 图 练习题及答案详细解析(精华版)
1一个连通的无向图G
求无向连通图的生成树
数据结构 无向图的存储和遍历
图论讲义第7章-平面图
求无向连通图的生成树
求无向连通图的生成树
实习三--求无向连通图的生成树
图的遍历生成树
图练习题
图及其答案
相关主题
文本预览