求一個(gè)無向圖g的連通分量的個(gè)數(shù)

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

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

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

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

4、tv)，而voidDFSTraverse(ALGraphG)內(nèi)調(diào)用了DFS()，因此計(jì)算機(jī)無法正確運(yùn)行，將兩者順序進(jìn)行了交換，程序便實(shí)現(xiàn)了其功能，且運(yùn)行正常。四、源程序及注釋：判斷一個(gè)圖有無回路：#include#include#include//輸出有向圖的一個(gè)拓?fù)湫蛄小?/圖的鄰接表存儲(chǔ)表示#defineMAX_NAME3//頂點(diǎn)字符串的最大長(zhǎng)度+1#defineMAX_VERTEX_NUM20#defineSTACK_INIT_SIZE10//存儲(chǔ)空間

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

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

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

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