离散数学应用实践Word文件下载.docx
《离散数学应用实践Word文件下载.docx》由会员分享，可在线阅读，更多相关《离散数学应用实践Word文件下载.docx（10页珍藏版）》请在冰点文库上搜索。
（一）问题描述
编写一个程序，从控制台输入一个用邻接矩阵表示的图，程序实现判断该图是不是树，并从控制台输出判断结果。
（二）实验准备
《离散数学》《数据结构》《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
对图的邻接矩阵进行遍历，计算出边的数目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<
this.vexNum;
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<
i++）
{
if（flag[i]!
=true&
&
elems[a][i]==1）
{
qu.QueueIn（i）;
}
//System.out.println（i）;
}
publicintGetEdgeNum（）//返回一个图的边数
intnum=0;
for（inti=0;
for（intj=0;
if（this.elems[i][j]!
=0）num++;
returnnum/2;
publicbooleanIsConnectedGraph（）//判断一个图是否连通
intn=0;
BFSTraverse（）;
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）;
请输入用邻接矩阵表示的图（"
+e.GetVexNum（）+"
）:
e.GetVexNum（）;
e.SetThisElems（input.nextLine（）,i）;
您输入的图是树吗？
+（e.IsTree（）?
是的！
:
不是！
））;
}
（六）测试数据与运行结果
测试数据：
i.是树的图：
01000
10111
ii.不是数的图：
01100
11000
实验结果：
ii.不是树的图：
（七）算法复杂性分析与讨论
这次试验的理论难点在于程序理论依据，既：
“T连通且m=n-1”
“T连通且无圈”
“连通且不含圈的图称为数”的证明。
实现难点在于图的遍历（本实验用了广度遍历）。
本程序的空间复杂度:
图的邻接矩阵的存储n^2,flag的存储n，既空间复杂度O（n^2）；
时间复杂度为O（n^2）。
升级会员 