《离散数学实验3报告讲解.doc》由会员分享，可在线阅读，更多相关《离散数学实验3报告讲解.doc（15页珍藏版）》请在三一文库上搜索。
1、实验报告目录第一章 实验概述 .31.1实验目的 .31.2实验内容 .31.3实验环境 .3第二章 实验原理和实现过程 .42.1实验原理 .42.1.1建立图的邻接矩阵，判断图是否连通 .42.1.2计算任意两个结点间的距离 .42.1.3对不连通的图输出其各个连通支 .52.2实验过程（算法描述） .52.2.1程序整体思路 .52.2.2具体算法流程 .5第三章 实验数据及结果分析 .73.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析.73.1.1输入无向图的边 .73.1.2建立图的连接矩阵 .83.2其他功能的功能测试和结果分析 .93.2.1计算节点间的距离 .93.2
2、.2判断图的连通性 .93.2.3输出图的连通支 .103.2.4退出系统 .10第四章 实验收获和心得体会 .114.1实验收获 .114.2心得体会 .12第五章实验源程序清单 .13I5.1 程序代码13II第一章实验概述1.1 实验目的理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、 性质和运算，培养逻辑思维；通过实验提高学生编写实验报告、 总结实验结果的能力，提高理论联系实际的能力； 使学生具备程序设计的思想， 能够独立完成简单的算法设计和分析。1.2 实验内容以偶对的形式输入一个无向简单
3、图的边，建立该图的邻接矩阵， 判断图是否连通（ A），并计算任意两个结点间的距离 （ B），对不连通的图输出其各个连通支 （C）。注意：题目类型分为 A，B，C三类，其中 A 为基本题，完成 A 类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。基本要求如下： 程序需具有基本的容错控制， 在输入错误时有处理手段； 程序界面友好，需要输入的地方有输入说明， 说明输入的内容和格式要求等； 实验原理和实现过程应该详细分析问题， 给出解决思路， 描述算法思想， 不能用源程序代替算法；测试数据应全面，包括非法输入的处理结果等都应包含在内。1.3 实验环境C或 C语言编程环境实现。3第
4、二章实验原理和实现过程2.1 实验原理建立图的邻接矩阵，判断图是否连通根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。连通图的定义： 在一个无向图 G 中，若从顶点 vi 到顶点 vj 有路径相连 ( 当然从 vj 到 vi 也一定有路径 ) ，则称 vi 和 vj 是连通的。如果 G 是有向图，那么连接vi 和 vj 的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。判断连通图的实现：在图中，从任意点出发在剩余的点中， 找到所有相邻点循环，直到没有点可以加入为止， 如果有剩余的点就是不连通的， 否则就是连通的。 或者也可用
5、WallShell 算法，由图的邻接矩阵判断图是否连通。计算任意两个结点间的距离l ajil 值求出。的最小的中使得 图中两点，为间的距离通过检验 A1ij 路径 P 中所含边的条数称为路径 P 的长度。在图 G<V,E>中，从结点 Vi 到 Vj 最短路径的长度叫从 Vi 到 Vj 的距离，记为 d<Vi， Vj> 。设图的邻接矩阵是 A，则 所对应的 aij 的值表示，点 Vi 到点 Vj 距离为 n 的路径有 aij 条。(1)(2)(n-1) ，中至少有一个不为0，则可断定 Viaij 与 Vj 若 aij可达，aij ， (l) 0 的最小的 l 即为 d(V
6、i ，使 aijVj) 。问题求解原理为：（ 1） 先构造初始邻接矩阵 A=Vij ，Vij为顶点 Vi 到顶点 Vj 的权。如果 Vi 和Vj 之间不存在弧段或者是负向回路或者是i=j ，则令 Vij其值为。（ 2） 再构造初始中间顶点矩阵。（ 3） 然后开始迭代计算（迭代的次数等于顶点的个数1）（ 4）最后查找 Vi 到 Vj 的最短路径。4计算节点 Vi 与 Vj 之间的距离的方法为：利用邻接矩阵相互间相乘后得到的矩阵来判断节点间的距离。如果c2sij=0，则这两个节点的距离为无穷大。如果c2s-2ij=0,c2s-1ij=1时，则这两点间的距离为s。对不连通的图输出其各个连通支图的连通
7、支的求法则可采用图的遍历算法， 图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。在无向图中，如果任何两点可达，则称图 G是连通的，如果 G的子图 G'是连通的，没有包含 G' 的更大的子图 G'' 是连通的，则称 G' 是 G的连通支。当有判断出关系不是连通的之后，将需要求出分支模块实现方法如下： 先定义一个二维数组用来存放相应的分块， 先选定一个点， 并将它放在数组中，然后判断，如果后面的和他是联通的便将它也放在同一个数组中，否则将其存入其他的数组中， 后面以此类推， 在输出相应的数组， 便可判断出连通分支。2.2 实验过
8、程（算法描述）程序整体思路本程序完成了实验所要求的全部功能， 其基本思路是 “运用模块化的思想，将实现“求连通支”、“输入结点关系”、“输出邻接矩阵”、“显示两结点间的距离” 、“求可达矩阵”和“图的遍历”的子函数分开编写，然后将它们以子函数的形式添加到主函数 main 的代码后面，在要使用相应的子函数时，进行子函数调用就可以实现相应的功能了。 ”本程序的一大特色就是开发者灵活使用了 C 语言中的数组概念来进行开发， 用数组来模拟矩阵的运算，通过相应的算法实现了全部的功能。具体算法流程在 main()系统界面显示；用 dowhile 循环语句和 switch 语句实现功能 1,2,3 的选择，
9、并调用相关的子程序；用 start 、goto start 实现控制流的转移； 循环控制遍历每个结点，并调求连通支，此子函数通过一个 liantongzhi()for 用函数 DFS（）求每个结点的连通支； 5DFS（int a）通过实参与形参，将结点数据代入函数；定义顺序栈变量；通过 for 循环初始化；为 a 置已访问标志，已经访问了的元素为 1；定义顺序栈的第一个元素；通过 while 循环实现结点遍历，栈不为空时执行循环； 栈顶元素赋值；通过 for 循环寻找 v 的下个未访问的邻接点；通过 if 条件句，若 x,i 是边和节点 i未被访问过，处理结点的访问，并进行访问标志，进栈等操作
10、；通过if 条件句，若 v 已访问到的出点，则将其退栈；shuru()输入结点关系；通过for 循环先将矩阵所有元素赋值0；再通过另一 for循环，根据输入结点的关系，将矩阵中相应的元素赋值，有关系则为1； 依次按格式输出邻接矩阵的元素； 通过 for 循环， linjiejuzhen() 输出邻接矩阵；次方矩阵及其中元素， 判断并显示两结点间的距离； nA 的 根据 julijuzhen()调用子函数 linjiejuzhen()，以确定并显示距离为 1 的两结点；通过 for 循环显示距离为 1 的结点对；再通过一系列的 for 循环，计算 A 的 n 次方矩阵并显示结果，根据其中的元素，
11、判断并显示结点间的距离； 详细算法请见附录相关部分的注释； kedajuzhen()求可达矩阵；通过一系列for 循环，根据公式，计算可达矩阵；通过 for 循环，将矩阵中不为 0 的一切值赋为 1 以生成可达矩阵并显示；通过 for 循环和 if 条件句的组合， 根据可达矩阵的元素特点， 判断图的连通性， 若可达矩阵矩阵中有 0，则跳出循环，显示不可连接；根据判断结果显示内容，不可连通或可连通； 6第三章实验数据及结果分析3.1 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析简单无向图的输入界面友好，有清楚的操作说明，方便用户进行使用。这就是集合的输入界面。输入无向图的边 ，表示输入的
12、是六个节点五条边的树。 6,5 ”时 当“； 1,2； 2,33,4 程序会在屏幕上显示输入节点间关系的界面，输入的关系为“ ”；4,55,67建立图的连接矩阵”，程序会显示建立的连接矩阵。 2 程序返回主界面后，选择“83.2 其他功能的功能测试和结果分析计算节点间的距离当选择“ 3”时，程序便会输出各节点间的距离。判断图的连通性”时，程序会根据可达矩阵判断图的连通性。 4 当选择 “9输出图的连通支当选择“ 5”时，程序会输出个连通支。退出系统”时，程序会退出系统。6 当选择“10第四章实验收获和心得体会4.1 实验收获这次离散数学实验是基于图论方面知识， 以图的各种矩阵为基础， 来研究图
13、的一些性质、特点。我独立完成了本次实验设计， 实现了 A、B、C 三个功能，满足了实验的基本要求，心得如下。通过这次实验，我学会了用C语言根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。巩固了课堂所学的ij间的距离可以通过检验，图论方面的有关知识，并在实践中学到：图中两点l al值求出；图的连通支的求法可采用图的遍历算法，1 中使得的最小的A 为 ij 图的遍历有深度优先和广度优先两种方法， 其中深度优先算法又分为递归和非递归两种。我选择的算法是较为简单、 易于实现的深度优先算法最简单， 查阅了相关资料，掌握了此算法的核心，最后独立完成了本次实验设计。
14、这次离散数学实验， 从拿到题目到完成整个编程， 从理论到实践的日子里， 我学到很多东西， 不仅可以巩固了以前所学过的知识， 而且通过查阅相关资料， 学到了很多在书本上所没有学到过的知识。 在这段时间里， 我对于离散数学中的 “逻辑”有了进一步的理解，对 C 语言的理解也更进了一步， 并提高了编写实验报告、总结实验结果的能力，提高了理论联系实际的能力，初步具备程序设计的思想，能够独立完成简单的算法设计和分析。感受最深的是，大量的上机实践是成为“编程高手”的必由之路， “质变”需要有“量”的积累。完成程序的编写， 决不意味着万事大吉。 曾经自己认为万无一失的程序， 实际上机运行时可能不断出现麻烦，
15、 如编译程序检测出一大堆错误。 有时程序本身不存在语法错误， 也能够顺利运行， 但是运行结果显然是错误的。 开发环境所提供的编译系统无法发现这种程序逻辑错误， 只能靠自己的上机经验分析判断错误所在。有时候一个小小错误会消耗我好的时间去找， 而高手一眼就看出错误所在， 这就是熟练程度的不同，量变到质变的不同。114.2 心得体会这次真的使我意识到了很多原来没有意识到的问题， 有时候一些很小的问题， 也会令人很是头痛。在刚开始编写程序的时候， 为了实现最基本的输入和输出功能， 我却花了大量的时间在那上面。 原因在后来查阅的很多资料后才知道的， 像 scanf 函数之类的小函数，其实是还有很多需要注
16、意的地方的。之后，在编写数组和指针的过程中， 花了很大的一部分时间去研发算法， 开发程序，在理论上反复证明没有问题之后，再在计算机上进行操作，编写代码，进行调试，反复了很久，才慢慢的实现了全部的功能，真的是来之不易。在实验的过程中我们要培养自己的独立分析问题，和解决问题的能力。培养这种能力的前题是你对每次实验的态度。 如果你在实验这方面很随便， 抱着等老师教你怎么做，拿同学的报告去抄，尽管你的成绩会很高，但对将来工作是不利的。在写实验报告，对于思考题，有很多不懂，于是去问老师，老师的启发了我，其实答案早就摆在报告中的公式，电路图中，自己要学会思考。最后，通过这次的实验我不但对理论知识有了更加深
17、的理解， 对于实际的操作和也有了质的飞跃。经过这次的实验，我们整体对各个方面都得到了不少的提高，希望以后学校和系里能够开设更多类似的实验，能够让我们得到更好的锻炼。12第五章实验源程序清单5.1 程序代码#include <stdio.h>/* 头文件 */#include<stdlib.h>#include <math.h>#define MAX 100/* 宏定义 */typedef struct int elemMAX;int top;SqStack;/* 定义栈的结构体,顺序栈的类型标识符*/void shuru();/* 各子函数声明*/void
18、linjiejuzhen();void julijuzhen();void kedajuzhen();void liantongzhi();void DFS(int a);int A99,B99,C99,D99;int i,j,k,t,v,e;int main()int a1;13start:do);printf(* *n););ttt系统主菜单 n);tt1.输入无向图的边ntt2.建立图的邻接矩阵ntt3.计算节点间的距离n);t4. 由可达矩阵判断图的连通性ntt5.输出各个连通支（深度优先DFS法）ntt6.退出系统 n););printf(* *n););tttt请输入功能选项:);
19、fflush(stdin);/*清空输入缓冲区，通常是为了确保不影响后面的数据读取*/scanf(%d,&a1);switch(a1)/*switch语句实现选择功能*/case 1:system(cls);shuru();break;/*输入节点关系，计算邻接矩阵*/case 2:system(cls);fflush(stdin);linjiejuzhen();break;/*输出邻接矩阵*/case 3:system(cls);fflush(stdin);julijuzhen();break;/* case 4:system(cls);fflush(stdin);kedajuzhe
20、n();break;/*求距离矩阵求可达矩阵*/*/14case 5:system(cls);fflush(stdin);liantongzhi();break;/*case 6:system(exit);exit(0);/*结束整个程序的运行default:system(cls);*/求连通支*/goto start;/*控制流转移到start处 */while(1);*/ 求连通支，此子函数控制遍历每个结点 void liantongzhi()/* for(i=1;i<=v;i+)printf(%d,i);DFS(i);/* 调用子函数求连通支*/);*/ void DFS(int
21、a)/* 由深度优先法求出并显示各个连通支DFSint i,x;int top=0;int visitedMAX;*/ SqStack s;/* 为顺序栈变量定义 sfor (i=0;i<100;i+)visitedi=0;/*初始化为0*/15visiteda -1=1;/*为 a 置已访问标志，已经访问了的元素为1*/top=top+1;s.elemtop=a -1;/*顺序栈的第一个元素*/while(top!=0)/*栈不为空时执行循环*/x=s.elemtop;/* for(i=0;i<v;i+)/*将栈顶元素付给x*/寻找v 的下个未访问的邻接点*/if(Dxi!=0
22、&&(!visitedi)/*若 x,i 是边和节点i 未被访问过*/printf( ->%d,i+1);visitedi=1;/* 为i 置已访问标准*/top=top+1;s.elemtop=i;/*i进栈*/break;if(i=v)/* 若 v 已访问到的出点，则将其退栈*/top -;*/ void shuru()/*输入结点关系printf(* *n););16t请输入结点数和边数（形式如6,5 ）： n);输入结点和边数*/ scanf(%d,%d,&v,&e);/* 0*/for(i=0;i<v;i+)/*初始赋值否为for(j=0;
23、j<v;j+)Aij=0;Cij=0;Bij=0;Dij=0;);printf(* *n);t请输入结点间的关系（形式如：1,2 ）： n););for(k=0;k<e;k+)/* 根据输入的关系，确定邻接矩阵中数值*/scanf(%d,%d,&i,&j);Ai-1j -1=1;/* 根据输入结点的关系，将矩阵中相应的元素赋值*/Aj-1i -1=1;Bi-1j -1=1;Bj-1i -1=1;Di -1j -1=1;17Dj -1i -1=1;system(cls);*/输出邻接矩阵void linjiejuzhen()/* 牰湩晴尨邻接矩阵A 为：n);for(
24、i=0;i<v;i+)for(j=0;j<v;j+),Aij);/*显示邻接矩阵*/););*/根据 void julijuzhen()/*An的次方矩阵及其中元素，判断并显示两结点间的距离*/的两结点1 linjiejuzhen();/*调用子函数，以确定并显示距离为for(i=1;i<=v;i+)for(j=1;j<=v;j+)18if(Ai -1j -1=1)牰湩晴尨 结点 %d 与结点 %d的距离为：%dn,i,j,1);*/for(k=2;k<=v -1;k+)/* 计算并显示距离大于1 的两节点n);A%d)为：n,k,k);即 距离为牰湩晴尨%d 的
25、矩阵 ( for(i=0;i<v;i+)for(j=0;j<v;j+)for(t=0;t<v;t+)Cij=Cij+Bit*Atj;/*计算矩阵中的元素*/for(i=0;i<v;i+)for(j=0;j<v;j+)Bij=Cij;/*将计算出的结果赋予B矩阵 */Cij=0;for(i=0;i<v;i+)19for(j=0;j<v;j+),Bij);/*显示距离矩阵*/););for(i=1;i<=v;i+)for(j=1;j<=v;j+)if(Ai -1j -1=0 && Bi -1j -1 != 0 &&
26、; i!=j)/*判断条件，以确定输出对象（相关的点）*/牰湩晴尨结点%d 与结点 %d 的距离为：%dn,i,j,k););*/ void kedajuzhen()/*求可达矩阵int l=1;牰湩晴尨可达矩阵为：n);*/for(i=0;i<v;i+)/* 初始矩阵赋值for(j=0;j<v;j+)Bij=Aij;20Cij=0;for(k=0;k<v;k+)for(i=0;i<v;i+)for(j=0;j<v;j+)for(t=0;t<v;t+)Cij=Cij+Bit*Atj;/*根据公式计算可达矩阵*/for(i=0;i<v;i+)for(j=
27、0;j<v;j+)Dij=Cij+Dij;/*根据公式计算可达矩阵*/for(i=0;i<v;i+)for(j=0;j<v;j+)Bij=Cij;/*根据公式计算可达矩阵*/Cij=0;for(i=0;i<v;i+)21for(j=0;j<v;j+)if(Dij>=1)/*将矩阵中不为0 的一切值赋为1 以生成可达矩阵*/Dij=1;for(i=0;i<v;i+)for(j=0;j<v;j+),Dij);/*显示可达矩阵*/);for(i=0;i<v;i+)for(j=0;j<v;j+)/*根据可达矩阵的元素特点，判断图的连通性*/if(Dij = 0)/*若可达矩阵矩阵中有0，则跳出循环，显示不可连接*/l=0;break;*/tttt根据上一步判断结果显示内容该图不连通！if(l=0)/*);else);tttt该图可连通！22