离散数学课程设计.图的矩阵表示与基本运算

..中国矿业大学软件开发基础实践报__xxs学号：bbaa0edf专业：计算机科学与技术指导sjc职称：js<仅供徐海计算机参考哈哈哈哈>2012年6月20XX目录第一章实验概述21.1实验目的21.2实验内容21.3实验环境2第二章实验原理和实现过程32.1实验原理3建立图的邻接矩阵,判断图是否连通32.1.2计算任意两个结点间的距离3对不连通的图输出其各个连通支42.2实验过程〔算法描述42.2.1程序整体思路4具体算法流程4第三章实验数据及结果分析63.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析6输入无向图的边6建立图的连接矩阵73.2其他功能的功能测试和结果分析8计算节点间的距离8判断图的连通性8输出图的连通支9退出系统9第四章实验收获和心得体会104.1实验收获104.2心得体会11第五章实验源程序清单125.1程序代码12..第一章实验概述1.1实验目的理解图论的基本概念,图的矩阵表示,图的连通性,图的遍历,以及求图的连通支方法。通过实验,帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算,培养逻辑思维；通过实验提高学生编写实验报告、总结实验结果的能力,提高理论联系实际的能力；使学生具备程序设计的思想,能够独立完成简单的算法设计和分析。1.2实验内容以偶对的形式输入一个无向简单图的边,建立该图的邻接矩阵,判断图是否连通〔A,并计算任意两个结点间的距离〔B,对不连通的图输出其各个连通支〔C。注意：题目类型分为A,B,C三类,其中A为基本题,完成A类题目可达到设计的基本要求,其他均为加分题,并按字母顺序分数增加越高。基本要求如下：程序需具有基本的容错控制,在输入错误时有处理手段；程序界面友好,需要输入的地方有输入说明,说明输入的内容和格式要求等；实验原理和实现过程应该详细分析问题,给出解决思路,描述算法思想,不能用源程序代替算法；测试数据应全面,包括非法输入的处理结果等都应包含在内。1.3实验环境C或C＋＋语言编程环境实现。第二章实验原理和实现过程2.1实验原理2.1.1建立图的邻接矩阵,判断图是否连通根据图的矩阵表示法建立邻接矩阵A,并利用矩阵的乘法和加法求出可达矩阵,从而判断图的连通性。连通图的定义：在一个无向图G中,若从顶点vi到顶点vj有路径相连<当然从vj到vi也一定有路径>,则称vi和vj是连通的。如果G是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。 判断连通图的实现：在图中,从任意点出发在剩余的点中,找到所有相邻点循环,直到没有点可以加入为止,如果有剩余的点就是不连通的,否则就是连通的。或者也可用WallShell算法,由图的邻接矩阵判断图是否连通。2.1.2计算任意两个结点间的距离图中两点i,j间的距离通过检验Al中使得aij为1的最小的l值求出。路径P中所含边的条数称为路径P的长度。在图G<V,E>中,从结点Vi到Vj最短路径的长度叫从Vi到Vj的距离,记为d<Vi,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。2.1.3对不连通的图输出其各个连通支图的连通支的求法则可采用图的遍历算法,图的遍历有深度优先和广度优先两种方法,其中深度优先算法又分为递归和非递归两种。在无向图中,如果任何两点可达,则称图G是连通的,如果G的子图G’是连通的,没有包含G’的更大的子图G’’是连通的,则称G’是G的连通支。当有判断出关系不是连通的之后,将需要求出分支模块实现方法如下：先定义一个二维数组用来存放相应的分块,先选定一个点,并将它放在数组中,然后判断,如果后面的和他是联通的便将它也放在同一个数组中,否则将其存入其他的数组中,后面以此类推,在输出相应的数组,便可判断出连通分支。2.2实验过程〔算法描述2.2.1程序整体思路本程序完成了实验所要求的全部功能,其基本思路是——"运用模块化的思想,将实现"求连通支"、"输入结点关系"、"输出邻接矩阵"、"显示两结点间的距离"、"求可达矩阵"和"图的遍历"的子函数分开编写,然后将它们以子函数的形式添加到主函数main的代码后面,在要使用相应的子函数时,进行子函数调用就可以实现相应的功能了。"本程序的一大特色就是开发者灵活使用了C语言中的数组概念来进行开发,用数组来模拟矩阵的运算,通过相应的算法实现了全部的功能。2.2.2具体算法流程 在main<>{系统界面显示；用do…while循环语句和switch语句实现功能1,2,3……的选择,并调用相关的子程序；用start、gotostart实现控制流的转移；} liantongzhi<>{求连通支,此子函数通过一个for循环控制遍历每个结点,并调用函数DFS〔求每个结点的连通支；} DFS〔inta{通过实参与形参,将结点数据代入函数；定义顺序栈变量；通过for循环初始化；为a置已访问标志,已经访问了的元素为1；定义顺序栈的第一个元素；通过while循环实现结点遍历,栈不为空时执行循环；栈顶元素赋值；通过for循环寻找v的下个未访问的邻接点；通过if条件句,若x,i是边和节点i未被访问过,处理结点的访问,并进行访问标志,进栈等操作；通过if条件句,若v已访问到的出点,则将其退栈；} shuru<>{输入结点关系；通过for循环先将矩阵所有元素赋值0；再通过另一for循环,根据输入结点的关系,将矩阵中相应的元素赋值,有关系则为1；} linjiejuzhen<>{输出邻接矩阵；通过for循环,依次按格式输出邻接矩阵的元素；} julijuzhen<>{根据A的n次方矩阵及其中元素,判断并显示两结点间的距离；调用子函数linjiejuzhen<>,以确定并显示距离为1的两结点；通过for循环显示距离为1的结点对；再通过一系列的for循环,计算A的n次方矩阵并显示结果,根据其中的元素,判断并显示结点间的距离；详细算法请见附录相关部分的注释；} kedajuzhen<>{求可达矩阵；通过一系列for循环,根据公式,计算可达矩阵；通过for循环,将矩阵中不为0的一切值赋为1以生成可达矩阵并显示；通过for循环和if条件句的组合,根据可达矩阵的元素特点,判断图的连通性,若可达矩阵矩阵中有0,则跳出循环,显示不可连接；根据判断结果显示内容,不可连通或可连通；}第三章实验数据及结果分析3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析简单无向图的输入界面友好,有清楚的操作说明,方便用户进行使用。这就是集合的输入界面。3.1.1输入无向图的边当"6,5"时,表示输入的是六个节点五条边的树。程序会在屏幕上显示输入节点间关系的界面,输入的关系为"1,2；2,3；3,4；4,5；5,6"3.1.2建立图的连接矩阵程序返回主界面后,选择"2",程序会显示建立的连接矩阵。3.2其他功能的功能测试和结果分析3.2.1计算节点间的距离 当选择"3"时,程序便会输出各节点间的距离。3.2.2判断图的连通性当选择"4"时,程序会根据可达矩阵判断图的连通性。3.2.3输出图的连通支当选择"5"时,程序会输出个连通支。3.2.4退出系统当选择"6"时,程序会退出系统。第四章实验收获和心得体会4.1实验收获这次离散数学实验是基于图论方面知识,以图的各种矩阵为基础,来研究图的一些性质、特点。我独立完成了本次实验设计,实现了A、B、C三个功能,满足了实验的基本要求,心得如下。通过这次实验,我学会了用C语言根据图的矩阵表示法建立邻接矩阵A,并利用矩阵的乘法和加法求出可达矩阵,从而判断图的连通性。巩固了课堂所学的图论方面的有关知识,并在实践中学到：图中两点i,j间的距离可以通过检验Al中使得aij为1的最小的l值求出；图的连通支的求法可采用图的遍历算法,图的遍历有深度优先和广度优先两种方法,其中深度优先算法又分为递归和非递归两种。我选择的算法是较为简单、易于实现的深度优先算法最简单,查阅了相关资料,掌握了此算法的核心,最后独立完成了本次实验设计。这次离散数学实验,从拿到题目到完成整个编程,从理论到实践的日子里,我学到很多东西,不仅可以巩固了以前所学过的知识,而且通过查阅相关资料,学到了很多在书本上所没有学到过的知识。在这段时间里,我对于离散数学中的"逻辑"有了进一步的理解,对C语言的理解也更进了一步,并提高了编写实验报告、总结实验结果的能力,提高了理论联系实际的能力,初步具备程序设计的思想,能够独立完成简单的算法设计和分析。感受最深的是,大量的上机实践是成为"编程高手"的必由之路,"质变"需要有"量"的积累。完成程序的编写,决不意味着万事大吉。曾经自己认为万无一失的程序,实际上机运行时可能不断出现麻烦,如编译程序检测出一大堆错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。有时候一个小小错误会消耗我好的时间去找,而高手一眼就看出错误所在,这就是熟练程度的不同,量变到质变的不同。4.2心得体会这次真的使我意识到了很多原来没有意识到的问题,有时候一些很小的问题,也会令人很是头痛。在刚开始编写程序的时候,为了实现最基本的输入和输出功能,我却花了大量的时间在那上面。原因在后来查阅的很多资料后才知道的,像scanf函数之类的小函数,其实是还有很多需要注意的地方的。之后,在编写数组和指针的过程中,花了很大的一部分时间去研发算法,开发程序,在理论上反复证明没有问题之后,再在计算机上进行操作,编写代码,进行调试,反复了很久,才慢慢的实现了全部的功能,真的是来之不易。在实验的过程中我们要培养自己的独立分析问题,和解决问题的能力。培养这种能力的前题是你对每次实验的态度。如果你在实验这方面很随便,抱着等老师教你怎么做,拿同学的报告去抄,尽管你的成绩会很高,但对将来工作是不利的。在写实验报告,对于思考题,有很多不懂,于是去问老师,老师的启发了我,其实答案早就摆在报告中的公式,电路图中,自己要学会思考。最后,通过这次的实验我不但对理论知识有了更加深的理解,对于实际的操作和也有了质的飞跃。经过这次的实验,我们整体对各个方面都得到了不少的提高,希望以后学校和系里能够开设更多类似的实验,能够让我们得到更好的锻炼。第五章实验源程序清单5.1程序代码#include<stdio.h>/*头文件*/#include<stdlib.h>#include<math.h>#defineMAX100/*宏定义*/typedefstruct{intelem[MAX];inttop;}SqStack;/*定义栈的结构体,顺序栈的类型标识符*/voidshuru<>;/*各子函数声明*/voidlinjiejuzhen<>;voidjulijuzhen<>;voidkedajuzhen<>;voidliantongzhi<>;voidDFS<inta>;intA[9][9],B[9][9],C[9][9],D[9][9];inti,j,k,t,v,e;intmain<>{ inta1; start: do { printf<"\n">; printf<"*******************************************************************************\n">; printf<"\n">; printf<"\t\t\t\t系统主菜单\n">; printf<"\n\t\t1.输入无向图的边\n\t\t2.建立图的邻接矩阵\n\t\t3.计算节点间的距离\n">; printf<"\t\t4.由可达矩阵判断图的连通性\n\t\t5.输出各个连通支〔深度优先DFS法\n\t\t6.退出系统\n">; printf<"\n">; printf<"********************************************************************************\n">; printf<"\n">; printf<"\n\t\t\t\t请输入功能选项:">; fflush<stdin>;/*清空输入缓冲区,通常是为了确保不影响后面的数据读取*/ scanf<"%d",&a1>; switch<a1>/*switch语句实现选择功能*/ { case1:system<"cls">;shuru<>;break;/*输入节点关系,计算邻接矩阵*/ case2:system<"cls">;fflush<stdin>;linjiejuzhen<>;break;/*输出邻接矩阵*/ case3:system<"cls">;fflush<stdin>;julijuzhen<>;break;/*求距离矩阵*/ case4:system<"cls">;fflush<stdin>;kedajuzhen<>;break;/*求可达矩阵*/ case5:system<"cls">;fflush<stdin>;liantongzhi<>;break;/*求连通支*/ case6:system<"exit">;exit<0>;/*结束整个程序的运行*/ default:system<"cls">; gotostart;/*控制流转移到start处*/ } }while<1>;}voidliantongzhi<>/*求连通支,此子函数控制遍历每个结点*/{ for<i=1;i<=v;i++> { printf<"%d",i>; DFS<i>;/*调用子函数求连通支*/ printf<"\n">; }}voidDFS<inta>/*由深度优先DFS法求出并显示各个连通支*/{ inti,x; inttop=0; intvisited[MAX]; SqStacks;/*定义s为顺序栈变量*/ for<i=0;i<100;i++> visited[i]=0;/*初始化为0*/ visited[a-1]=1;/*为a置已访问标志,已经访问了的元素为1*/ top=top+1; s.elem[top]=a-1;/*顺序栈的第一个元素*/ while<top!=0>/*栈不为空时执行循环*/ { x=s.elem[top];/*将栈顶元素付给x*/ for<i=0;i<v;i++>/*寻找v的下个未访问的邻接点*/ if<D[x][i]!=0&&<!visited[i]>>/*若x,i是边和节点i未被访问过*/ { printf<"->%d",i+1>; visited[i]=1;/*为i置已访问标准*/ top=top+1; s.elem[top]=i;/*i进栈*/ break; } if<i==v>/*若v已访问到的出点,则将其退栈*/ top--; }}voidshuru<>/*输入结点关系*/{ printf<"*******************************************************************************\n">; printf<"\n">; printf<"\t\t请输入结点数和边数〔形式如6,5：\n">; scanf<"%d,%d",&v,&e>;/*输入结点和边数*/ for<i=0;i<v;i++>/*初始赋值否为0*/ { for<j=0;j<v;j++> { A[i][j]=0; C[i][j]=0; B[i][j]=0; D[i][j]=0; } } printf<"\n">; printf<"*******************************************************************************\n">; printf<"\t\t请输入结点间的关系〔形式如：1,2：\n">; printf<"\n">; for<k=0;k<e;k++>/*根据输入的关系,确定邻接矩阵中数值*/ { scanf<"%d,%d",&i,&j>; A[i-1][j-1]=1;/*根据输入结点的关系,将矩阵中相应的元素赋值*/ A[j-1][i-1]=1; B[i-1][j-1]=1; B[j-1][i-1]=1; D[i-1][j-1]=1; D[j-1][i-1]=1; } system<"cls">;}voidlinjiejuzhen<>/*输出邻接矩阵*/{ printf<"邻接矩阵A为：\n">; for<i=0;i<v;i++> { for<j=0;j<v;j++> { printf<"\t%5d",A[i][j]>;/*显示邻接矩阵*/ } printf<"\n">; } printf<"\n">; }voidjulijuzhen<>/*根据A的n次方矩阵及其中元素,判断并显示两结点间的距离*/{ linjiejuzhen<>;/*调用子函数,以确定并显示距离为1的两结点*/ for<i=1;i<=v;i++> { for<j=1;j<=v;j++> { if<A[i-1][j-1]==1> printf<"结点%d与结点%d的距离为：%d\n",i,j,1>; } } for<k=2;k<=v-1;k++>/*计算并显示距离大于1的两节点*/ { printf<"\n\n">; printf<"距离为%d的矩阵<即A%d>为：\n",k,k>; { for<i=0;i<v;i++> for<j=0;j<v;j++> { for<t=0;t<v;t++> C[i][j]=C[i][j]+B[i][t]*A[t][j];/*计算矩阵中的元素*/ } for<i=0;i<v;i++> for<j=0;j<v;j++> { B[i][j]=C[i][j];/*将计算出的结果赋予B矩阵*/ C[i][j]=0; } } for<i=0;i<v;i++> { for<j=0;j<v;j++> printf<"\t%5d",B[i][j]>;/*显示距离矩阵*/ printf<"\n">; } printf<"\n">; for<i=1;i<=v;i++> for<j=1;j<=v;j++> { if<A[i-1][j-1]==0&&B[i-1][j-1]!=0&&i!=j>/*判断条件,以确定输出对象〔相关的点*/ printf<"结点%d与结点%d的距离为：%d\n",i,j,k>; } } printf<"\n">;}voidkedajuzhen<>/*求可达矩阵*/{ intl=1; printf<"可达矩阵为：\n">; for<i=0;i<v;i++>/*初始矩阵赋值*/ for<j=0;j<v;j++> { B[i][j]=A[i][j]; C[i][j]=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++> C[i][j]=C[i][j]+B[i][t]*A[t][j];/*根据公式计算可达矩阵*/ } for<i=0;i<v;i++> for<j=0;j<v;j++> { D[i][j]=C[i][j]+D[i][j];/*根据公式计算可达矩阵*/ } for<i=0;i<v;i++> for<j=0;j<v;j++> { B[i][j]=C[i][j];/*根据公式计算可达矩阵*/ C[i][j]=0; } } for<i=0;i<v;i++> { for<j=0;j<v;j++> if<D[i][j]>=1>/*将矩阵中不为0的一切值赋为1以生成可达矩阵*/ D[i][j]=1; } for<i=0;i<v;i++> { for<j=0;j<v;j++> printf<"\t%5d",D[i][j]>;/*显示可达矩阵*/ printf<"\n">; } for<i=0;i<v;i++> { for<j=0;j<v;j++>/*根据可达矩阵的元素特点,判断图的连通性*/ if<D[i][j]==0>/*若可达矩阵矩阵中有0,则跳出循环,显示不可连接*/