《离散数学应用实践》
实验报告
课序号: 07 学 号: 1143041254 姓 名: 发权
任课教师: 瑜
评阅成绩: 评阅意见:
提交报告时间:2012年 12 月 27 日
实验五:判断图是否是树
(一) 问题描述
编写一个程序,从控制台输入一个用邻接矩阵表示的图,程序实现判断该图是不是树,并从控制台输出判断结果。 (二) 实验准备
《离散数学》《数据结构》《Java程序设计语言》 开发环境:eclipse 编程语言:Java
(三) 算法分析
该程序运用的是定理“T连通且m=n-1” “T连通且无圈” “连通且不含圈的图称为数”《离散数学》P226.
实验中,为图的每个的节点设置一个flag标志,标记每个节点是否被访问过,我用广度遍历从其中一个节点开始沿边遍历,如果图是连通的,那无论从哪个顶点开始遍历,每个顶点都会被访问过,既被访问过的节点数=图的节点数。这可以证明图是连通的;
接下来,计算出图的边数m;
继而可以判断m是否等于图的节点数n-1;
“T连通且m=n-1” “T连通且无圈”且不含圈的图称为数”
最终证明图是树。 判断连通性,如图:
A a B b C c
D d (1) (2)
“连通
图(1)中,图是连通的,无论从哪个节点遍历,都能把整个图遍历了,m=n-1;
图(2)中,图是不连通的,对其的遍历要么只遍历c,要么只遍历了abd,m!=n-1。
计算图的边数,如图 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 对图的邻接矩阵进行遍历,计算出边的数目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) { }
public Integer QueueOut() {
capacity=n; qs=new Integer[n];
}
}
int a= (qs[pFront]).intValue(); pFront=(++pFront)êpacity; return a;
public void QueueIn(int n) { }
public Boolean isEmpty() { }
return pBack==pFront; pBack=(pBack++)êpacity; qs[pBack]=new Integer(n);
public void SetElems(Integer[][]elems) { }
public void SetThisElems(String s,int i) {
this.elems=elems;
离散数学应用实践
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)