离散数学应用实践.docx
《离散数学应用实践.docx》由会员分享，可在线阅读，更多相关《离散数学应用实践.docx（10页珍藏版）》请在冰点文库上搜索。
离散数学应用实践
《离散数学应用实践》
实验报告
课序号：
07
学号：
1143041254
姓名：
姚发权
任课教师：
陈瑜
评阅成绩：
评阅意见：
提交报告时间：
2012年12月27日
实验五：
判断图是否是树
（一）问题描述
编写一个程序，从控制台输入一个用邻接矩阵表示的图，程序实现判断该图是不是树，并从控制台输出判断结果。
（二）实验准备
《离散数学》《数据结构》《Java程序设计语言》
开发环境：
eclipse
编程语言：
Java
（三）算法分析
（四）
该程序运用的是定理“T连通且m=n-1”“T连通且无圈”“连通且不含圈的图称为数”《离散数学》P226.
实验中，为图的每个的节点设置一个flag标志，标记每个节点是否被访问过，我用广度遍历从其中一个节点开始沿边遍历，如果图是连通的，那无论从哪个顶点开始遍历，每个顶点都会被访问过，既被访问过的节点数=图的节点数。
这可以证明图是连通的；
接下来，计算出图的边数m；
继而可以判断m是否等于图的节点数n-1；
“T连通且m=n-1”“T连通且无圈”
“连通且不含圈的图称为数”
最终证明图是树。
判断连通性，如图：
Aa
Bb
Cc
Dd
（1）
（2）
图
（1）中，图是连通的，无论从哪个节点遍历，都能把整个图遍历了，m=n-1；
图
（2）中，图是不连通的，对其的遍历要么只遍历c，要么只遍历了abd，m！
=n-1。
计算图的边数，如图
1
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
1
对图的邻接矩阵进行遍历，计算出边的数目m；
（五）程序源代码
importjava.util.Scanner;
publicclassisTree{
privateInteger[][]elems;//图的邻接矩阵表示
privateBoolean[]flag;//对元素是否被访问进行标记
privateintvexNum;//图的顶点数
privateclassQueue//队列
{
privateInteger[]qs;
privateintcapacity;
privateintpFront=0;
privateintpBack=0;
publicQueue（intn）
{
capacity=n;
qs=newInteger[n];
}
publicIntegerQueueOut（）
{
inta=（qs[pFront]）.intValue（）;
pFront=（++pFront）%capacity;
returna;
}
publicvoidQueueIn（intn）
{
pBack=（pBack++）%capacity;
qs[pBack]=newInteger（n）;
}
publicBooleanisEmpty（）
{
returnpBack==pFront;
}
}
publicvoidSetElems（Integer[][]elems）
{
this.elems=elems;
}
publicvoidSetThisElems（Strings,inti）
{
for（intj=0;j{
elems[i][j]=Integer.parseInt（""+s.charAt（j））;
}
}
publicvoidSetNum（intvexNum）
{
this.vexNum=vexNum;
elems=newInteger[vexNum][vexNum];
flag=newBoolean[vexNum];
}
publicInteger[][]GetElems（）
{
returnthis.elems;
}
publicBoolean[]GetFlag（）
{
returnthis.flag;
}
publicintGetVexNum（）
{
returnthis.vexNum;
}
publicvoidBFSTraverse（）//对图的广度遍历
{
Queuequ=newQueue（this.vexNum）;
qu.QueueIn（0）;
while（!
qu.isEmpty（））
{
//System.out.println（"x"）;
inta=qu.QueueOut（）;
flag[a]=true;
for（inti=0;i{
if（flag[i]!
=true&&elems[a][i]==1）
{
qu.QueueIn（i）;
}
//System.out.println（i）;
}
}
}
publicintGetEdgeNum（）//返回一个图的边数
{
intnum=0;
for（inti=0;i{
for（intj=0;j{
if（this.elems[i][j]!
=0）num++;
}
}
returnnum/2;
}
publicbooleanIsConnectedGraph（）//判断一个图是否连通
{
intn=0;
BFSTraverse（）;
for（inti=0;i{
if（this.flag[i]=true）n++;
}
returnn==this.vexNum;
}
publicbooleanIsTree（）
{
booleanb=IsConnectedGraph（）;
intn=GetEdgeNum（）;
returnb&&（n==this.vexNum-1）;
}
publicisTree（）{
//TODOAuto-generatedconstructorstub
elems=newInteger[20][20];
flag=newBoolean[20];
vexNum=20;
}
/**
*@paramargs
*/
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
isTreee=newisTree（）;
System.out.printf（"请输入图中节点的数目：
\n"）;
@SuppressWarnings（"resource"）
Scannerinput=newScanner（System.in）;
Stringis=input.nextLine（）;
intn=Integer.parseInt（is）;
e.SetNum（n）;
System.out.printf（"请输入用邻接矩阵表示的图（"+e.GetVexNum（）+"x"+e.GetVexNum（）+"）:
\n"）;
for（inti=0;i{
e.SetThisElems（input.nextLine（）,i）;
}
System.out.printf（"您输入的图是树吗？
"+（e.IsTree（）?
"是的！
\n":
"不是！
\n"））;
}
}
（六）测试数据与运行结果
测试数据：
i.是树的图：
01000
10111
01000
01000
01000
ii.不是数的图：
01100
10111
11000
01000
01000
实验结果：
i.是树的图：
ii.不是树的图：
（七）算法复杂性分析与讨论
这次试验的理论难点在于程序理论依据，既：
“T连通且m=n-1”
“T连通且无圈”
“连通且不含圈的图称为数”的证明。
实现难点在于图的遍历（本实验用了广度遍历）。
本程序的空间复杂度:
图的邻接矩阵的存储n^2,flag的存储n，既空间复杂度O（n^2）；
时间复杂度为O（n^2）。
升级会员 