离散数学应用实践

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。计算图的边数，如图10110001001110000011对图的邻接矩阵进行遍历，计算

3、出边的数目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)capacity=n;qs=new Integern;

4、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;public void SetThisElems(String s,int i)for

5、(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;public int GetVexNum()return this.vexNum;public voi

6、d 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);public int GetEdgeNum()/返回一个图的边数int num=0;for(int i=0;ithis.vexNum;i

7、+)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()boolean b=IsConnectedGraph();int n=GetEdgeNum();return b&(n=this.vexNum-1)

8、;public isTree() / TODO Auto-generated constructor stubelems=new Integer2020;flag=new Boolean20;vexNum=20;/* * param args */public static void main(String args) / TODO Auto-generated method stubisTree e=new isTree();System.out.printf(请输入图中节点的数目：n);SuppressWarnings(resource)Scanner input=new Scanner(

9、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(), i);System.out.printf(您输入的图是树吗？+(e.IsTree()?是的！n:不是！n);（五） 测试数据与运行结果测试数据：i. 是树的图：0100010111010000100001000ii. 不是数的图：0110010111110000100001000实验结果：i. 是树的图：ii. 不是树的图：（六）