資源描述：
《圖的建立及輸出(圖的遍歷)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目圖的建立及輸出21學(xué)生姓名學(xué)號(hào)院系專業(yè)指導(dǎo)教師二Ｏ一Ｏ年12月16日目錄一、設(shè)計(jì)題目…………………………………………………2二、運(yùn)行環(huán)境（軟、硬件環(huán)境）………………………………2三、算法設(shè)計(jì)的思想…………………………………………23.1鄰接矩陣表示法…………………………………………23.2圖的遍歷………………………………………………43.3鄰接矩陣的輸出…………………………………………5四、算法的流程圖……………………………………………6五、算法設(shè)計(jì)分析……………………………………………7215.1無(wú)向網(wǎng)鄰接矩陣的建立算法…
2、……………………………75.2無(wú)向圖鄰接矩陣的建立算法………………………………75.3圖的深度優(yōu)先遍歷………………………………………75.4圖的廣度優(yōu)先遍歷………………………………………8六、源代碼……………………………………………………8七、運(yùn)行結(jié)果分析……………………………………………14八、收獲及體會(huì)………………………………………………15一、設(shè)計(jì)題目：圖的建立及輸出*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
3、二、運(yùn)行環(huán)境（軟、硬件環(huán)境）21*軟件環(huán)境：Windows7、WindowsVista、WindowsXp等*硬件環(huán)境：處理器：Pentium4以上內(nèi)存容量：256M以上硬盤容量：40GB以上三、算法設(shè)計(jì)的思想1、鄰接矩陣表示法: 設(shè)G=(V,E)是一個(gè)圖，其中V={V1,V2,V3…,Vn}。G的鄰接矩陣是一個(gè)他有下述性質(zhì)的n階方陣： 1，若(Vi,Vj)∈E或∈E；A[i,j]={0，反之圖5-2中有向圖G1和無(wú)向圖G2的鄰接矩陣分別為M1和M2:M1=┌0101┐│1010││1001│└0000┘M2=┌011
4、1┐│1010││1101│└1010┘21 注意無(wú)向圖的鄰接是一個(gè)對(duì)稱矩陣，例如M2。 用鄰接矩陣表示法來(lái)表示一個(gè)具有n個(gè)頂點(diǎn)的圖時(shí)，除了用鄰接矩陣中的n*n個(gè)元素存儲(chǔ)頂點(diǎn)間相鄰關(guān)系外，往往還需要另設(shè)一個(gè)向量存儲(chǔ)n個(gè)頂點(diǎn)的信息。因此其類型定義如下： VertexTypevertex[MAX_VERTEX_NUM];//頂點(diǎn)向量AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)GraphKindkind;//圖的種類標(biāo)志 若圖中每個(gè)頂點(diǎn)只含一個(gè)編號(hào)i(1≤i≤vnum)，則只需一個(gè)二維
5、數(shù)組表示圖的鄰接矩陣。此時(shí)存儲(chǔ)結(jié)構(gòu)可簡(jiǎn)單說(shuō)明如下： typeadjmatrix=array[1..vnum,1..vnum]ofadj; 利用鄰接矩陣很容易判定任意兩個(gè)頂點(diǎn)之間是否有邊（或?。┫嗦?lián)，并容易求得各個(gè)頂點(diǎn)的度?！ ?duì)于無(wú)向圖，頂點(diǎn)Vi的度是鄰接矩陣中第i行元素之和，即 n n D(Vi)＝∑A[i,j] ?。ɑ颉艫[i,j]） j=1 i=1 對(duì)于有向圖，頂點(diǎn)Vi的出度OD(Vi)為鄰接矩陣第i行元素之和，頂點(diǎn)Vi的入度ID(Vi)為第i列元素之和。即 n
6、 n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1 j=1 21 用鄰接矩陣也可以表示帶權(quán)圖，只要令 Wij,若或(Vi,Vj) A[i,j]＝{ ∞,否則?！ ∑渲蠾ij為或(Vi,Vj)上的權(quán)值。相應(yīng)地，網(wǎng)的鄰接矩陣表示的類型定義應(yīng)作如下的修改： adj:weightype;{weightype為權(quán)類型} 圖5-6列出一個(gè)網(wǎng)和它的鄰接矩陣。┌∞３１∞∞┐│∞∞５１∞││∞∞∞∞∞││∞∞６
7、∞∞│└∞３２２∞┘(a)網(wǎng)(b)鄰接矩陣圖5-6網(wǎng)及其鄰接矩陣 對(duì)無(wú)向圖或無(wú)向網(wǎng)絡(luò)，由于其鄰接矩陣是對(duì)稱的，故可采用壓縮存貯的方法，僅存貯下三角或上三角中的元素(但不含對(duì)角線上的元素)即可。顯然，鄰接矩陣表示法的空間復(fù)雜度O()。無(wú)向網(wǎng)鄰接矩陣的建立方法是：首先將矩陣A的每個(gè)元素都初始化成∞。然后，讀入邊及權(quán)值(i,j,wij),將A的相應(yīng)元素置成Wij。2、圖的遍歷：*深度優(yōu)先搜索21深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有的頂點(diǎn)未曾被訪問，則深度優(yōu)先遍歷可從圖的某個(gè)頂點(diǎn)V出發(fā)，訪問此頂點(diǎn)，然后依次
8、從V的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中的一個(gè)未被訪問的頂點(diǎn)，重復(fù)
