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

中国矿业大学
软件开发基础实践报告
姓名: xxs 学号: bbaa0edf
专业: 计算机科学与技术
指导教师: sjc 职称: js


(仅供徐海计算机参考哈哈哈哈)

2012 年 6 月 20 徐州
目录
第一章实验概述 2
实验目的 2
实验内容 2
实验环境 2
第二章实验原理和实现过程 3
实验原理 3
,判断图是否连通 3
计算任意两个结点间的距离 3
4
实验过程(算法描述) 4
程序整体思路 4
4
第三章实验数据及结果分析 6
6
6
7
其他功能的功能测试和结果分析 8
8
8
9
9
第四章实验收获和心得体会 10
实验收获 10
心得体会 11
第五章实验源程序清单 12
程序代码 12
第一章实验概述
实验目的
理解图论的基本概念,图的矩阵表示,图的连通性,图的遍历,以及求图的连通支方法。
通过实验,帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算,培养逻辑思维;通过实验提高学生编写实验报告、总结实验结果的能力,提高理论联系实际的能力;使学生具备程序设计的思想,能够独立完成简单的算法设计和分析。
实验内容
以偶对的形式输入一个无向简单图的边,建立该图的邻接矩阵,判断图是否连通(A),并计算任意两个结点间的距离(B),对不连通的图输出其各个连通支(C)。
注意:题目类型分为A,B,C三类,其中A为基本题,完成A类题目可达到设计的基本要求,其他均为加分题,并按字母顺序分数增加越高。
基本要求如下:程序需具有基本的容错控制,在输入错误时有处理手段;程序界面友好,需要输入的地方有输入说明,说明输入的内容和格式要求等;实验原理和实现过程应该详细分析问题,给出解决思路,描述算法思想,不能用源程序代替算法;测试数据应全面,包括非法输入的处理结果等都应包含在内。
实验环境
C或C++语言编程环境实现。
第二章实验原理和实现过程
实验原理
,判断图是否连通
根据图的矩阵表示法建立邻接矩阵A,并利用矩阵的乘法和加法求出可达矩阵,从而判断图的连通性。
连通图的定义:在一个无向图 G 中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。
判断连通图的实现:在图中,从任意点出发在剩余的点中,找到所有相邻点循环,直到没有点可以加入为止,如果有剩余的点就是不连通的,否则就是连通的。或者也可用WallShell算法,由图的邻接矩阵判断图是否连通。
计算任意两个结点间的距离
图中两点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。

图的连通支的求法则可采用图的遍历算法,图的遍历有深度优先和广度优先两种方法,其中深度优先算法又分为递归和非递归两种。
在无向图中,如果任何两点可达,则称图G是连通的,如果G