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

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

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

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

3、元組定義圖Ｇ是一個三元組由集合V，E和關(guān)聯(lián)函數(shù)組成，記為：G=（V，E，W（G））。其中V是頂點的集合，表示V（G）={V1，V2，V3，……Vn}，V（Ｇ）≠ＮＵＬＬ。Ｅ是V中的點偶對的有窮集，表示為E（G）={e1，e2，e3……em}，其中ei為或{Vj，Vt}，若ei為{Vj，Vt}，稱ei為以Vj和Vt為端點的無向邊；若ei為，稱ei為以Vj為起點，Vt為終點的有向邊；W（G）稱為E→VxV的關(guān)聯(lián)函數(shù)。2圖的存儲結(jié)構(gòu)　　圖的存儲結(jié)構(gòu)除了要存儲圖中各個頂點的本身的信息外，同時還要

4、存儲頂點與頂點之間的所有關(guān)系（邊的信息），因此，圖的結(jié)構(gòu)比較復(fù)雜，很難以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系，但也正是由于其任意的特性，故物理表示方法很多。常用的圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。對圖的每個頂點建立一個單鏈表（n個頂點建立n個單鏈表），第i個單鏈表中的結(jié)點包含頂點Vi的所有鄰接頂點。V2V1V5V4V3圖1無向圖G該圖的G的鄰接表表示如下:為了便于理解，本文以無向圖G作為具體示例（如圖1所示），給出以鄰接表進行存儲的圖的數(shù)據(jù)結(jié)構(gòu)?，F(xiàn)將圖G

5、的各頂點進行編號，其對應(yīng)的鄰接表如圖2所示：V1V2V3V4V531∧420∧431∧20∧1∧2圖2圖G的鄰接表表示2.1鄰接表的數(shù)據(jù)結(jié)構(gòu)定義，將圖G采用鄰接表存儲。其結(jié)構(gòu)有：#include"iostream.h"int*visited;//存放當(dāng)前結(jié)點是否遍歷typedefint**MGraph;//定義一個二維數(shù)組存放鄰接矩陣，暫不定義矩陣大小，數(shù)據(jù)元素類型為整型//把矩陣看作數(shù)組元素是一維數(shù)組的一個一維數(shù)組structArcNode{//定義鄰接表中的邊結(jié)點類型intadjvex;//鄰接點位置intwe

6、ight;//權(quán)值A(chǔ)rcNode*nextarc;//指向下一個邊結(jié)點的鏈域};structVNode{intdata;ArcNode*nextarc;};//鄰接表表頭結(jié)點typedefVNode*adjlist;//鄰接矩陣存儲方式voidInitGraph(MGraph&G,intn)//建立n行n列的二維數(shù)組{G=newint*[n];//分配第一維空間inti,j;for(i=0;i

7、)G[i][j]=0;//初始情況下沒有連接}2.2構(gòu)造算法：voidCreateGraph(MGraph&G,intn){//建立無向圖，其它形式的圖可以自己建立inti,j,e;cout<<"輸入無向圖中邊的總數(shù)量";cin>>e;cout<<"輸入每條邊的起點和終點序號(注：結(jié)點編號范圍為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

14、;}}//初始化voidInitAdj(adjlist&G,intn){G=newVNode[n];for(inti=0;i>e;