離散數(shù)學課程設(shè)計.圖的矩陣表示與基本運算

..中國礦業(yè)大學軟件開發(fā)基礎(chǔ)實踐報__xxs學號：bbaa0edf專業(yè)：計算機科學與技術(shù)指導sjc職稱：js<僅供徐海計算機參考哈哈哈哈>2012年6月20XX目錄第一章實驗概述21.1實驗目的21.2實驗內(nèi)容21.3實驗環(huán)境2第二章實驗原理和實現(xiàn)過程32.1實驗原理3建立圖的鄰接矩陣,判斷圖是否連通32.1.2計算任意兩個結(jié)點間的距離3對不連通的圖輸出其各個連通支42.2實驗過程〔算法描述42.2.1程序整體思路4具體算法流程4第三章實驗數(shù)據(jù)及結(jié)果分析63.1建立圖的鄰接矩陣并判斷圖是否連通的功能測試及結(jié)果分析6輸入無向圖的邊6建立圖的連接矩陣73.2其他功能的功能測試和結(jié)果分析8計算節(jié)點間的距離8判斷圖的連通性8輸出圖的連通支9退出系統(tǒng)9第四章實驗收獲和心得體會104.1實驗收獲104.2心得體會11第五章實驗源程序清單125.1程序代碼12..第一章實驗概述1.1實驗目的理解圖論的基本概念,圖的矩陣表示,圖的連通性,圖的遍歷,以及求圖的連通支方法。通過實驗,幫助學生更好地掌握計算機科學技術(shù)常用的離散數(shù)學中的概念、性質(zhì)和運算,培養(yǎng)邏輯思維；通過實驗提高學生編寫實驗報告、總結(jié)實驗結(jié)果的能力,提高理論聯(lián)系實際的能力；使學生具備程序設(shè)計的思想,能夠獨立完成簡單的算法設(shè)計和分析。1.2實驗內(nèi)容以偶對的形式輸入一個無向簡單圖的邊,建立該圖的鄰接矩陣,判斷圖是否連通〔A,并計算任意兩個結(jié)點間的距離〔B,對不連通的圖輸出其各個連通支〔C。注意：題目類型分為A,B,C三類,其中A為基本題,完成A類題目可達到設(shè)計的基本要求,其他均為加分題,并按字母順序分數(shù)增加越高?；疽笕缦拢撼绦蛐杈哂谢镜娜蒎e控制,在輸入錯誤時有處理手段；程序界面友好,需要輸入的地方有輸入說明,說明輸入的內(nèi)容和格式要求等；實驗原理和實現(xiàn)過程應該詳細分析問題,給出解決思路,描述算法思想,不能用源程序代替算法；測試數(shù)據(jù)應全面,包括非法輸入的處理結(jié)果等都應包含在內(nèi)。1.3實驗環(huán)境C或C＋＋語言編程環(huán)境實現(xiàn)。第二章實驗原理和實現(xiàn)過程2.1實驗原理2.1.1建立圖的鄰接矩陣,判斷圖是否連通根據(jù)圖的矩陣表示法建立鄰接矩陣A,并利用矩陣的乘法和加法求出可達矩陣,從而判斷圖的連通性。連通圖的定義：在一個無向圖G中,若從頂點vi到頂點vj有路徑相連<當然從vj到vi也一定有路徑>,則稱vi和vj是連通的。如果G是有向圖,那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的,那么圖被稱作連通圖。 判斷連通圖的實現(xiàn)：在圖中,從任意點出發(fā)在剩余的點中,找到所有相鄰點循環(huán),直到?jīng)]有點可以加入為止,如果有剩余的點就是不連通的,否則就是連通的?；蛘咭部捎肳allShell算法,由圖的鄰接矩陣判斷圖是否連通。2.1.2計算任意兩個結(jié)點間的距離圖中兩點i,j間的距離通過檢驗Al中使得aij為1的最小的l值求出。路徑P中所含邊的條數(shù)稱為路徑P的長度。在圖G<V,E>中,從結(jié)點Vi到Vj最短路徑的長度叫從Vi到Vj的距離,記為d<Vi,Vj>。設(shè)圖的鄰接矩陣是A,則所對應的aij的值表示,點Vi到點Vj距離為n的路徑有aij條。若aij<1>,aij<2>,…,aij<n-1>,中至少有一個不為0,則可斷定Vi與Vj可達,使aij<l>≠0的最小的l即為d<Vi,Vj>。問題求解原理為：〔1先構(gòu)造初始鄰接矩陣A=Vij,Vij為頂點Vi到頂點Vj的權(quán)。如果Vi和Vj之間不存在弧段或者是負向回路或者是i=j,則令Vij其值為∞?！?再構(gòu)造初始中間頂點矩陣?！?然后開始迭代計算〔迭代的次數(shù)等于頂點的個數(shù)1〔4最后查找Vi到Vj的最短路徑。計算節(jié)點Vi與Vj之間的距離的方法為：利用鄰接矩陣相互間相乘后得到的矩陣來判斷節(jié)點間的距離。如果c2[s][i][j]==0,則這兩個節(jié)點的距離為無窮大。如果c2[s-2][i][j]==0,c2[s-1][i][j]==1時,則這兩點間的距離為s。2.1.3對不連通的圖輸出其各個連通支圖的連通支的求法則可采用圖的遍歷算法,圖的遍歷有深度優(yōu)先和廣度優(yōu)先兩種方法,其中深度優(yōu)先算法又分為遞歸和非遞歸兩種。在無向圖中,如果任何兩點可達,則稱圖G是連通的,如果G的子圖G’是連通的,沒有包含G’的更大的子圖G’’是連通的,則稱G’是G的連通支。當有判斷出關(guān)系不是連通的之后,將需要求出分支模塊實現(xiàn)方法如下：先定義一個二維數(shù)組用來存放相應的分塊,先選定一個點,并將它放在數(shù)組中,然后判斷,如果后面的和他是聯(lián)通的便將它也放在同一個數(shù)組中,否則將其存入其他的數(shù)組中,后面以此類推,在輸出相應的數(shù)組,便可判斷出連通分支。2.2實驗過程〔算法描述2.2.1程序整體思路本程序完成了實驗所要求的全部功能,其基本思路是——"運用模塊化的思想,將實現(xiàn)"求連通支"、"輸入結(jié)點關(guān)系"、"輸出鄰接矩陣"、"顯示兩結(jié)點間的距離"、"求可達矩陣"和"圖的遍歷"的子函數(shù)分開編寫,然后將它們以子函數(shù)的形式添加到主函數(shù)main的代碼后面,在要使用相應的子函數(shù)時,進行子函數(shù)調(diào)用就可以實現(xiàn)相應的功能了。"本程序的一大特色就是開發(fā)者靈活使用了C語言中的數(shù)組概念來進行開發(fā),用數(shù)組來模擬矩陣的運算,通過相應的算法實現(xiàn)了全部的功能。2.2.2具體算法流程 在main<>{系統(tǒng)界面顯示；用do…while循環(huán)語句和switch語句實現(xiàn)功能1,2,3……的選擇,并調(diào)用相關(guān)的子程序；用start、gotostart實現(xiàn)控制流的轉(zhuǎn)移；} liantongzhi<>{求連通支,此子函數(shù)通過一個for循環(huán)控制遍歷每個結(jié)點,并調(diào)用函數(shù)DFS〔求每個結(jié)點的連通支；} DFS〔inta{通過實參與形參,將結(jié)點數(shù)據(jù)代入函數(shù)；定義順序棧變量；通過for循環(huán)初始化；為a置已訪問標志,已經(jīng)訪問了的元素為1；定義順序棧的第一個元素；通過while循環(huán)實現(xiàn)結(jié)點遍歷,棧不為空時執(zhí)行循環(huán)；棧頂元素賦值；通過for循環(huán)尋找v的下個未訪問的鄰接點；通過if條件句,若x,i是邊和節(jié)點i未被訪問過,處理結(jié)點的訪問,并進行訪問標志,進棧等操作；通過if條件句,若v已訪問到的出點,則將其退棧；} shuru<>{輸入結(jié)點關(guān)系；通過for循環(huán)先將矩陣所有元素賦值0；再通過另一for循環(huán),根據(jù)輸入結(jié)點的關(guān)系,將矩陣中相應的元素賦值,有關(guān)系則為1；} linjiejuzhen<>{輸出鄰接矩陣；通過for循環(huán),依次按格式輸出鄰接矩陣的元素；} julijuzhen<>{根據(jù)A的n次方矩陣及其中元素,判斷并顯示兩結(jié)點間的距離；調(diào)用子函數(shù)linjiejuzhen<>,以確定并顯示距離為1的兩結(jié)點；通過for循環(huán)顯示距離為1的結(jié)點對；再通過一系列的for循環(huán),計算A的n次方矩陣并顯示結(jié)果,根據(jù)其中的元素,判斷并顯示結(jié)點間的距離；詳細算法請見附錄相關(guān)部分的注釋；} kedajuzhen<>{求可達矩陣；通過一系列for循環(huán),根據(jù)公式,計算可達矩陣；通過for循環(huán),將矩陣中不為0的一切值賦為1以生成可達矩陣并顯示；通過for循環(huán)和if條件句的組合,根據(jù)可達矩陣的元素特點,判斷圖的連通性,若可達矩陣矩陣中有0,則跳出循環(huán),顯示不可連接；根據(jù)判斷結(jié)果顯示內(nèi)容,不可連通或可連通；}第三章實驗數(shù)據(jù)及結(jié)果分析3.1建立圖的鄰接矩陣并判斷圖是否連通的功能測試及結(jié)果分析簡單無向圖的輸入界面友好,有清楚的操作說明,方便用戶進行使用。這就是集合的輸入界面。3.1.1輸入無向圖的邊當"6,5"時,表示輸入的是六個節(jié)點五條邊的樹。程序會在屏幕上顯示輸入節(jié)點間關(guān)系的界面,輸入的關(guān)系為"1,2；2,3；3,4；4,5；5,6"3.1.2建立圖的連接矩陣程序返回主界面后,選擇"2",程序會顯示建立的連接矩陣。3.2其他功能的功能測試和結(jié)果分析3.2.1計算節(jié)點間的距離 當選擇"3"時,程序便會輸出各節(jié)點間的距離。3.2.2判斷圖的連通性當選擇"4"時,程序會根據(jù)可達矩陣判斷圖的連通性。3.2.3輸出圖的連通支當選擇"5"時,程序會輸出個連通支。3.2.4退出系統(tǒng)當選擇"6"時,程序會退出系統(tǒng)。第四章實驗收獲和心得體會4.1實驗收獲這次離散數(shù)學實驗是基于圖論方面知識,以圖的各種矩陣為基礎(chǔ),來研究圖的一些性質(zhì)、特點。我獨立完成了本次實驗設(shè)計,實現(xiàn)了A、B、C三個功能,滿足了實驗的基本要求,心得如下。通過這次實驗,我學會了用C語言根據(jù)圖的矩陣表示法建立鄰接矩陣A,并利用矩陣的乘法和加法求出可達矩陣,從而判斷圖的連通性。鞏固了課堂所學的圖論方面的有關(guān)知識,并在實踐中學到：圖中兩點i,j間的距離可以通過檢驗Al中使得aij為1的最小的l值求出；圖的連通支的求法可采用圖的遍歷算法,圖的遍歷有深度優(yōu)先和廣度優(yōu)先兩種方法,其中深度優(yōu)先算法又分為遞歸和非遞歸兩種。我選擇的算法是較為簡單、易于實現(xiàn)的深度優(yōu)先算法最簡單,查閱了相關(guān)資料,掌握了此算法的核心,最后獨立完成了本次實驗設(shè)計。這次離散數(shù)學實驗,從拿到題目到完成整個編程,從理論到實踐的日子里,我學到很多東西,不僅可以鞏固了以前所學過的知識,而且通過查閱相關(guān)資料,學到了很多在書本上所沒有學到過的知識。在這段時間里,我對于離散數(shù)學中的"邏輯"有了進一步的理解,對C語言的理解也更進了一步,并提高了編寫實驗報告、總結(jié)實驗結(jié)果的能力,提高了理論聯(lián)系實際的能力,初步具備程序設(shè)計的思想,能夠獨立完成簡單的算法設(shè)計和分析。感受最深的是,大量的上機實踐是成為"編程高手"的必由之路,"質(zhì)變"需要有"量"的積累。完成程序的編寫,決不意味著萬事大吉。曾經(jīng)自己認為萬無一失的程序,實際上機運行時可能不斷出現(xiàn)麻煩,如編譯程序檢測出一大堆錯誤。有時程序本身不存在語法錯誤,也能夠順利運行,但是運行結(jié)果顯然是錯誤的。開發(fā)環(huán)境所提供的編譯系統(tǒng)無法發(fā)現(xiàn)這種程序邏輯錯誤,只能靠自己的上機經(jīng)驗分析判斷錯誤所在。有時候一個小小錯誤會消耗我好的時間去找,而高手一眼就看出錯誤所在,這就是熟練程度的不同,量變到質(zhì)變的不同。4.2心得體會這次真的使我意識到了很多原來沒有意識到的問題,有時候一些很小的問題,也會令人很是頭痛。在剛開始編寫程序的時候,為了實現(xiàn)最基本的輸入和輸出功能,我卻花了大量的時間在那上面。原因在后來查閱的很多資料后才知道的,像scanf函數(shù)之類的小函數(shù),其實是還有很多需要注意的地方的。之后,在編寫數(shù)組和指針的過程中,花了很大的一部分時間去研發(fā)算法,開發(fā)程序,在理論上反復證明沒有問題之后,再在計算機上進行操作,編寫代碼,進行調(diào)試,反復了很久,才慢慢的實現(xiàn)了全部的功能,真的是來之不易。在實驗的過程中我們要培養(yǎng)自己的獨立分析問題,和解決問題的能力。培養(yǎng)這種能力的前題是你對每次實驗的態(tài)度。如果你在實驗這方面很隨便,抱著等老師教你怎么做,拿同學的報告去抄,盡管你的成績會很高,但對將來工作是不利的。在寫實驗報告,對于思考題,有很多不懂,于是去問老師,老師的啟發(fā)了我,其實答案早就擺在報告中的公式,電路圖中,自己要學會思考。最后,通過這次的實驗我不但對理論知識有了更加深的理解,對于實際的操作和也有了質(zhì)的飛躍。經(jīng)過這次的實驗,我們整體對各個方面都得到了不少的提高,希望以后學校和系里能夠開設(shè)更多類似的實驗,能夠讓我們得到更好的鍛煉。第五章實驗源程序清單5.1程序代碼#include<stdio.h>/*頭文件*/#include<stdlib.h>#include<math.h>#defineMAX100/*宏定義*/typedefstruct{intelem[MAX];inttop;}SqStack;/*定義棧的結(jié)構(gòu)體,順序棧的類型標識符*/voidshuru<>;/*各子函數(shù)聲明*/voidlinjiejuzhen<>;voidjulijuzhen<>;voidkedajuzhen<>;voidliantongzhi<>;voidDFS<inta>;intA[9][9],B[9][9],C[9][9],D[9][9];inti,j,k,t,v,e;intmain<>{ inta1; start: do { printf<"\n">; printf<"*******************************************************************************\n">; printf<"\n">; printf<"\t\t\t\t系統(tǒng)主菜單\n">; printf<"\n\t\t1.輸入無向圖的邊\n\t\t2.建立圖的鄰接矩陣\n\t\t3.計算節(jié)點間的距離\n">; printf<"\t\t4.由可達矩陣判斷圖的連通性\n\t\t5.輸出各個連通支〔深度優(yōu)先DFS法\n\t\t6.退出系統(tǒng)\n">; printf<"\n">; printf<"********************************************************************************\n">; printf<"\n">; printf<"\n\t\t\t\t請輸入功能選項:">; fflush<stdin>;/*清空輸入緩沖區(qū),通常是為了確保不影響后面的數(shù)據(jù)讀取*/ scanf<"%d",&a1>; switch<a1>/*switch語句實現(xiàn)選擇功能*/ { case1:system<"cls">;shuru<>;break;/*輸入節(jié)點關(guān)系,計算鄰接矩陣*/ case2:system<"cls">;fflush<stdin>;linjiejuzhen<>;break;/*輸出鄰接矩陣*/ case3:system<"cls">;fflush<stdin>;julijuzhen<>;break;/*求距離矩陣*/ case4:system<"cls">;fflush<stdin>;kedajuzhen<>;break;/*求可達矩陣*/ case5:system<"cls">;fflush<stdin>;liantongzhi<>;break;/*求連通支*/ case6:system<"exit">;exit<0>;/*結(jié)束整個程序的運行*/ default:system<"cls">; gotostart;/*控制流轉(zhuǎn)移到start處*/ } }while<1>;}voidliantongzhi<>/*求連通支,此子函數(shù)控制遍歷每個結(jié)點*/{ for<i=1;i<=v;i++> { printf<"%d",i>; DFS<i>;/*調(diào)用子函數(shù)求連通支*/ printf<"\n">; }}voidDFS<inta>/*由深度優(yōu)先DFS法求出并顯示各個連通支*/{ inti,x; inttop=0; intvisited[MAX]; SqStacks;/*定義s為順序棧變量*/ for<i=0;i<100;i++> visited[i]=0;/*初始化為0*/ visited[a-1]=1;/*為a置已訪問標志,已經(jīng)訪問了的元素為1*/ top=top+1; s.elem[top]=a-1;/*順序棧的第一個元素*/ while<top!=0>/*棧不為空時執(zhí)行循環(huán)*/ { x=s.elem[top];/*將棧頂元素付給x*/ for<i=0;i<v;i++>/*尋找v的下個未訪問的鄰接點*/ if<D[x][i]!=0&&<!visited[i]>>/*若x,i是邊和節(jié)點i未被訪問過*/ { printf<"->%d",i+1>; visited[i]=1;/*為i置已訪問標準*/ top=top+1; s.elem[top]=i;/*i進棧*/ break; } if<i==v>/*若v已訪問到的出點,則將其退棧*/ top--; }}voidshuru<>/*輸入結(jié)點關(guān)系*/{ printf<"*******************************************************************************\n">; printf<"\n">; printf<"\t\t請輸入結(jié)點數(shù)和邊數(shù)〔形式如6,5：\n">; scanf<"%d,%d",&v,&e>;/*輸入結(jié)點和邊數(shù)*/ for<i=0;i<v;i++>/*初始賦值否為0*/ { for<j=0;j<v;j++> { A[i][j]=0; C[i][j]=0; B[i][j]=0; D[i][j]=0; } } printf<"\n">; printf<"*******************************************************************************\n">; printf<"\t\t請輸入結(jié)點間的關(guān)系〔形式如：1,2：\n">; printf<"\n">; for<k=0;k<e;k++>/*根據(jù)輸入的關(guān)系,確定鄰接矩陣中數(shù)值*/ { scanf<"%d,%d",&i,&j>; A[i-1][j-1]=1;/*根據(jù)輸入結(jié)點的關(guān)系,將矩陣中相應的元素賦值*/ A[j-1][i-1]=1; B[i-1][j-1]=1; B[j-1][i-1]=1; D[i-1][j-1]=1; D[j-1][i-1]=1; } system<"cls">;}voidlinjiejuzhen<>/*輸出鄰接矩陣*/{ printf<"鄰接矩陣A為：\n">; for<i=0;i<v;i++> { for<j=0;j<v;j++> { printf<"\t%5d",A[i][j]>;/*顯示鄰接矩陣*/ } printf<"\n">; } printf<"\n">; }voidjulijuzhen<>/*根據(jù)A的n次方矩陣及其中元素,判斷并顯示兩結(jié)點間的距離*/{ linjiejuzhen<>;/*調(diào)用子函數(shù),以確定并顯示距離為1的兩結(jié)點*/ for<i=1;i<=v;i++> { for<j=1;j<=v;j++> { if<A[i-1][j-1]==1> printf<"結(jié)點%d與結(jié)點%d的距離為：%d\n",i,j,1>; } } for<k=2;k<=v-1;k++>/*計算并顯示距離大于1的兩節(jié)點*/ { printf<"\n\n">; printf<"距離為%d的矩陣<即A%d>為：\n",k,k>; { for<i=0;i<v;i++> for<j=0;j<v;j++> { for<t=0;t<v;t++> C[i][j]=C[i][j]+B[i][t]*A[t][j];/*計算矩陣中的元素*/ } for<i=0;i<v;i++> for<j=0;j<v;j++> { B[i][j]=C[i][j];/*將計算出的結(jié)果賦予B矩陣*/ C[i][j]=0; } } for<i=0;i<v;i++> { for<j=0;j<v;j++> printf<"\t%5d",B[i][j]>;/*顯示距離矩陣*/ printf<"\n">; } printf<"\n">; for<i=1;i<=v;i++> for<j=1;j<=v;j++> { if<A[i-1][j-1]==0&&B[i-1][j-1]!=0&&i!=j>/*判斷條件,以確定輸出對象〔相關(guān)的點*/ printf<"結(jié)點%d與結(jié)點%d的距離為：%d\n",i,j,k>; } } printf<"\n">;}voidkedajuzhen<>/*求可達矩陣*/{ intl=1; printf<"可達矩陣為：\n">; for<i=0;i<v;i++>/*初始矩陣賦值*/ for<j=0;j<v;j++> { B[i][j]=A[i][j]; C[i][j]=0; } for<k=0;k<v;k++> { for<i=0;i<v;i++> for<j=0;j<v;j++> { for<t=0;t<v;t++> C[i][j]=C[i][j]+B[i][t]*A[t][j];/*根據(jù)公式計算可達矩陣*/ } for<i=0;i<v;i++> for<j=0;j<v;j++> { D[i][j]=C[i][j]+D[i][j];/*根據(jù)公式計算可達矩陣*/ } for<i=0;i<v;i++> for<j=0;j<v;j++> { B[i][j]=C[i][j];/*根據(jù)公式計算可達矩陣*/ C[i][j]=0; } } for<i=0;i<v;i++> { for<j=0;j<v;j++> if<D[i][j]>=1>/*將矩陣中不為0的一切值賦為1以生成可達矩陣*/ D[i][j]=1; } for<i=0;i<v;i++> { for<j=0;j<v;j++> printf<"\t%5d",D[i][j]>;/*顯示可達矩陣*/ printf<"\n">; } for<i=0;i<v;i++> { for<j=0;j<v;j++>/*根據(jù)可達矩陣的元素特點,判斷圖的連通性*/ if<D[i][j]==0>/*若可達矩陣矩陣中有0,則跳出循環(huán),顯示不可連接*/