圖的深度優(yōu)先搜索遍歷算法分析及其應(yīng)用

《圖的深度優(yōu)先搜索遍歷算法分析及其應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、重慶郵電大學(xué)數(shù)學(xué)大類(lèi)專(zhuān)業(yè)2008級(jí)《數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)》課程設(shè)計(jì)設(shè)計(jì)題目：圖的深度優(yōu)先搜索遍歷算法分析及其應(yīng)用設(shè)計(jì)時(shí)間：2010.9.7-----2010.9.12設(shè)計(jì)成績(jī)：姓名：班級(jí)：學(xué)號(hào)：指導(dǎo)教師：圖的深度優(yōu)先搜索遍歷算法分析及其應(yīng)用摘要:文章介紹了圖論，圖的基本概念及其圖的表示方法。詳細(xì)的分析了圖中以鄰接表為存儲(chǔ)結(jié)構(gòu)進(jìn)行的圖的深度優(yōu)先搜索遍歷的算法，并且在VC++環(huán)境中實(shí)現(xiàn)其算法的過(guò)程，對(duì)運(yùn)行記過(guò)做了一定量的分析，最后介紹了基于該算法的一些應(yīng)用。關(guān)鍵詞：圖；深度優(yōu)先搜索；遍歷；算法圖論〔GraphTheory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)

2、象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖（Graph）是一種較線性表和樹(shù)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。因此，在研究有關(guān)圖的問(wèn)題時(shí)，要考慮圖中每個(gè)頂點(diǎn)的信息，訪問(wèn)圖中的各個(gè)頂點(diǎn)，而訪問(wèn)圖中各個(gè)頂點(diǎn)的操作過(guò)程即使圖的遍歷，圖的遍歷算法是求解圖的連通性問(wèn)題，拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。1圖的三元組定義圖Ｇ是一個(gè)三元組由集合V，E和關(guān)聯(lián)函數(shù)組成，記為：G=（V，

3、E，W（G））。其中V是頂點(diǎn)的集合，表示V（G）={V1，V2，V3，……Vn}，V（Ｇ）≠ＮＵＬＬ。Ｅ是V中的點(diǎn)偶對(duì)的有窮集，表示為E（G）={e1，e2，e3……em}，其中ei為或{Vj，Vt}，若ei為{Vj，Vt}，稱(chēng)ei為以Vj和Vt為端點(diǎn)的無(wú)向邊；若ei為，稱(chēng)ei為以Vj為起點(diǎn)，Vt為終點(diǎn)的有向邊；W（G）稱(chēng)為E→VxV的關(guān)聯(lián)函數(shù)。2圖的存儲(chǔ)結(jié)構(gòu)　　圖的存儲(chǔ)結(jié)構(gòu)除了要存儲(chǔ)圖中各個(gè)頂點(diǎn)的本身的信息外，同時(shí)還要存儲(chǔ)頂點(diǎn)與頂點(diǎn)之間的所有關(guān)系（邊的信息），因此，圖的結(jié)構(gòu)比較復(fù)雜，很難以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)

4、表示元素之間的關(guān)系，但也正是由于其任意的特性，故物理表示方法很多。常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表（n個(gè)頂點(diǎn)建立n個(gè)單鏈表），第i個(gè)單鏈表中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。V2V1V5V4V3圖1無(wú)向圖G該圖的G的鄰接表表示如下:為了便于理解，本文以無(wú)向圖G作為具體示例（如圖1所示），給出以鄰接表進(jìn)行存儲(chǔ)的圖的數(shù)據(jù)結(jié)構(gòu)?，F(xiàn)將圖G的各頂點(diǎn)進(jìn)行編號(hào)，其對(duì)應(yīng)的鄰接表如圖2所示：V1V2V3V4V531∧420∧431∧20∧1∧2圖2圖G的鄰接表表示2.1鄰接表的數(shù)據(jù)

5、結(jié)構(gòu)定義，將圖G采用鄰接表存儲(chǔ)。其結(jié)構(gòu)有：#include"iostream.h"int*visited;//存放當(dāng)前結(jié)點(diǎn)是否遍歷typedefint**MGraph;//定義一個(gè)二維數(shù)組存放鄰接矩陣，暫不定義矩陣大小，數(shù)據(jù)元素類(lèi)型為整型//把矩陣看作數(shù)組元素是一維數(shù)組的一個(gè)一維數(shù)組structArcNode{//定義鄰接表中的邊結(jié)點(diǎn)類(lèi)型intadjvex;//鄰接點(diǎn)位置intweight;//權(quán)值A(chǔ)rcNode*nextarc;//指向下一個(gè)邊結(jié)點(diǎn)的鏈域};structVNode{intdata;ArcNode*nextarc;};//鄰接表表頭

6、結(jié)點(diǎn)typedefVNode*adjlist;//鄰接矩陣存儲(chǔ)方式voidInitGraph(MGraph&G,intn)//建立n行n列的二維數(shù)組{G=newint*[n];//分配第一維空間inti,j;for(i=0;i

7、圖中邊的總數(shù)量";cin>>e;cout<<"輸入每條邊的起點(diǎn)和終點(diǎn)序號(hào)(注：結(jié)點(diǎn)編號(hào)范圍為0~n-1):";for(intk=1;k<=e;k++){cout<<"第"<>i>>j;if(i>n

8、

9、j>n

10、

11、i<0

12、

13、j<0)return;G[i][j]=G[j][i]=1;}}//初始化voidInitAdj(adjlist&G,intn){G=newVNode[n];for(inti=0;i

14、CreateAdj(adjlist&G,intn){inti,j,k,e;cout<<"輸入圖的總邊數(shù)：";cin>>e;