求一個無向圖g的連通分量的個數

《求一個無向圖g的連通分量的個數》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、《數據結構》實驗報告實驗內容：（一）判斷一個圖有無回路（二）求一個無向圖G的連通分量的個數一、目的和要求（需求分析）：1、了解圖的定義和圖的存儲結構。2、熟悉掌握圖的鄰接矩陣和鄰接表。3、理解圖的遍歷算法---深度優(yōu)先搜索和廣度優(yōu)先搜索。4、學會編程處理圖的連通性問題。二、程序設計的基本思想，原理和算法描述：（包括程序的結構，數據結構，輸入/輸出設計，符號名說明等）判斷一個圖有無回路：在程序設計中，先必須確定所要創(chuàng)建的圖是有向還是無向，是圖還是網，其次再根據各自的特點，用連接表來實現創(chuàng)建。在有向圖中，先找出入度為0

2、的頂點，刪除與這個頂點相關聯的邊（出邊），將與這些邊相關的其它頂點的入度減1，循環(huán)直到沒有入度為0的頂點。如果此時還有未被刪除的頂點，則必然存在環(huán)路，否則不存在回路。無向圖則可以轉化為：如果存在回路，則必然存在一個子圖，是一個回路。因此回路中所有定點的度>=2。第一步：刪除所有度<=1的頂點及相關邊，并將另外與這些邊相關的其它頂點的度減1。第二步：將度數變?yōu)?的頂點排入隊列，并從該隊列中（使用棧）取出一個頂點，并重復步驟一。如果最后還有未刪除的頂點，則存在回路，否則沒有。求一個無向圖G的連通分量的個數：用連接表創(chuàng)建

3、圖，對于非連通圖，則需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。所以在設計中，為了統計出無向圖中的連通分量個數，則因在其深度優(yōu)先所搜無向圖時對函數DFSTraverse(ALGraphG)調用DFS次數進行統計，其結果便為無向圖中連通分量個數。三、調試和運行程序過程中產生的問題及采取的措施：在調試和運行求一個無向圖G的連通分量的個數程序時，由于執(zhí)行語句塊voidDFSTraverse(ALGraphG)先于voidDFS(ALGraphG,in

4、tv)，而voidDFSTraverse(ALGraphG)內調用了DFS()，因此計算機無法正確運行，將兩者順序進行了交換，程序便實現了其功能，且運行正常。四、源程序及注釋：判斷一個圖有無回路：#include#include#include//輸出有向圖的一個拓撲序列。//圖的鄰接表存儲表示#defineMAX_NAME3//頂點字符串的最大長度+1#defineMAX_VERTEX_NUM20#defineSTACK_INIT_SIZE10//存儲空間

5、初始分配量#defineSTACKINCREMENT2//存儲空間分配增量typedefintInfoType;//存放網的權值typedefcharVertexType[MAX_NAME];//字符串類型typedefenum{DG,DN,AG,AN}GraphKind;//{有向圖,有向網,無向圖,無向網}typedefstructArcNode{intadjvex;//該弧所指向的頂點的位置structArcNode*nextarc;//指向下一條弧的指針I(yè)nfoType*info;//網的權值指針）}Arc

6、Node;//表結點typedefstructVNode{VertexTypedata;//頂點信息ArcNode*firstarc;//第一個表結點的地址,指向第一條依附該頂點的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];//頭結點typedefstruct{AdjListvertices;intvexnum,arcnum;//圖的當前頂點數和弧數intkind;//圖的種類標志}ALGraph;//若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。intLocateVex(ALG

7、raphG,VertexTypeu){inti;for(i=0;i

8、,&(*G).kind);printf("請輸入圖的頂點數和邊數:（空格）");scanf("%d%d",&(*G).vexnum,&(*G).arcnum);printf("請輸入%d個頂點的值(小于%d個字符):",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)//構造頂點向量{scanf("%s