版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
離散數(shù)學應用實踐離散數(shù)學應用實踐離散數(shù)學應用實踐資料僅供參考文件編號:2022年4月離散數(shù)學應用實踐版本號:A修改號:1頁次:1.0審核:批準:發(fā)布日期:《離散數(shù)學應用實踐》實驗報告課序號:07學號:54 姓名:姚發(fā)權(quán) 任課教師:陳瑜 評閱成績: 評閱意見: 提交報告時間:2012年12月27日實驗五:判斷圖是否是樹問題描述編寫一個程序,從控制臺輸入一個用鄰接矩陣表示的圖,程序?qū)崿F(xiàn)判斷該圖是不是樹,并從控制臺輸出判斷結(jié)果。實驗準備《離散數(shù)學》《數(shù)據(jù)結(jié)構(gòu)》《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ù)與運行結(jié)果測試數(shù)據(jù):是樹的圖:0100010111010000100001000不是數(shù)的圖:0110010111110000100001000實驗結(jié)果:是樹的圖:不是樹的圖:算法
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年西安客運證模擬考試題庫答案解析
- 邢臺市廣宗縣2024年數(shù)學四年級第一學期期末達標檢測模擬試題含解析
- 2024年朝陽駕駛員貨運從業(yè)資格證考試題
- 徐州市沛縣2025屆四上數(shù)學期末質(zhì)量跟蹤監(jiān)視模擬試題含解析
- 煙臺市長島縣2025屆數(shù)學六年級第一學期期末質(zhì)量檢測模擬試題含解析
- 領航信息安全未來
- 承債轉(zhuǎn)讓合同(2篇)
- 代理權(quán)轉(zhuǎn)讓合同協(xié)議書范本(2篇)
- 1.3安防機器人的制作實踐(第二課時)(課件)-九年級信息技術(shù)下冊課堂(川教2019版)
- 北歐會所案例研究報告
- 《地形圖的判讀》課件-2024-2025學年人教版(2024)地理七年級上冊
- 曹沖稱象 任務一走進古代兒童感受曹沖巧思考 公開課一等獎創(chuàng)新教學設計
- 2024年新滬科大版七年級上冊數(shù)學教學課件 第1章 小結(jié)與復習
- 2024年全國職業(yè)院校技能大賽高職組(智能節(jié)水系統(tǒng)設計與安裝賽項)考試題庫-上(單選題)
- 新能源汽車維修服務合同協(xié)議
- 織夢系統(tǒng)多站點集群架構(gòu)設計與實現(xiàn)
- 2024兵器工業(yè)集團招聘1人(高頻重點提升專題訓練)共500題附帶答案詳解
- Unit 1 Section A(1a-Pronunciation)課件人教版2024新教材七年級上冊英語
- 2024江蘇溧水區(qū)區(qū)級機關鎮(zhèn)(街)招聘編外人員56人(高頻重點提升專題訓練)共500題附帶答案詳解
- 人教版(2024新教材)七年級上冊數(shù)學第一次月考測試卷(含答案)
評論
0/150
提交評論