【文章內(nèi)容簡(jiǎn)介】 如果將圖頂點(diǎn)的鄰接點(diǎn) 看作二叉樹(shù)結(jié)點(diǎn)的左、右孩子 深度優(yōu)先遍歷算法與 先序遍歷算法 的結(jié)構(gòu)是不是很像？ 深度優(yōu)先遍歷算法 void dfs( int v) { int w。 printf( “%d, “, v)。 visit[v]=1。 // 訪問(wèn)此結(jié)點(diǎn) while (ptr[v]！ =NULL） { w= ptr[v]vertex。 取結(jié)點(diǎn)的鄰接頂點(diǎn) w if ( visit[w]= =0。 ) dfs(w)。 ptr[v]=ptr[v]link。 // 記住頂點(diǎn) v 的鄰接點(diǎn)位置， } 該鄰接點(diǎn)在 w之后 } 先序遍歷遞歸算法 void prev (NODE *root) { if (root!=NULL) { printf(“%d,”, rootdata)； // 訪問(wèn)此結(jié)點(diǎn) prev(rootlch)。 // 訪問(wèn)孩子結(jié)點(diǎn) prev(rootrch)。 } } 比較 第 46頁(yè) 圖中某未訪問(wèn)過(guò)的頂點(diǎn) vi出發(fā)： 1）訪問(wèn)頂點(diǎn) vi ； 2）訪問(wèn) vi 的所有未被訪問(wèn)的鄰接點(diǎn) w1 ,w2 , … wk ； 3）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn) 。 依此類推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)； 二、廣度優(yōu)先遍歷 （類似于樹(shù)的按層遍歷） V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V2 V7 V5 V4 這是序列（ 1） 在遍歷過(guò)程中 所經(jīng)過(guò)的路徑 由于沒(méi)有規(guī)定 訪問(wèn)鄰接點(diǎn)的順序， 廣度優(yōu)先序列不是唯一的 例 求圖 G 的以 V0起點(diǎn)的的廣度優(yōu)先序列 : V0,V1,V2,V3,V4,V5,V6,V7 第 47頁(yè) 從圖中某頂點(diǎn) vi出發(fā)： 1）訪問(wèn)頂點(diǎn) vi ；（容易實(shí)現(xiàn)） 2）訪問(wèn) vi 的所有未被訪問(wèn)的鄰接點(diǎn) w1 ,w2 , … wk ； （容易實(shí)現(xiàn)） 3）依次從這些鄰接點(diǎn)（在步驟 2）訪問(wèn)的頂點(diǎn)）出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn) 。 依此類推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)； 為實(shí)現(xiàn) 3），需要 保存 在步驟 (2）中訪問(wèn)的頂點(diǎn)，而且 訪問(wèn)這些頂點(diǎn) 鄰接點(diǎn) 的順序?yàn)椋?先保存的頂點(diǎn)，其鄰接點(diǎn)先被訪問(wèn) 。 廣度優(yōu)先遍歷算法 在 廣度優(yōu)先遍歷算法中， 需設(shè)置一 隊(duì)列 Q， 保存已訪問(wèn)的頂點(diǎn)， 并控制遍歷頂點(diǎn)的順序。 V0 V7 V6 V5 V4 V3 V2 V1 第 48頁(yè) 廣度優(yōu)先遍歷 從圖中某頂點(diǎn) v出發(fā)： 1）訪問(wèn)頂點(diǎn) v ； 2）訪問(wèn) v的所有未被訪問(wèn)的鄰接點(diǎn) w1 ,w2 , … wk ； 3）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn) 。 依此類推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)； V0 V7 V6 V5 V4 V3 V2 V1 Q V1 V2 V3 V0 V4 V5 V6 V7 V0 V1 V2 V3 V4 V5 V6 V7 圖的遍歷 第 49頁(yè) 在 廣度優(yōu)先遍歷算法中， 需設(shè)置一 隊(duì)列 Q， 保存已訪問(wèn)的頂點(diǎn)， 并控制遍歷頂點(diǎn)的順序 int visit[MAX]。 int queue[MAX], front=0, rear=0。 第 50頁(yè) void bft(int v) //從 v出發(fā)，廣度優(yōu)先遍歷圖 G。 { int w。 NODE *p。 visit[v]=1。printf(“%d,”,v)。 enter(v)。 // enter(v)為入隊(duì)列函數(shù) while((v=leave())!=NULL)。 // leave()為出隊(duì)列函數(shù) { p=adjlist[v].link。 //p指向出隊(duì)列頂點(diǎn) v的第一個(gè)鄰接點(diǎn) while(p!=NULL) { w = pvertex。 //遍歷 v所指的整個(gè)鏈表 if(visit[w]= =0) //如果 w 未被訪問(wèn)過(guò) { printf(“%d,”,w)。 // 訪問(wèn) w visit[w]=1。enter(w)。 訪問(wèn)后， w 入隊(duì) } p=plink。 } } } 第 51頁(yè) main( ) { int num。 num=create(adjlist)。 breadfirst(num)。 // 調(diào)用對(duì)圖 G 廣度遍歷圖算法 } void breadfirst(int num) { int。 for (i=0。inum。i++) visit[i]=0。//給所有頂點(diǎn)一個(gè)未被訪問(wèn)標(biāo)記 for (i=0。inum。i++) if(visit[i]= =0) bft(i)。 // 調(diào)用以頂點(diǎn) vi 為出發(fā)點(diǎn)的是 廣度優(yōu)先 遍歷圖 G的算法 } 第 52頁(yè) 0 1 2 3 4 5 6 7 V0 V1 V2 V3 V4 V5 V6 V7 1 2 0 1 1 5 7 7 3 0 6 4 2 6 5 2 4 3 第 53頁(yè) V0 V2 V3 V1 V5 V4 V0 V2 V3 V1 V5 V4 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 兩種遍歷 的比較 第 54頁(yè) ? 無(wú)向圖的連通分量和生成樹(shù) ? 深度遍歷 P159圖 G3，得到的序列為： ? ALMJBFC DE GKHI 第 55頁(yè) 生成樹(shù) 生成樹(shù)是一個(gè)連通圖 G 的一個(gè)極小的連通子圖。包含圖 G 的所有頂點(diǎn)，但只有 n1 條邊，并且是連通的。生成樹(shù)可由遍歷過(guò)程中所經(jīng)過(guò)的邊組成。 深度優(yōu)先遍歷得到的 生成樹(shù)稱為 深度優(yōu)先 生成樹(shù) ；廣 度優(yōu)先遍歷得到的 生成樹(shù)稱為 廣 度優(yōu)先 生成樹(shù) 。 V0 V7 V6 V5 V4 V3 V2 V1 V3 V0 V7 V6 V5 V4 V2 V1 深度優(yōu)先 生成樹(shù) 廣 度優(yōu)先 生成樹(shù) 第 56頁(yè) 要在 n 個(gè)城市間建立交通網(wǎng) ， 要考慮的問(wèn)題如何在保證 n 點(diǎn)連通的前題下最節(jié)省經(jīng)費(fèi) ? V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 例 如何求連通圖的 最小生成樹(shù) ? 最小生成樹(shù)（最小支撐樹(shù)） 若有一個(gè)連通的無(wú)向圖 G ，有 n 個(gè)頂點(diǎn)，并且它的邊是有權(quán)值的。在 G 上構(gòu)造生成樹(shù) G’ ,最小生成樹(shù) n1 條邊的權(quán)值之和最小的 G’ 。 第 57頁(yè) ? MST性質(zhì)： 假設(shè) N=(V,{E})是一個(gè)連通網(wǎng)，若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，則必存在一棵包含邊 (u,v)的最小生成樹(shù)。 ? 普里姆算法 ? 克魯斯卡爾算法 第 58頁(yè) ? 普魯姆算法基本步驟 設(shè) G=（ V， E） 為一個(gè)具有 n個(gè)頂點(diǎn)的帶權(quán)的連通網(wǎng)絡(luò) ， T=（ U， TE）為構(gòu)造的生成樹(shù) 。 （ 1） 初始時(shí) ， U={u0}， TE=?； （ 2） 在所有 u?U 、 v?VU 的邊 （ u,v） 中選擇一條權(quán)值最小的邊 ， 不妨設(shè)為 （ u,v)； （ 3） (u,v) 加入 TE， 同時(shí)將 u 加入 U； （ 4） 重復(fù) (2)、 （ 3） ， 直到 U=V為止； (1) 普魯姆算法 V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 第 59頁(yè) V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 V2 V0 V3 V5 V4 V1 1 2 V2 V0 V3 V5 V4 V1 1 4 V2 V0 V3 V5 V4 V1 1 4 2 V2 V0 V3 V5 V4 V1 1 4 5 2 V3 V0 V3 V5 V4 V1 1 4 5 3 U={ V0 } U={ V0,V2 } U={ V0,V2,V5} U={ V0,V2,V5,V3 } U={ V0,V2,V5,V3,V1 } U={ V0,V2,V5,V3,V1,V4 } 第 60頁(yè) ?有關(guān)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 無(wú)向連通網(wǎng)絡(luò) : G 為 選擇權(quán)值最小的邊 : 置一個(gè)一維數(shù)組： closest[ ]， 對(duì) i?VU closest[i]= j (j?U) (j,i)是一條邊，且是 i 到 U 中各頂點(diǎn)“權(quán)最小邊 ” Lowcost[i]：用來(lái)保存連接 i 到 U 中各頂點(diǎn)“權(quán)最小邊”的權(quán)。 ?普魯姆算法涉及的數(shù)據(jù)和操作： 數(shù)據(jù)：無(wú)向連通網(wǎng)絡(luò) 操作 : 選擇權(quán)值最小的邊，不妨設(shè)為（ u,v) (u,v)加入 TE， u加入 U V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 U VU ? vi vj 第 61頁(yè) V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 例 0 0 0 0 0 0 0 6 1 5 max max i closest[i] lowcost[i] 0 1 2 3 4 5 i closest[i] lowcost[i] 0 1 2 3 4 5 0 2 0 0 2 2 0 5 0 5 6 4 U={ v0} U={ v0,v2} V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 U U 對(duì) i?VU closest[i]= j (j?U) (j,i)是一條邊，且是 i 到 U 中各頂點(diǎn)“權(quán)最小邊 ” Lowcost[i]：用來(lái)保存連接 i 到 U 中各頂點(diǎn)“權(quán)最小邊”的權(quán)。 VU={ v1,V2,V3,V4,V5 } VU={ v1, V3,V4,V5 } 生成樹(shù)和最小生成樹(shù) 第 62頁(yè) 0 0 0 0 0 0 0 6 1 5 max max lowcost {0} 0 2 0 0 2 2 0 5 0 5 6 4 closest lowcost {0,2} 0 2 0 5 2 2 0 5 0 2 6 0 closest lowcost {0,2,5} 0 2 0 5 2 2 0 5 0 0 6 0 closest lowcost {0,2,5,3} 0 2 0 5 1 2 0 0 0 0 3 0 closest lowcost {0,2,5,3,1} 0 2 0 5 1 2 0 0 0 0 0 0 closest lowcost {0,2,5,3,1,4} i closest 0 1 2 3 4 5 U 第 63頁(yè) 普里姆算法 圖采用鄰接矩陣表示，鄰接矩陣所對(duì)應(yīng)的二維數(shù)組是 cost[MAX][MAX], 則 (1) 初始化 ( U