離散數(shù)學應用實踐

離散數(shù)學應用實踐離散數(shù)學應用實踐離散數(shù)學應用實踐資料僅供參考文件編號：2022年4月離散數(shù)學應用實踐版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：《離散數(shù)學應用實踐》實驗報告課序號：07學號：54 姓名：姚發(fā)權 任課教師：陳瑜 評閱成績： 評閱意見： 提交報告時間：2012年12月27日實驗五：判斷圖是否是樹問題描述編寫一個程序，從控制臺輸入一個用鄰接矩陣表示的圖，程序實現(xiàn)判斷該圖是不是樹，并從控制臺輸出判斷結果。實驗準備《離散數(shù)學》《數(shù)據(jù)結構》《Java程序設計語言》開發(fā)環(huán)境：eclipse編程語言：Java算法分析該程序運用的是定理“T連通且m=n-1”“T連通且無圈”“連通且不含圈的圖稱為數(shù)”《離散數(shù)學》P226.實驗中，為圖的每個的節(jié)點設置一個flag標志，標記每個節(jié)點是否被訪問過，我用廣度遍歷從其中一個節(jié)點開始沿邊遍歷，如果圖是連通的，那無論從哪個頂點開始遍歷，每個頂點都會被訪問過，既被訪問過的節(jié)點數(shù)=圖的節(jié)點數(shù)。這可以證明圖是連通的；接下來，計算出圖的邊數(shù)m；繼而可以判斷m是否等于圖的節(jié)點數(shù)n-1；“T連通且m=n-1”“T連通且無圈”“連通且不含圈的圖稱為數(shù)”最終證明圖是樹。判斷連通性，如圖：AaBbCcDd（2）圖（1）中，圖是連通的，無論從哪個節(jié)點遍歷，都能把整個圖遍歷了，m=n-1；圖（2）中，圖是不連通的，對其的遍歷要么只遍歷c，要么只遍歷了abd，m！=n-1。計算圖的邊數(shù)，如圖10110001001110000011對圖的鄰接矩陣進行遍歷，計算出邊的數(shù)目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()//返回一個圖的邊數(shù) { 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(); "請輸入圖中節(jié)點的數(shù)目：\n"); @SuppressWarnings("resource") Scannerinput=newScanner; Stringis=(); intn=(is); (n); "請輸入用鄰接矩陣表示的圖("+()+"x"+()+"):\n"); for(inti=0;i<();i++) { (),i); } "您輸入的圖是樹嗎"

+()

"是的！\n":"不是！\n")); }}測試數(shù)據(jù)與運行結果測試數(shù)據(jù)：是樹的圖：0100010111010000100001000不是數(shù)的圖：0110010111110000100001000實驗結果：是樹的圖：不是樹的圖：算法