離散數學應用實踐離散數學應用實踐離散數學應用實踐xxx公司離散數學應用實踐文件編號：文件日期：修訂次數：第1.0次更改批準審核制定方案設計，管理制度《離散數學應用實踐》實驗報告課序號：07學號：54 姓名：姚發權 任課教師：陳瑜 評閱成績： 評閱意見： 提交報告時間：2012年12月27日實驗五：判斷圖是否是樹問題描述編寫一個程序，從控制臺輸入一個用鄰接矩陣表示的圖，程序實現判斷該圖是不是樹，并從控制臺輸出判斷結果。實驗準備《離散數學》《數據結構》《Java程序設計語言》開發環境：eclipse編程語言：Java算法分析該程序運用的是定理“T連通且m=n-1”“T連通且無圈”“連通且不含圈的圖稱為數”《離散數學》P226.實驗中，為圖的每個的節點設置一個flag標志，標記每個節點是否被訪問過，我用廣度遍歷從其中一個節點開始沿邊遍歷，如果圖是連通的，那無論從哪個頂點開始遍歷，每個頂點都會被訪問過，既被訪問過的節點數=圖的節點數。這可以證明圖是連通的；接下來，計算出圖的邊數m；繼而可以判斷m是否等于圖的節點數n-1；“T連通且m=n-1”“T連通且無圈”“連通且不含圈的圖稱為數”最終證明圖是樹。判斷連通性，如圖：AaBbCcDd（2）圖（1）中，圖是連通的，無論從哪個節點遍歷，都能把整個圖遍歷了，m=n-1；圖（2）中，圖是不連通的，對其的遍歷要么只遍歷c，要么只遍歷了abd，m！=n-1。計算圖的邊數，如圖10110001001110000011對圖的鄰接矩陣進行遍歷，計算出邊的數目m；程序源代碼importclassisTree{ privateInteger[][]elems;ntValue(); pFront=(++pFront)%capacity; returna; } publicvoidQueueIn(intn) { pBack=(pBack++)%capacity; qs[pBack]=newInteger(n); } publicBooleanisEmpty() { returnpBack==pFront; } } publicvoidSetElems(Integer[][]elems) { =elems; } publicvoidSetThisElems(Strings,inti) { for(intj=0;j<;j++) { elems[i][j]=(""+(j)); } } publicvoidSetNum(intvexNum) { =vexNum; elems=newInteger[vexNum][vexNum]; flag=newBoolean[vexNum]; } publicInteger[][]GetElems() { return; } publicBoolean[]GetFlag() { return; } publicintGetVexNum() { return; } publicvoidBFSTraverse()//對圖的廣度遍歷 { Queuequ=newQueue; (0); while(!()) { //"x"); inta=(); flag[a]=true; for(inti=0;i<;i++) { if(flag[i]!=true&&elems[a][i]==1) { (i); } // } } } publicintGetEdgeNum()//返回一個圖的邊數 { intnum=0; for(inti=0;i<;i++) { for(intj=0;j<;j++) { if[i][j]!=0)num++; } } returnnum/2; } publicbooleanIsConnectedGraph()//判斷一個圖是否連通 { intn=0; BFSTraverse(); for(inti=0;i<;i++) { if[i]=true)n++; } returnn==; } publicbooleanIsTree() { booleanb=IsConnectedGraph(); intn=GetEdgeNum(); returnb&&(n==; } publicisTree(){ //TODOAuto-generatedconstructorstub elems=newInteger[20][20]; flag=newBoolean[20]; vexNum=20; } /** *@paramargs */ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub isTreee=newisTree(); "請輸入圖中節點的數目：\n"); @SuppressWarnings("resource") Scannerinput=newScanner; Stringis=(); intn=(is); (n); "請輸入用鄰接矩陣表示的圖("+()+"x"+()+"):\n"); for(inti=0;i<();i++) { (),i); } "您輸入的圖是樹嗎"+()"是的！\n":"不是！\n")); }}測試數據與運行結果測試數據：是樹的圖：0100010111010000100001000不是數的圖：0110010111110000100001000實驗結果：是樹的圖：不是樹的圖：算法復雜性