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

1、7.3 圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止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)方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止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個景點，實際上走過幾條路？如果遍歷的圖是連通的，當(dāng)然是走過n-1條路。N個結(jié)點，n-1條邊，讓我們想到了什么？對連通圖做一次DFS遍歷，把走過的的點和走過的邊留下，得到的稱為生成樹。腦子有點亂，我整理一下哦：對一個連通的圖，進行深度，或者廣度優(yōu)先的遍歷，得到的結(jié)果其實是一棵樹。這棵樹可以保證做到：n個點之間用最少的邊，保持圖的連通特性。假設(shè)，每個邊上還帶著權(quán)值。那這樣可以嗎？構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設(shè)N=(V,E)是連通

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