【文章內(nèi)容簡介】 V5 V3 V7 V6 V8 例 0 1 2 3 1 3 4 2 data firstout 1 6 7 2 ^ ^ ^ adjvex link 4 5 5 ^ 3 7 1 ^ 6 7 8 5 6 7 6 ^ ^ ^ 深度遍歷： V1? V3 ? V7 ? V6 ? V2 ? V4 ? V8 ? V5 54 圖的遍歷 算法分析 ?圖中有 n 個頂點(diǎn)， e 條邊。 ?如果用鄰接矩陣存儲圖，則查找每一個頂點(diǎn)的所有的邊，所需時(shí)間為 O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為 O(n2)。 ?如果用鄰接表存儲圖，在每一個單鏈 表中可以找到某個頂點(diǎn) v 的所有鄰接頂點(diǎn) w。由于總共有 2e 個邊結(jié)點(diǎn) (無向圖 )，所以掃描邊的時(shí)間為 O(e)。而且對所有頂點(diǎn)遞歸訪問 1次，所以遍歷圖的時(shí)間復(fù)雜性為 O(n+e)。 55 圖的遍歷 廣度優(yōu)先遍歷 BFS（ Breadth First Search） 思路 ?在訪問了起始頂點(diǎn) v 之后，由 v 出發(fā)，依次訪問 v 的所有未被訪問過的鄰接點(diǎn) w1, w2, …, wt ，然后再順序訪問 w1, w2, …, wt 的所有未被訪問過的鄰接點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有未被訪問過的鄰接點(diǎn)， … ，如此重復(fù)，直到圖中所有頂點(diǎn)都被訪問完為止。 56 圖的遍歷 例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹 57 圖的遍歷 說明 ?廣度優(yōu)先遍歷是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先遍歷不是一個遞歸的過程，其算法也不是遞歸的。 ?為了實(shí)現(xiàn)逐層訪問，算法中使用了一個隊(duì)列，以記憶正在訪問的頂點(diǎn)，以便向下一層訪問。 ?與深度優(yōu)先遍歷過程一樣，為避免重復(fù)訪問，需要一個輔助數(shù)組 visited [ n]，對被訪問過的頂點(diǎn)加以標(biāo)記。 58 圖的遍歷 算法思想 ? 1）清隊(duì)列 Q； ? 2）對出發(fā)頂點(diǎn) v 做 ?v 入隊(duì)；標(biāo)記 v； ? 3）當(dāng) Q 不空反復(fù)做： ?出隊(duì)頭元素到 u； ?訪問 u； ?將 u 的每個未被訪問的鄰接點(diǎn) w 入隊(duì)；標(biāo)記 w。 59 圖的遍歷 廣度優(yōu)先搜索算法 void BFS (int v){ //廣度優(yōu)先求圖的連通分量 Q=new Queue( )； //清隊(duì)列 Q (v)； //每次從尚未訪問過的頂點(diǎn)中選取一個頂點(diǎn) v visited[v]=1； //標(biāo)記 v while (!()){ //Q不空 u=()； //出隊(duì)頭元素到 u visited(u)； //訪問 u for (w=FirstAdjVex(u)。 w。 w=NextAdjVex(u, w)) if (!visited[w]) { (w)； //將 u的每個未被訪問的鄰接點(diǎn) w 入隊(duì) visited[w]=1； } } }// BFS 60 圖的遍歷 ? BFS從出發(fā)點(diǎn)只能遍歷一個連通分量，若對任意圖的遍歷需要對每個分量中一個未被訪問的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行 BFS遍歷。 void BFSTraverse(){ //廣度優(yōu)先求圖的連通分量 int visited[n]； //設(shè)置訪問標(biāo)志數(shù)組 for (v=0； vn； v++) visited[v]=0； //初始化訪問標(biāo)志 for (v=0； vn； v++) if (!visited[v]) BFS( v)； } // BFSTraverse 61 圖的遍歷 例，廣度優(yōu)先遍歷序列，入隊(duì)序列，出隊(duì)序列。 V1 V3 V2 V4 V5 V6 V7 V8 遍歷序列： V1 V2 V3 V4 V5 V5 V6 V6 V7 V7 V8 V8 V4 V1 V2 V3 62 圖的遍歷 算法分析 ?如果用鄰接矩陣存儲圖，則對于每一個被訪問過的頂點(diǎn)，循環(huán)要檢測矩陣中的 n 個元素，總的時(shí)間代價(jià)為 O(n2)。 ?如果用鄰接表存儲圖，則循環(huán)的總時(shí)間代價(jià)為 D0 + D1 + … + D n1 = O(e)，其中的 Di 是頂點(diǎn) i 的度。而且對所有頂點(diǎn)訪問 1次，所以遍歷圖的時(shí)間復(fù)雜性為 O(n+e)。 63 圖的遍歷 DFS 與 BFS 之比較 ?空間復(fù)雜度相同，都是 O(n)（借用了堆棧或隊(duì)列）； ?時(shí)間復(fù)雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。 64 無向圖的應(yīng)用 —— 最小生成樹 生成樹 ?包含連通無向圖中全部頂點(diǎn)的極小連通子圖（ n 個頂點(diǎn)、 n1 條邊） ?一個連通圖的生成樹不唯一 ?使用不同的遍歷圖的方法，可以得到不同的生成樹 ?從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹 ?對于非連通圖，通過圖的遍歷，得到的是生成森林 65 無向圖的應(yīng)用 —— 最小生成樹 例 （ a） 深度優(yōu)先生成樹 （ b） 廣度優(yōu)先生成樹 V1 V3 V2 V4 V5 V6 V7 V8 V1 V3 V2 V4 V5 V6 V7 V8 66 無向圖的應(yīng)用 —— 最小生成樹 最小生成樹 MST（ Minimumcost Spanning Tree） ?連通無向網(wǎng)中 邊權(quán)之和 最小的生成樹 最小生成樹 MST的典型用途 ?假設(shè)在 7 個城市之間要建立通信網(wǎng)絡(luò)線，要求使得每個城市之間連通且費(fèi)用最少。 數(shù)學(xué)模型 連通網(wǎng) —— 表示 7個城市間的通信網(wǎng) ?頂點(diǎn) —— 表示城市 ?邊 ——— 表示城市間的通信線路 ?邊的權(quán)值 — 表示線路的經(jīng)濟(jì)代價(jià) 28 1 2 3 4 5 6 7 10 16 14 18 12 25 24 22 67 無向圖的應(yīng)用 —— 最小生成樹 構(gòu)造最小生成樹的準(zhǔn)則 ?必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹； ?必須使用且僅使用 n1 條邊來連接網(wǎng)絡(luò)中的 n 個頂點(diǎn)； ?不能使用產(chǎn)生回路的邊。 求一個連通無向網(wǎng)中最小生成樹的方法 ? Prim 算法 ? Kruskal 算法 都是利用 MST的性質(zhì) 構(gòu)造最小生成樹 68 無向圖的應(yīng)用 —— 最小生成樹 最小生成樹的性質(zhì) ?若集合 U 是集合 V 的一個非空子集，若 (u, v) 是一條具有最小權(quán)值的邊，其中 u?U， v?VU；則：(u, v) 必在最小生成樹上。 U VU 69 無向圖的應(yīng)用 —— 最小生成樹 Prim 算法 ? Prim 算法的基本思想 ?設(shè)連通 N={ V, E }， T 是 N 的最小生成樹中邊的集合， U 是生成樹的頂點(diǎn)集合。 ?（ 1） T={ } ， U={ u } （ u 為任一頂點(diǎn)）； ?（ 2）在所有 u∈ U， v∈ VU 的邊 (u, v)∈ E 中找一條代價(jià)最小的邊 (u, v) 加入集合 T 中，同時(shí) v 加入 U； ?（ 3）重復(fù)（ 2），直到 U=V 為止。 70 無向圖的應(yīng)用 —— 最小生成樹 ?例 0 1 2 6 3 4 5 28 16 12 22 25 10 25 14 18 T = { } U = { 0 } Min{10, 28}=10 (0,5) , 5 {25 }=25, (5,4) , 4 {28, 25, 22}=22 , (4,3) , 3 Min , , 18, 12}=12 , (3,2) , 2 , , 18, 16}=16 , (2,1) , 1 {25, 18, 14}=14 , (1,6) , 6 U=V，算法結(jié)束 71 無向圖的應(yīng)用 —— 最小生成樹 ? Prim 算法的實(shí)現(xiàn) ?圖的存儲：鄰接矩陣 ?在構(gòu)造過程中，還設(shè)置了一個輔助數(shù)組 closedge： ? 每個元素 closedge[v]有兩個域 – lowcost：存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹外各頂點(diǎn)v的各邊上的當(dāng)前最小權(quán)值 – adjvex：記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個頂點(diǎn)最近（即權(quán)值最小） 72 無向圖的應(yīng)用 —— 最小生成樹 ?從頂點(diǎn) 0出發(fā)利用 Prim算法構(gòu)造最小生成樹過程中輔助數(shù)組各分量的值的變化 i 1 2 3 4 5 6 closedge adjvex lowcost 0 28 0 ∞ 0 ∞ 0 ∞ 0 10 0 ∞ 525 422 424312 318 216i 1 2 3 4 5 6 edge adjvex lowcost 1140 1 2 3 4 5 6 U 1 0 0 0 0 0 0 5 25 0 10 114 22 13 12 12 16 11 14 173 無向圖的應(yīng)用 —— 最小生成樹 ?利用 Prim 算法求最小生成樹的算法 class AddArray{ int adjvex。 float lowcost。 }。// AddArray void MinSpanTree_Prim (int u, AddArray closedge[], AddArray edge[], AdjMatrix G){ // 設(shè)圖以鄰接矩陣存儲，用 Prim算法從頂點(diǎn) u出發(fā)構(gòu)造網(wǎng) G的最小生成樹且保存到數(shù)組 edge中 for(v=0； vn； v++) U[v]=0； U[u]=1； for (v=0； v n； v++) if（ u!=v) { closedge[v].adjvex=u。 74 無向圖的應(yīng)用 —— 最小生成樹 closedge[v].lowcost=[u][v]。 } for (t=1； tn； t++){ //選擇其余的 n1個頂點(diǎn) k=minimum(closedge)； // 求出 T的下一個頂點(diǎn) k頂點(diǎn) u=closedge[k].adjvex； edge[k].lowcost=[k][u]。 //保存選中邊的權(quán)值 edge[k].adjvex=u。 //保存選中邊的頂點(diǎn) U[k]=1； for (j=0； jn； j++) if (U[j]==0 amp。amp。 closedge[j].lowcost[k][j]){ closedge[j].lowcost=[k][j]； closedge[j].adjvex=k； } }// for } // MinSpanTree_Prim 75 無向圖的應(yīng)用 —— 最小生成樹 ? Prime 算法分析 ?設(shè)連通無向網(wǎng)有 n 個頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為O(n2) ?適用于稠密的網(wǎng)絡(luò) 76 無向圖的應(yīng)用 —— 最小生成樹 Kruscal 算法 ?基本思想 ?先構(gòu)造一個只含 n 個頂點(diǎn)、不含有邊的零圖 T ，然后從權(quán)值最小的邊開始，若它的添加不使 T 產(chǎn)生回路，則在 T 上加上這條邊，如此重復(fù)，直至加上 n1 條邊為止。