1、 中國礦業大學軟件開發基礎實踐報告姓 名： xxs 學 號： bbaa0edf 專 業： 計算機科學與技術 指導教師： sjc 職 稱： js (僅供徐海計算機參考哈哈哈哈) 2012 年 6 月 20 徐州目錄第一章 實驗概述21.1 實驗目的21.2 實驗內容21.3 實驗環境2第二章 實驗原理和實現過程32.1 實驗原理3建立圖的鄰接矩陣，判斷圖是否連通32.1.2 計算任意兩個結點間的距離3對不連通的圖輸出其各個連通支42.2 實驗過程（算法描述）42.2.1 程序整體思路4具體算法流程4第三章 實驗數據及結果分析63.1建立圖的鄰接矩陣并判斷圖是否連通的功能測試及結果分析6輸入無向圖

2、的邊6建立圖的連接矩陣73.2 其他功能的功能測試和結果分析8計算節點間的距離8判斷圖的連通性8輸出圖的連通支9退出系統9第四章 實驗收獲和心得體會104.1 實驗收獲104.2 心得體會11第五章 實驗源程序清單125.1 程序代碼12第一章 實驗概述1.1 實驗目的理解圖論的基本概念，圖的矩陣表示，圖的連通性，圖的遍歷，以及求圖的連通支方法。通過實驗，幫助學生更好地掌握計算機科學技術常用的離散數學中的概念、性質和運算，培養邏輯思維；通過實驗提高學生編寫實驗報告、總結實驗結果的能力，提高理論聯系實際的能力；使學生具備程序設計的思想，能夠獨立完成簡單的算法設計和分析。1.2 實驗內容以偶對的形

3、式輸入一個無向簡單圖的邊，建立該圖的鄰接矩陣，判斷圖是否連通（A），并計算任意兩個結點間的距離（B），對不連通的圖輸出其各個連通支（C）。注意：題目類型分為A，B，C三類，其中A為基本題，完成A類題目可達到設計的基本要求，其他均為加分題，并按字母順序分數增加越高。基本要求如下：程序需具有基本的容錯控制，在輸入錯誤時有處理手段；程序界面友好，需要輸入的地方有輸入說明，說明輸入的內容和格式要求等；實驗原理和實現過程應該詳細分析問題，給出解決思路，描述算法思想，不能用源程序代替算法；測試數據應全面，包括非法輸入的處理結果等都應包含在內。1.3 實驗環境C或C語言編程環境實現。第二章 實驗原理和實現過

4、程2.1 實驗原理2.1.1建立圖的鄰接矩陣，判斷圖是否連通根據圖的矩陣表示法建立鄰接矩陣A，并利用矩陣的乘法和加法求出可達矩陣，從而判斷圖的連通性。連通圖的定義：在一個無向圖 G 中，若從頂點vi到頂點vj有路徑相連(當然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。判斷連通圖的實現：在圖中，從任意點出發在剩余的點中，找到所有相鄰點循環，直到沒有點可以加入為止，如果有剩余的點就是不連通的，否則就是連通的。或者也可用WallShell算法，由圖的鄰接矩陣判斷圖是否連通。2.1

5、.2 計算任意兩個結點間的距離圖中兩點i，j間的距離通過檢驗Al中使得aij為1的最小的l值求出。路徑P中所含邊的條數稱為路徑P的長度。在圖G<V,E>中，從結點Vi到Vj最短路徑的長度叫從Vi到Vj的距離，記為d<Vi，Vj>。設圖的鄰接矩陣是A，則 所對應的aij的值表示，點Vi到點Vj距離為n的路徑有aij條。若aij(1)，aij(2)，aij(n-1)，中至少有一個不為0，則可斷定Vi與Vj可達，使aij(l)0的最小的l即為d(Vi，Vj)。問題求解原理為：（1） 先構造初始鄰接矩陣A=Vij，Vij為頂點Vi到頂點Vj的權。如果Vi和Vj之間不存在弧段或者

6、是負向回路或者是i=j，則令Vij其值為。（2） 再構造初始中間頂點矩陣。（3） 然后開始迭代計算（迭代的次數等于頂點的個數1）（4）最后查找Vi到Vj的最短路徑。計算節點Vi與Vj之間的距離的方法為：利用鄰接矩陣相互間相乘后得到的矩陣來判斷節點間的距離。如果c2sij=0，則這兩個節點的距離為無窮大。如果c2s-2ij=0,c2s-1ij=1時，則這兩點間的距離為s。2.1.3對不連通的圖輸出其各個連通支圖的連通支的求法則可采用圖的遍歷算法，圖的遍歷有深度優先和廣度優先兩種方法，其中深度優先算法又分為遞歸和非遞歸兩種。在無向圖中，如果任何兩點可達，則稱圖G是連通的，如果G的子圖G是連通的，沒

7、有包含G的更大的子圖G是連通的，則稱G是G的連通支。當有判斷出關系不是連通的之后，將需要求出分支模塊實現方法如下：先定義一個二維數組用來存放相應的分塊，先選定一個點，并將它放在數組中，然后判斷，如果后面的和他是聯通的便將它也放在同一個數組中，否則將其存入其他的數組中，后面以此類推，在輸出相應的數組，便可判斷出連通分支。2.2 實驗過程（算法描述）2.2.1 程序整體思路本程序完成了實驗所要求的全部功能，其基本思路是“運用模塊化的思想，將實現“求連通支”、“輸入結點關系”、“輸出鄰接矩陣”、“顯示兩結點間的距離”、“求可達矩陣”和“圖的遍歷”的子函數分開編寫，然后將它們以子函數的形式添加到主函數

8、main的代碼后面，在要使用相應的子函數時，進行子函數調用就可以實現相應的功能了。”本程序的一大特色就是開發者靈活使用了C語言中的數組概念來進行開發，用數組來模擬矩陣的運算，通過相應的算法實現了全部的功能。2.2.2具體算法流程在main()系統界面顯示；用dowhile循環語句和switch語句實現功能1,2,3的選擇，并調用相關的子程序；用start、goto start實現控制流的轉移；liantongzhi()求連通支，此子函數通過一個for循環控制遍歷每個結點，并調用函數DFS（）求每個結點的連通支；DFS（int a）通過實參與形參，將結點數據代入函數；定義順序棧變量；通過for循

9、環初始化；為a置已訪問標志，已經訪問了的元素為1；定義順序棧的第一個元素；通過while循環實現結點遍歷，棧不為空時執行循環；棧頂元素賦值；通過for循環尋找v的下個未訪問的鄰接點；通過if條件句，若x,i是邊和節點i未被訪問過，處理結點的訪問，并進行訪問標志，進棧等操作；通過if條件句，若v已訪問到的出點，則將其退棧；shuru()輸入結點關系；通過for循環先將矩陣所有元素賦值0；再通過另一for循環，根據輸入結點的關系，將矩陣中相應的元素賦值，有關系則為1；linjiejuzhen()輸出鄰接矩陣；通過for循環，依次按格式輸出鄰接矩陣的元素；julijuzhen()根據A的n次方矩陣及

10、其中元素，判斷并顯示兩結點間的距離；調用子函數linjiejuzhen()，以確定并顯示距離為1的兩結點；通過for循環顯示距離為1的結點對；再通過一系列的for循環，計算A的n次方矩陣并顯示結果，根據其中的元素，判斷并顯示結點間的距離；詳細算法請見附錄相關部分的注釋；kedajuzhen()求可達矩陣；通過一系列for循環，根據公式，計算可達矩陣；通過for循環，將矩陣中不為0的一切值賦為1以生成可達矩陣并顯示；通過for循環和if條件句的組合，根據可達矩陣的元素特點，判斷圖的連通性，若可達矩陣矩陣中有0，則跳出循環，顯示不可連接；根據判斷結果顯示內容，不可連通或可連通；第三章 實驗數據及結

11、果分析3.1建立圖的鄰接矩陣并判斷圖是否連通的功能測試及結果分析簡單無向圖的輸入界面友好，有清楚的操作說明，方便用戶進行使用。這就是集合的輸入界面。3.1.1輸入無向圖的邊當“6,5”時 ，表示輸入的是六個節點五條邊的樹。程序會在屏幕上顯示輸入節點間關系的界面，輸入的關系為“1,2；2,3；3,4；4,5；5,6”3.1.2建立圖的連接矩陣程序返回主界面后，選擇“2”，程序會顯示建立的連接矩陣。3.2 其他功能的功能測試和結果分析3.2.1計算節點間的距離當選擇“3”時，程序便會輸出各節點間的距離。3.2.2判斷圖的連通性當選擇“4”時，程序會根據可達矩陣判斷圖的連通性。3.2.3輸出圖的連通

12、支當選擇“5”時，程序會輸出個連通支。3.2.4退出系統當選擇“6”時，程序會退出系統。第四章 實驗收獲和心得體會4.1 實驗收獲這次離散數學實驗是基于圖論方面知識，以圖的各種矩陣為基礎，來研究圖的一些性質、特點。我獨立完成了本次實驗設計，實現了A、B、C三個功能，滿足了實驗的基本要求，心得如下。通過這次實驗，我學會了用C語言根據圖的矩陣表示法建立鄰接矩陣A，并利用矩陣的乘法和加法求出可達矩陣，從而判斷圖的連通性。鞏固了課堂所學的圖論方面的有關知識，并在實踐中學到：圖中兩點i，j間的距離可以通過檢驗Al中使得aij為1的最小的l值求出；圖的連通支的求法可采用圖的遍歷算法，圖的遍歷有深度優先和廣

13、度優先兩種方法，其中深度優先算法又分為遞歸和非遞歸兩種。我選擇的算法是較為簡單、易于實現的深度優先算法最簡單，查閱了相關資料，掌握了此算法的核心，最后獨立完成了本次實驗設計。這次離散數學實驗，從拿到題目到完成整個編程，從理論到實踐的日子里，我學到很多東西，不僅可以鞏固了以前所學過的知識，而且通過查閱相關資料，學到了很多在書本上所沒有學到過的知識。在這段時間里，我對于離散數學中的“邏輯”有了進一步的理解，對C語言的理解也更進了一步，并提高了編寫實驗報告、總結實驗結果的能力，提高了理論聯系實際的能力，初步具備程序設計的思想，能夠獨立完成簡單的算法設計和分析。感受最深的是，大量的上機實踐是成為“編程

14、高手”的必由之路，“質變”需要有“量”的積累。完成程序的編寫，決不意味著萬事大吉。曾經自己認為萬無一失的程序，實際上機運行時可能不斷出現麻煩，如編譯程序檢測出一大堆錯誤。有時程序本身不存在語法錯誤，也能夠順利運行，但是運行結果顯然是錯誤的。開發環境所提供的編譯系統無法發現這種程序邏輯錯誤，只能靠自己的上機經驗分析判斷錯誤所在。有時候一個小小錯誤會消耗我好的時間去找，而高手一眼就看出錯誤所在，這就是熟練程度的不同，量變到質變的不同。4.2 心得體會這次真的使我意識到了很多原來沒有意識到的問題，有時候一些很小的問題，也會令人很是頭痛。在剛開始編寫程序的時候，為了實現最基本的輸入和輸出功能，我卻花了

15、大量的時間在那上面。原因在后來查閱的很多資料后才知道的，像scanf函數之類的小函數，其實是還有很多需要注意的地方的。之后，在編寫數組和指針的過程中，花了很大的一部分時間去研發算法，開發程序，在理論上反復證明沒有問題之后，再在計算機上進行操作，編寫代碼，進行調試，反復了很久，才慢慢的實現了全部的功能，真的是來之不易。在實驗的過程中我們要培養自己的獨立分析問題，和解決問題的能力。培養這種能力的前題是你對每次實驗的態度。如果你在實驗這方面很隨便，抱著等老師教你怎么做，拿同學的報告去抄，盡管你的成績會很高，但對將來工作是不利的。在寫實驗報告，對于思考題，有很多不懂，于是去問老師，老師的啟發了我，其實

16、答案早就擺在報告中的公式，電路圖中，自己要學會思考。最后，通過這次的實驗我不但對理論知識有了更加深的理解，對于實際的操作和也有了質的飛躍。經過這次的實驗，我們整體對各個方面都得到了不少的提高，希望以后學校和系里能夠開設更多類似的實驗，能夠讓我們得到更好的鍛煉。第五章 實驗源程序清單5.1 程序代碼#include <stdio.h>/*頭文件*/#include<stdlib.h>#include <math.h>#define MAX 100/*宏定義*/typedef struct int elemMAX; int top;SqStack;/*定義棧的結

17、構體,順序棧的類型標識符*/void shuru();/*各子函數聲明*/void linjiejuzhen();void julijuzhen();void kedajuzhen();void liantongzhi();void DFS(int a);int A99,B99,C99,D99;int i,j,k,t,v,e;int main()int a1;start: doprintf("n");printf("*n");printf("n");printf("tttt系 統 主 菜 單n");printf(&

18、quot;ntt1.輸入無向圖的邊ntt2.建立圖的鄰接矩陣ntt3.計算節點間的距離n");printf("tt4.由可達矩陣判斷圖的連通性ntt5.輸出各個連通支（深度優先DFS法）ntt6.退出系統n");printf("n"); printf("*n"); printf("n");printf("ntttt請輸入功能選項:");fflush(stdin);/*清空輸入緩沖區，通常是為了確保不影響后面的數據讀取*/scanf("%d",&a1);swi

19、tch(a1)/*switch語句實現選擇功能*/ case 1:system("cls");shuru();break;/*輸入節點關系，計算鄰接矩陣*/case 2:system("cls");fflush(stdin);linjiejuzhen();break;/*輸出鄰接矩陣*/case 3:system("cls");fflush(stdin);julijuzhen();break;/*求距離矩陣*/case 4:system("cls");fflush(stdin);kedajuzhen();break

20、;/*求可達矩陣*/case 5:system("cls");fflush(stdin);liantongzhi();break;/*求連通支*/case 6:system("exit");exit(0);/*結束整個程序的運行*/default:system("cls");goto start;/*控制流轉移到start處*/while(1); void liantongzhi()/*求連通支，此子函數控制遍歷每個結點*/for(i=1;i<=v;i+)printf("%d",i);DFS(i);/*調用子

21、函數求連通支*/printf("n");void DFS(int a)/*由深度優先DFS法求出并顯示各個連通支*/int i,x;int top=0;int visitedMAX;SqStack s;/*定義s為順序棧變量*/for (i=0;i<100;i+) visitedi=0;/*初始化為0*/visiteda-1=1;/*為a置已訪問標志，已經訪問了的元素為1*/ top=top+1; s.elemtop=a-1;/*順序棧的第一個元素*/while(top!=0)/*棧不為空時執行循環*/x=s.elemtop;/*將棧頂元素付給x*/for(i=0;i

22、<v;i+)/*尋找v的下個未訪問的鄰接點*/ if(Dxi!=0 &&(!visitedi)/*若x,i是邊和節點i未被訪問過*/ printf("->%d",i+1);visitedi=1;/*為i置已訪問標準*/ top=top+1; s.elemtop=i;/*i進棧*/break; if(i=v)/*若v已訪問到的出點，則將其退棧*/ top-; void shuru()/*輸入結點關系*/printf("*n");printf("n");printf("tt請輸入結點數和邊數（形式如6

23、,5）：n");scanf("%d,%d",&v,&e);/*輸入結點和邊數*/for(i=0;i<v;i+)/*初始賦值否為0*/for(j=0;j<v;j+)Aij=0; Cij=0; Bij=0; Dij=0;printf("n");printf("*n");printf("tt請輸入結點間的關系（形式如：1,2）：n");printf("n");for(k=0;k<e;k+)/*根據輸入的關系，確定鄰接矩陣中數值*/scanf("%d

24、,%d",&i,&j);Ai-1j-1=1;/*根據輸入結點的關系，將矩陣中相應的元素賦值*/Aj-1i-1=1; Bi-1j-1=1;Bj-1i-1=1; Di-1j-1=1;Dj-1i-1=1;system("cls");void linjiejuzhen()/*輸出鄰接矩陣*/printf("鄰接矩陣A為：n");for(i=0;i<v;i+)for(j=0;j<v;j+)printf("t%5d",Aij);/*顯示鄰接矩陣*/printf("n");printf(&q

25、uot;n");void julijuzhen()/*根據A的n次方矩陣及其中元素，判斷并顯示兩結點間的距離*/linjiejuzhen();/*調用子函數，以確定并顯示距離為1的兩結點*/for(i=1;i<=v;i+)for(j=1;j<=v;j+)if(Ai-1j-1=1)printf("結點%d與結點%d的距離為：%dn",i,j,1);for(k=2;k<=v-1;k+)/*計算并顯示距離大于1的兩節點*/printf("nn");printf("距離為%d的矩陣(即A%d)為：n",k,k);f

26、or(i=0;i<v;i+)for(j=0;j<v;j+)for(t=0;t<v;t+)Cij=Cij+Bit*Atj;/*計算矩陣中的元素*/for(i=0;i<v;i+)for(j=0;j<v;j+)Bij=Cij;/*將計算出的結果賦予B矩陣*/Cij=0;for(i=0;i<v;i+)for(j=0;j<v;j+)printf("t%5d",Bij);/*顯示距離矩陣*/printf("n");printf("n");for(i=1;i<=v;i+)for(j=1;j<=v

27、;j+)if(Ai-1j-1=0 && Bi-1j-1 != 0 && i!=j)/*判斷條件，以確定輸出對象（相關的點）*/printf("結點%d與結點%d的距離為：%dn",i,j,k);printf("n");void kedajuzhen()/*求可達矩陣*/int l=1;printf("可達矩陣為：n");for(i=0;i<v;i+)/*初始矩陣賦值*/for(j=0;j<v;j+)Bij=Aij;Cij=0;for(k=0;k<v;k+)for(i=0;i<v;

28、i+)for(j=0;j<v;j+)for(t=0;t<v;t+)Cij=Cij+Bit*Atj;/*根據公式計算可達矩陣*/for(i=0;i<v;i+)for(j=0;j<v;j+)Dij=Cij+Dij;/*根據公式計算可達矩陣*/for(i=0;i<v;i+)for(j=0;j<v;j+)Bij=Cij;/*根據公式計算可達矩陣*/Cij=0;for(i=0;i<v;i+)for(j=0;j<v;j+)if(Dij>=1)/*將矩陣中不為0的一切值賦為1以生成可達矩陣*/Dij=1;for(i=0;i<v;i+)for(j=0

29、;j<v;j+)printf("t%5d",Dij);/*顯示可達矩陣*/printf("n");for(i=0;i<v;i+)for(j=0;j<v;j+)/*根據可達矩陣的元素特點，判斷圖的連通性*/if(Dij = 0)/*若可達矩陣矩陣中有0，則跳出循環，顯示不可連接*/l=0;break;if(l=0)/*根據上一步判斷結果顯示內容*/printf("ntttt該圖不連通！");elseprintf("ntttt該圖可連通！");#include<stdio.h>#include<iostream>#include<stdlib.h>using namespace std;type