1、离散数学应用实践离散数学应用实践实验报告课序号: 07 学 号: 1143041254 姓 名: 姚发权 任课教师: 陈瑜 评阅成绩: 评阅意见: 提交报告时间:2012年 12 月 27 日实验五:判断图是否是树(一) 问题描述编写一个程序,从控制台输入一个用邻接矩阵表示的图,程序实现判断该图是不是树,并从控制台输出判断结果。(二) 实验准备离散数学数据结构Java程序设计语言开发环境:eclipse编程语言:Java(三) 算法分析(四) 该程序运用的是定理“T连通且m=n-1” “T连通且无圈” “连通且不含圈的图称为数”离散数学P226.实验中,为图的每个的节点设置一个flag标志,标
2、记每个节点是否被访问过,我用广度遍历从其中一个节点开始沿边遍历,如果图是连通的,那无论从哪个顶点开始遍历,每个顶点都会被访问过,既被访问过的节点数=图的节点数。这可以证明图是连通的;接下来,计算出图的边数m;继而可以判断m是否等于图的节点数n-1; “T连通且m=n-1” “T连通且无圈”“连通且不含圈的图称为数”最终证明图是树。判断连通性,如图:A aB bC cD d(1) (2)图(1)中,图是连通的,无论从哪个节点遍历,都能把整个图遍历了,m=n-1;图(2)中,图是不连通的,对其的遍历要么只遍历c,要么只遍历了abd,m!=n-1。计算图的边数,如图10110001001110000
3、011对图的邻接矩阵进行遍历,计算出边的数目m;(五) 程序源代码import java.util.Scanner;public class isTree private Integer elems;/图的邻接矩阵表示 private Boolean flag;/对元素是否被访问进行标记 private int vexNum;/图的顶点数 private class Queue/队列 private Integer qs; private int capacity; private int pFront=0; private int pBack=0; public Queue(int n) c
4、apacity=n; qs=new Integern; public Integer QueueOut() int a= (qspFront).intValue(); pFront=(+pFront)%capacity; return a; public void QueueIn(int n) pBack=(pBack+)%capacity; qspBack=new Integer(n); public Boolean isEmpty() return pBack=pFront; public void SetElems(Integerelems) this.elems=elems; publ
5、ic void SetThisElems(String s,int i) for(int j=0;jthis.vexNum;j+) elemsij=Integer.parseInt(+s.charAt(j); public void SetNum(int vexNum) this.vexNum=vexNum; elems=new IntegervexNumvexNum; flag=new BooleanvexNum; public Integer GetElems() return this.elems; public Boolean GetFlag() return this.flag; p
6、ublic int GetVexNum() return this.vexNum; public void BFSTraverse()/对图的广度遍历 Queue qu=new Queue(this.vexNum); qu.QueueIn(0); while(!qu.isEmpty() /System.out.println(x); int a=qu.QueueOut(); flaga=true; for(int i=0;ithis.vexNum;i+) if(flagi!=true&elemsai=1) qu.QueueIn(i); /System.out.println(i); publi
7、c int GetEdgeNum()/返回一个图的边数 int num=0; for(int i=0;ithis.vexNum;i+) for(int j=0;jthis.vexNum;j+) if(this.elemsij!=0)num+; return num/2; public boolean IsConnectedGraph()/判断一个图是否连通 int n=0; BFSTraverse(); for(int i=0;ithis.vexNum;i+) if(this.flagi=true)n+; return n=this.vexNum; public boolean IsTree(
8、) boolean b=IsConnectedGraph(); int n=GetEdgeNum(); return b&(n=this.vexNum-1); public isTree() / TODO Auto-generated constructor stub elems=new Integer2020; flag=new Boolean20; vexNum=20; /* * param args */ public static void main(String args) / TODO Auto-generated method stub isTree e=new isTree()
9、; System.out.printf(请输入图中节点的数目:n); SuppressWarnings(resource) Scanner input=new Scanner(System.in); String is=input.nextLine(); int n=Integer.parseInt(is); e.SetNum(n); System.out.printf(请输入用邻接矩阵表示的图 (+e.GetVexNum()+x+e.GetVexNum()+):n); for(int i=0;ie.GetVexNum();i+) e.SetThisElems(input.nextLine()
10、, i); System.out.printf(您输入的图是树吗?+(e.IsTree()?是的!n:不是!n); (六) 测试数据与运行结果测试数据:i. 是树的图:0100010111010000100001000ii. 不是数的图:0110010111110000100001000实验结果:i. 是树的图:ii. 不是树的图:(七) 算法复杂性分析与讨论这次试验的理论难点在于程序理论依据,既:“T连通且m=n-1”“T连通且无圈”“连通且不含圈的图称为数”的证明。实现难点在于图的遍历(本实验用了广度遍历)。本程序的空间复杂度:图的邻接矩阵的存储n2,flag的存储n,既空间复杂度O(n2);时间复杂度为O(n2)。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2