【正文】 if ( !selected[j] amp。 for (j=1。i=n1。 selected[1]=TRUE。i=n。} else edges[i].w= ∞。i++) if ( [v0,i] ∞ ) {edges[i].vj=v0。T) { for (i=1。 i=n1。 i++) { 從候選邊中找出權(quán)值最小的邊 (v,vk)； //其中 v已選邊， vk未選 將 vk設(shè)置為已選頂點； 調(diào)整候選邊集合 調(diào)整新 入選頂點 和 未選頂點 之間的邊的集合 } 由此可知，需要考慮如下幾個方面的實現(xiàn)： （ 1） 已選頂點 的標(biāo)識：可用 數(shù)組 來或 集合 來存儲（或形式化描述）。 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 41 最小生成樹 Prim算法的簡要描述（設(shè)起點為 v0）： 設(shè)置各候選邊 (v0,vi)； for (i=1。 2. 實例 對右圖所示圖， 用 Prim算法求最小生成樹。但是如何求解？ ? prim算法 1. 基本思想 在滿足如下條件的過程中選出一條最小的邊： 一端已選，另一端未選。i++) if(!visited[i]) bfs(i)。 for(i=1。i=n。} w=nextadj(G,v,w)。 visited[w]=TRUE。 w=firstadj(G,v)。 (v0)。 visite(v0)。 (c) 出隊：從隊列中刪除一個頂點 v，這意味著要依次訪問 v的所有未被訪問過的鄰接點。 由此可知，這一結(jié)構(gòu)應(yīng)是 隊列 。 將搜索的便連起來得到 bfs生成樹。 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 33 廣度優(yōu)先搜索遍歷 bfs(1)的執(zhí)行過程如下圖所示。 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 32 廣度優(yōu)先搜索遍歷 ? 廣度優(yōu)先搜索遍歷（ Breadth_first search) 廣度優(yōu)先遍歷 —— 由近及遠(yuǎn)逐層訪問頂點（典型的層次遍歷） 1. 基本算法 從頂點 v0出發(fā)廣度優(yōu)先搜索遍歷圖的算法 bfs(v0): （ 1）訪問 v0 （ 2）依次訪問 v0的各鄰接點。為避免遺漏某種放置，從最后往前依次用余下的頂點中的與其前面相鄰接的頂點替換。 (4)若 k=ｎ ,有兩種情況 : (a)B[n]與 B[1]相鄰接 , 說明已求得一解 , 則輸出求解結(jié)果 , 然后返回。 (2)若 kn, 且不在當(dāng)前路徑上的頂點中存在與 B[k]相鄰的， 則 依次 從 余下 的頂點中取出與 B[k]相鄰的頂點放置在 B[k+1]中 , 轉(zhuǎn) (1)。 （ 3）需要判斷首尾相接。 （ 1， 2， 3， 4， 7， 6， 5， 8， 9， 10） 6 7 1 2 5 3 4 8 9 10 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 30 深度優(yōu)先搜索遍歷 算法設(shè)計中需要注意的： 通過在 dfs算法的基礎(chǔ)上變化而得： （ 1）路徑的記錄：需要增加變量或參數(shù)以記錄路徑，因此，不妨設(shè)一個數(shù)組以記錄路徑中的頂點序列和一個記錄長度的變量。 在這一表示下，問題轉(zhuǎn)化為： 求圖中包含所有頂點的簡單回路 。 分析 ：可以用 圖 來描述該問題： ① 用 頂點 表示一個 數(shù) ② 若兩個數(shù)的和為質(zhì)數(shù)， 則對應(yīng)頂點之間有一條 邊 。 return E/2。 i++) if (visited[i]==FALSE。 for (i=1。 i=n。 E=0。 w=nextadj(G,v,w)。 while (w!=0) { E++。 visited[v]=TRUE。 } 遍歷整個圖的算法dfs_travel中的原來的部分 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 27 深度優(yōu)先搜索遍歷 例 2 設(shè)計算法求出無向圖 G的邊數(shù)。 dfs(G,i)。 i=n。 i++) visited[i]=FALSE。 // k用于連通分量的計數(shù) for (i=1。 具體算法如下： 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 26 深度優(yōu)先搜索遍歷 int numofGC(graph G) { int i。 分析 ：對無向圖 G來說，選擇某一頂點 v執(zhí)行 dfs(v)， 可訪問到所在連通分量中的所有頂點 因此，選擇起點的次數(shù)就是圖 G的連通分量數(shù)， 這可通過修改遍歷整個圖的算法 dfs_travel來實現(xiàn)：每調(diào)用一次 dfs算法計數(shù)一次。 （ 5）設(shè)計算法以判斷圖中的一個節(jié)點是否為關(guān)節(jié)點。 } 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 24 深度優(yōu)先搜索遍歷 3. 深度遍歷算法的應(yīng)用 問題 ： （ 1）如何設(shè)計算法以判斷給定的無向圖是否是連通的？ （ 2）如何設(shè)計算法以求解給定的無向圖中的邊數(shù)？ （ 3）設(shè)計算法以判斷給定的無向圖是樹。 i=n。 i++) visited[i]=FALSE。 如何選擇新的起點？ 起點應(yīng)滿足什么條件？ 將對訪問標(biāo)志數(shù)組的賦初值運算， 以及選擇起點的控制合在一起， 構(gòu)成對 整個圖的遍歷算法 如下： void travel_dfs(graph G) { for (i=1。如下圖所示。 w=nextadj(G,v,w)。 visted[v0]=TRUE。 w=nextadj(G,v0,w)。 w=firstadj(G,v0)。 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 21 Y N 深度優(yōu)先搜索遍歷 由討論可得到 dfs算法的流程圖如下 ： 由此得深度遍歷基本算法 dfs(v0)如下 : void dfs(int v0) { visite(v0)。 nextadj(G,v,w)。 分析 ：由算法描述可知： ① 訪問 頂點 v0的基本操作： 可用 visite(v0)簡單表示。 6 7 1 2 5 3 4 8 10 9 6 7 1 2 5 3 4 8 10 9 原圖及其搜索示意圖 dfs(1)生成樹 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 20 深度優(yōu)先搜索遍歷 下面討論 dfs算法的設(shè)計。 1. 基本算法 從頂點 v0出發(fā)深度優(yōu)先搜索遍歷圖 G的 dfs (v0)描述如下： (1) 訪問 v0； (2) 依次從 v0的未被訪問過的鄰接點出發(fā)深度遍歷。則采用 n n的矩陣 A來表示， 1 i， j∈ E 其中 Aij＝ 0 否則 例 ： 1 3 2 4 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 行的方向：發(fā)出的弧 列的方向 ：進(jìn)入的弧 對應(yīng)關(guān)系 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 14 圖的存儲 （ 2） 網(wǎng)絡(luò)的表示方法 wij i， j∈ E Aij＝ 0 或 ∞ 否則 例 ： 4 ∞ 4 3 5 4 ∞ ∞ 2 3 ∞ ∞ 6 5 2 6 ∞ 1 2 4 3 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 無向圖的鄰接矩陣 對稱 1 4 2 3 6 3 5 2 4 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 15 圖的存儲 2. 鄰接表表示法 將 鄰接點構(gòu)成鏈表 例 ： 1 2 3 4 1 2 4 3 data firstadj 2 3 4 ^ 1 4 ^ 1 4 ^ 1 2 3 ^ 對應(yīng)關(guān)系 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 16 圖的存儲 ? 逆鄰接鏈表 將“鄰接自”的頂點連成鏈表 1 2 3 4 data firstadj 4 ^ 1 ^ 1 ^ 3 ^ 4 3 2 1 3 ^ 2 1 2 3 4 data firstadj 4 ^ 4 ^ 1 ^ 2 data firstadj 對應(yīng)關(guān)系 代表弧 4,1 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 17 圖的遍歷 圖的遍歷 —— 訪問圖中所有頂點一次且僅且一次。 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 13 圖的存儲 圖的存儲 圖結(jié)構(gòu)在計算機中的存儲形式 1。 返回頂點 v的鄰接點中處于鄰接點 w之后的鄰接點號。 若不存在時，返回 0（或定義為 1）。 6 7 1 2 5 3 4 樹的示例 6 7 1 2 5 3 4 有向樹示例 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 11 基本概念和運算 圖的運算： 基本運算 ： 初始化圖 插入頂點 插入邊（?。? 修改權(quán)值 刪除頂點 刪除邊（?。? 求指定頂點的鄰接點 常用運算 ： 遍歷 合肥工業(yè)大學(xué) 計算機與信息學(xué)院 12 基本概念和運算 鄰接點的求解方法： 具體實現(xiàn)依賴于圖的存儲結(jié)構(gòu)， 可以考慮用兩個運算來實現(xiàn)求解： int firstadj(G,v)。 并稱其中入度為 0的頂點為 有向根 。 連通的無環(huán)圖。 樹的定義有如下幾個 等價的描述 ： 有最少邊數(shù)的連通圖。 （共有 n (n1) / 2條邊） 若 有向圖 中每個頂點到其余各點均有一條弧 —— 則稱為 有向完全圖。 若 有向圖 中的任意兩點間可以 互相到達(dá) —— 則稱為 強連通圖。