中南大学离散数学实验报告(实验3ABC).docVIP

“离散数学”实验报告 (实验3ABC) 专 业 班 级 学 号 姓 名 日期：2011.12.19 目录 一、实验目的 3 二、实验内容 3 三、实验环境 3 四、实验原理和实现过程（算法描述） 3 1实验原理 3 2实验过程 5 五、实验数据及结果分析 6 六、源程序清单 10 七、其他收获及体会 16 一、实验目的 理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。 二、实验内容 以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A）。并计算任意两个结点间的距离（B）。对不连通的图输出其各个连通支（C）。 三、实验环境 C或C＋＋语言编程环境实现。 四、实验原理和实现过程（算法描述） 1、实验原理 （1）建立图的邻接矩阵，判断图是否连通 根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。 连通图的定义：在一个无向图 G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。 判断连通图的实现：在图中，从任意点出发在剩余的点中，找到所有相邻点循环，直到没有点可以加入为止，如果有剩余的点就是不连通的，否则就是连通的。或者也可用WallShell算法，由图的邻接矩阵判断图是否连通。 （2）计算任意两个结点间的距离 图中两点i，j间的距离通过检验Al中使得aij为1的最小的l值求出。 路径P中所含边的条数称为路径P的长度。在图GV,E中，从结点Vi到Vj最短路径的长度叫从Vi到Vj的距离，记为dVi，Vj。 设图的邻接矩阵是A，则 所对应的aij的值表示，点Vi到点Vj距离为n的路径有aij条。 若aij(1)，aij(2)，…，aij(n-1)，中至少有一个不为0，则可断定Vi与Vj可达，使aij(l)≠0的最小的l即为d(Vi，Vj)。 问题求解原理为： （1） 先构造初始邻接矩阵A=Vij，Vij为顶点Vi到顶点Vj的权。如果Vi和Vj之间不存在弧段或者是负向回路或者是i=j，则令Vij其值为∞。 （2） 再构造初始中间顶点矩阵。 （3） 然后开始迭代计算（迭代的次数等于顶点的个数1） （4）最后查找Vi到Vj的最短路径。 计算节点Vi与Vj之间的距离的方法为： 利用邻接矩阵相互间相乘后得到的矩阵来判断节点间的距离。如果c2[s][i][j]==0，则这两个节点的距离为无穷大。如果c2[s-2][i][j]==0,c2[s-1][i][j]==1时，则这两点间的距离为s。 （3）对不连通的图输出其各个连通支 图的连通支的求法则可采用图的遍历算法，图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。 在无向图中，如果任何两点可达，则称图G是连通的，如果G的子图G’是连通的，没有包含G’的更大的子图G’’是连通的，则称G’是G的连通支。 当有判断出关系不是连通的之后，将需要求出分支模块 实现方法如下：先定义一个二维数组用来存放相应的分块，先选定一个点，并将它放在数组中，然后判断，如果后面的和他是联通的便将它也放在同一个数组中，否则将其存入其他的数组中，后面以此类推，在输出相应的数组，便可判断出连通分支。 2、实验过程 （1） 程序整体思路 本程序完成了实验所要求的全部功能，其基本思路是——“运用模块化的思想，将实现“求连通支”、“输入结点关系”、“输出邻接矩阵”、“显示两结点间的距离”、“求可达矩阵”和“图的遍历”的子函数分开编写，然后将它们以子函数的形式添加到主函数main的代码后面，在要使用相应的子函数时，进行子函数调用就可以实现相应的功能了。” （2）具体算法流程 …while循环语句和switch语句实现功能1,2,3……的选择，并调用相关的子程序；用start、goto start实现控制流的转移；} liantongzhi(){求连通支，此子函数通过一个for循环控制遍历每个结点，并调用函数DFS（）求每个结点的连通支；} DFS（int a）{通过实参与形参，将结点数据代入函数；定义顺序栈变量；通过for循环初始化；为a置已访问标志，已经访问了的元素为1；定义顺序栈的第一个元素；通过while循环实现结点遍历，栈不为空时执行循环；栈顶元素赋值；通过for循环寻找v的下个未访问的邻接点；通过if条件句，若x,i是边和节点i未被访问过，处理结点的访问，并进行访问标志，进栈等操作；通过if条件句，若v已访问到的出点，则将其退栈；} shuru(){输入结点关系；通过for循环先将矩阵所有元素赋值0；再通过另一for循环，根据输入结点的关