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）。
