數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：第七講3圖

1、7.3 圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍歷：V1

2、V2 V4 V8 V3 V6 V7 V5廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V

3、7 V8V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5無論是深度優(yōu)先遍歷，還是廣度優(yōu)先遍歷，走遍n個(gè)景點(diǎn)，實(shí)際上走過幾條路？如果遍歷的圖是連通的，當(dāng)然是走過n-1條路。N個(gè)結(jié)點(diǎn)，n-1條邊，讓我們想到了什么？對(duì)連通圖做一次DFS遍歷，把走過的的點(diǎn)和走過的邊留下，得到的稱為生成樹。腦子有點(diǎn)亂，我整理一下哦：對(duì)一個(gè)連通的圖，進(jìn)行深度，或者廣度優(yōu)先的遍歷，得到的結(jié)果其實(shí)是一棵樹。這棵樹可以保證做到：n個(gè)點(diǎn)之間用最少的邊，保持圖的連通特性。假設(shè)，每個(gè)邊上還帶著權(quán)值。那這樣可以嗎？構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設(shè)N=(V,E)是連通

4、網(wǎng)， 初始令U=u0,(u0V), TE= 在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0) 將邊(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn) 重復(fù)上述操作直至U=V為止，則T=(V,TE)為N的最小生成樹u0V1,v2,v3UV普里姆(Prim)算法實(shí)現(xiàn)所用數(shù)據(jù)結(jié)構(gòu)為鄰接矩陣“從V1出發(fā)，找周邊最小的邊”-在哪里找？我看出來了：v1-v3 最小。按照規(guī)定，把v3發(fā)展進(jìn)U集合。現(xiàn)在U集合周邊誰最??？第3行代表V3周邊所有邊的邊長(zhǎng)。所以，U周邊當(dāng)前最小邊是在第1行和第3行中間但是要想個(gè)辦法不能再選“1”。據(jù)觀察，周邊最小的邊是3-6.現(xiàn)在U1,3,6,有n個(gè)點(diǎn)呢，總不能就這么一直“觀察”算法描述：1、要有一個(gè)一維數(shù)組，記錄誰已經(jīng)被選中過了，不能重復(fù)選。2、最開始把V1那一行單獨(dú)拿出來，放在一個(gè)固定的一維數(shù)組lowcost里。3、以后找誰最小就在這個(gè)數(shù)組里找。4、找到誰最小，就在標(biāo)志數(shù)組里做標(biāo)志5，如果當(dāng)前是j列最小，那么就要用第j行和Lowcost對(duì)應(yīng)位置的數(shù)比較，用更小