深度優(yōu)先搜索

• 深度優(yōu)先搜索（depth-first search） 是對(duì)先序遍歷（preorder traversal）的推廣，我們從某個(gè)頂點(diǎn)v開(kāi)始處理v，然后遞歸的遍歷所有與v鄰接頂點(diǎn)。如果這個(gè)過(guò)程是對(duì)一棵樹(shù)進(jìn)行，那么，由于E=O(V)，因此樹(shù)的所有頂點(diǎn)在總時(shí)間O(E)內(nèi)都會(huì)被訪問(wèn)到。
• 方法：
  • 當(dāng)訪問(wèn)頂點(diǎn)v時(shí)候，我們標(biāo)記該節(jié)點(diǎn)以及訪問(wèn)過(guò)，并且對(duì)于未被標(biāo)記的所有鄰接頂點(diǎn)遞歸調(diào)用深度優(yōu)先搜索，
  • 加上我們對(duì)無(wú)向圖每條邊（v，w）在鄰接表中出現(xiàn)兩次：一次（v，w），另外一次（w，v）
  • 如下圖過(guò)程中執(zhí)行一次深度優(yōu)先搜索，什么都沒(méi)有操作的一次遍歷，只是深度優(yōu)先搜索的案例：

/*** @author liaojiamin* @Date:Created in 16:29 2021/1/8*/ public class GraphDepthFirstSearch {//遞歸調(diào)用深度優(yōu)先搜索實(shí)現(xiàn)public void depthFirst(Vertex v){v.setKnow(true);for (Vertex vertex : v.getVertexList()) {if(!vertex.isKnow()){depthFirst(vertex);}}} }

• 以上算法中，對(duì)每個(gè)頂點(diǎn)的known都是初始化為false，通過(guò)只對(duì)未訪問(wèn)過(guò)的節(jié)點(diǎn)進(jìn)行進(jìn)行遞歸調(diào)用，我們以此保證不進(jìn)入無(wú)線循環(huán)。
• 如果圖是無(wú)向的且不連通的，或者是有向的非強(qiáng)連通的（上一節(jié)中有對(duì)應(yīng)說(shuō)明）不能保證所有節(jié)點(diǎn)都能范文到，比如我們的v節(jié)點(diǎn)是從中途選取的一個(gè)節(jié)點(diǎn)，并不是圖的入口節(jié)點(diǎn)。
• 次數(shù)我們搜索一個(gè)未被標(biāo)記的節(jié)點(diǎn)，然后以這個(gè)節(jié)點(diǎn)為入口節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索，繼續(xù)執(zhí)行這兩個(gè)步驟直到所有節(jié)點(diǎn)都被標(biāo)記為止

無(wú)向圖

• 當(dāng)我們從無(wú)向圖的任何一個(gè)節(jié)點(diǎn)開(kāi)始深度優(yōu)先搜索的時(shí)候能訪問(wèn)到圖中的所有節(jié)點(diǎn)，那么這個(gè)無(wú)向圖是連通無(wú)向圖。
• 假設(shè)我們所處理的圖都是連通的，如果不連通我們可以找出所有連通分支并將我們的算法一次運(yùn)用到每個(gè)分支上即可（同上步驟）
• 作為深度優(yōu)先搜索的案例，在下圖中，我們從A點(diǎn)開(kāi)始。用以下遍歷流程：
  • 從A節(jié)點(diǎn)出發(fā)，A已經(jīng)被訪問(wèn)過(guò)，標(biāo)記A為true，并遞歸調(diào)用dfs（B）
  • dfs（B）標(biāo)記B節(jié)點(diǎn)為true并且遞歸調(diào)用dfs（C）
  • dfs（C）標(biāo)記C節(jié)點(diǎn)為true并且遞歸調(diào)用dfs（D）
  • dfs（D）遇到A，B但是A與B都已經(jīng)被標(biāo)記為true，因此沒(méi)有遞歸調(diào)用可以進(jìn)行，此時(shí)D-A，D-B為非必要的路徑
  • dfs（D）同時(shí)也是鄰接C的頂點(diǎn)，但是C也是被標(biāo)記為true，因此這里也沒(méi)有遞歸調(diào)用，此時(shí)D-C也是非必要路徑
  • 于是按照遞歸dfs（D）返回到dfs（C）
  • dfs（C）看到B是鄰接節(jié)點(diǎn)，但是B已經(jīng)是true，并且E也是C的鄰接節(jié)點(diǎn)，因此調(diào)用dfs（E）。
  • dfs（E）將E標(biāo)記為true，鄰接節(jié)點(diǎn)是A，C，都是true，因此忽略A，C，所以E-A，E-C是非必要路徑，因?yàn)镃-E已經(jīng)是被范問(wèn)過(guò)的已經(jīng)存在的路徑，所以剩下E-A是非必要路徑，繼續(xù)返回上一層dfs（C）
  • dfs（C）返回dfs（B），dfs（B）忽略A，D，同理BA是已知路徑，上面已經(jīng)走過(guò)，所以BD是非必要路徑
  • 返回上一層dfs（A）忽略D，E，兩個(gè)都是非必要路徑
  • 按以上算法遞歸得到，我們實(shí)際上對(duì)每個(gè)表都范問(wèn)了兩次，一次作為邊（v，w），一次作為邊（w，v），這實(shí)際上是每個(gè)鄰接表遍歷一次而已
    

深度優(yōu)先生成樹(shù)

• 我們用深度優(yōu)先生成樹(shù)（depth-first spanning tree）一圖形的方式來(lái)標(biāo)識(shí)上面的遞歸步驟，樹(shù)的根節(jié)點(diǎn)是入口節(jié)點(diǎn)A，第一個(gè)被訪問(wèn)到的頂點(diǎn)，圖中每一條表（v，w）都出現(xiàn)在樹(shù)上
  • 如果我們處理（v，w）的時(shí)候發(fā)現(xiàn)w是為未被標(biāo)記，或者處理（w，v）的時(shí)候發(fā)現(xiàn)v是未被標(biāo)記，那么我們就用樹(shù)的一條邊來(lái)標(biāo)識(shí)他
  • 如果我們處理（v，w）時(shí)候發(fā)現(xiàn)w已經(jīng)被標(biāo)記，并且處理（w，v）時(shí)候發(fā)現(xiàn)v已經(jīng)有標(biāo)記，那么我們就用虛線稱(chēng)為背向邊（上述步驟中的非必要路徑），標(biāo)識(shí)這條邊實(shí)際上不是這棵樹(shù)的一部分，也就是我們?nèi)サ暨@些邊也可以全部遍歷所有節(jié)點(diǎn)。
  • 如下圖

• 如果圖不是連通圖，我們上面討論過(guò)，需要多次執(zhí)行這個(gè)算法，直到所有節(jié)點(diǎn)都已經(jīng)被訪問(wèn)，每次都按照算法生成一顆樹(shù)，整個(gè)集合就是深度優(yōu)先生成森林（depth-first spanning forest）

雙連通性

• 一個(gè)連通的無(wú)向圖如果不存在被刪除之后使得剩下的圖有不在連通的頂點(diǎn)，那么這樣的無(wú)向連通圖就稱(chēng)為雙連通（biconnected）的。上面案例中的圖是雙連通的。
• 案例： 如果節(jié)點(diǎn)標(biāo)識(shí)計(jì)算機(jī)，邊是鏈路，如果一臺(tái)計(jì)算機(jī)宕機(jī)，則網(wǎng)絡(luò)是不受影響的，當(dāng)然這臺(tái)壞的計(jì)算機(jī)除外。
• 如果存在一個(gè)圖不是雙連通的，那么將其刪除后使得圖不在連通的那些頂點(diǎn)叫做割點(diǎn)（articulation point）。這些節(jié)點(diǎn)在許多應(yīng)用中很重要。下圖中所示不是雙連通的：頂點(diǎn)C，D都是割點(diǎn)。刪除頂點(diǎn)C，使的G不在連通，刪除D使得E，F單獨(dú)分離開(kāi)
• 深度優(yōu)先所搜提供一種找出連通圖中的所有割點(diǎn)的線性時(shí)間算法:
  • 首先從圖中任意一頂點(diǎn)開(kāi)始，執(zhí)行深度優(yōu)先搜索，并在頂點(diǎn)被訪問(wèn)的時(shí)候編號(hào)。對(duì)每個(gè)頂點(diǎn)v，我們稱(chēng)為先序編號(hào)為Num（v）。然后對(duì)于深度優(yōu)先搜索生成樹(shù)
  • 然后對(duì)于深度優(yōu)先搜索生成樹(shù)上的每個(gè)頂點(diǎn)v，計(jì)算編號(hào)最低的頂點(diǎn)，也就是在鄰接表中每個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)中Num（v）的最小值，我們稱(chēng)為L(zhǎng)ow（v），該節(jié)點(diǎn)可以從v開(kāi)始通過(guò)樹(shù)的0條邊（節(jié)點(diǎn)本身），或者多條表且有一條背向邊而達(dá)到
  • 如下圖中，依據(jù)深度優(yōu)先搜索樹(shù)首先得出先序編號(hào)，然后支出在上述方法下面可以達(dá)到的最低的編號(hào)。

• 如上圖，如A 頂點(diǎn)數(shù)據(jù)（1/1）,第一個(gè)數(shù)據(jù)表示Num（v），是先序遍歷的順序字段，圖中樹(shù)結(jié)構(gòu)的先序遍歷順序是A，B，C，D，E，F，G。

• 第二個(gè)數(shù)據(jù)表示的是Low（v），所有頂點(diǎn)的Low（v）開(kāi)始都等于Num（v），頂點(diǎn)A的low（v）是本身，

• D的鄰接節(jié)點(diǎn)中存在A節(jié)點(diǎn)，所以按以上規(guī)則Low（v）是最小的Num（v）所以取A 頂點(diǎn)的Num（v）

• 同理C節(jié)點(diǎn)鄰接節(jié)點(diǎn)是D也是1,B節(jié)點(diǎn)鄰接C也是1

• E節(jié)點(diǎn)鄰接F，F背向邊到D，所以F，E，都是D節(jié)點(diǎn)的Num（v） = 4.

• G沒(méi)有背向節(jié)點(diǎn)，所以是本身 7

• 我們依據(jù)以上Low定義可以指定Low（v）是滿(mǎn)足如下規(guī)則：

  • 初始值Num（v）
  • 如果有背向邊的話，取所有背向邊（v，w）中最低的Num（w）
  • 取樹(shù)的所有邊（v，w）中最低的Low（w）中的最小者

• 以上規(guī)則中第一條是不選取邊，本身就是最小，第二條規(guī)則是不選取樹(shù)的邊而是選取一條背向邊，第三種規(guī)則我們可以用遞歸調(diào)用簡(jiǎn)單的描述，由于我們需要對(duì)v的所有子節(jié)點(diǎn)算出Low值后才能得到最小Low（v），因此這是一個(gè)后續(xù)遍歷。對(duì)于任意的（v，w），只要檢查Num（v）和Num（w）就知道他是樹(shù)的一條邊還是一條背向邊，（因?yàn)榘礃?shù)生成算法背向邊總數(shù)從大的 num值 到小的num值）。因此Low（v）容易計(jì)算，我們只需要掃描v的鄰接節(jié)點(diǎn)，然后記住最小值。時(shí)間復(fù)雜度在O(E+V)。

• 接著我們需要做的就是利用以上信息找到所有割點(diǎn)。

  • 根是割點(diǎn)的時(shí)候只有在根節(jié)點(diǎn)有大于一個(gè)兒子節(jié)點(diǎn)的時(shí)候成立，如果有2個(gè)兒子節(jié)點(diǎn)，刪除根則使得不同子樹(shù)上節(jié)點(diǎn)不連通
  • 對(duì)于任何其他頂點(diǎn)v，他是割點(diǎn)的蟲(chóng)咬條件是，當(dāng)他的某個(gè)兒子節(jié)點(diǎn)w使得Low（w） >= Num（v），滿(mǎn)足
  • 還是上圖中的案例，C和D是割點(diǎn)，D有一個(gè)兒子節(jié)點(diǎn)E，且Lov（E） >= Num（D），兩個(gè)都是4
  • 同理C也是割點(diǎn)Low（G） >= Num?

算法實(shí)現(xiàn)

• 最后我們給出以下代碼實(shí)現(xiàn)該算法，我們需要在之前的Vertex圖節(jié)點(diǎn)中修改幾個(gè)屬性，num， low，沿用之前的known，path（父節(jié)點(diǎn)），用類(lèi)變了counter做統(tǒng)計(jì)為先序遍歷num編號(hào)，如下：

/*** @author liaojiamin* @Date:Created in 16:29 2021/1/8*/ public class GraphDepthFirstSearch {//假設(shè)圖基本數(shù)據(jù)結(jié)構(gòu)已經(jīng)被讀入鄰接表中private static final List<Vertex_v1> vertices = new ArrayList<>();private Integer counter = 0;/*** 深度優(yōu)先遞歸模板* */public void depthFirst(Vertex_v1 v){v.setKnow(true);for (Vertex_v1 vertex : v.getVertexList()) {if(!vertex.isKnow()){depthFirst(vertex);}}}/*** 深度優(yōu)先遞歸賦值nnum* */public void assignNum(Vertex_v1 v){v.setNum(counter++);v.setKnow(true);for (Vertex_v1 vertex_v1 : v.getVertexList()) {if(!vertex_v1.isKnow()){vertex_v1.setPath(v);assignNum(vertex_v1);}}}/*** 同樣的算法，深度優(yōu)先對(duì)Low賦值* */public void assignLow(Vertex_v1 v){v.setLow(v.getNum());for (Vertex_v1 w : v.getVertexList()) {//w > v 標(biāo)識(shí)w是v的子節(jié)點(diǎn)if(w.getNum() > v.getNum()){assignLow(w);//割點(diǎn)規(guī)則if(w.getLow() > v.getNum()){System.out.println(v.getNum() + " is an articulation point");}v.setLow(Math.min(v.getLow(), w.getLow()));}else if(v.getPath().compareTo(w) != 0){//此處不能寫(xiě)成： v.setLow(Math.min(v.getLow(), w.getLow()));因?yàn)榇朔N情況是在最后二次訪問(wèn)邊路徑的時(shí)候得到，可能w的Low已經(jīng)被修改成更小的值v.setLow(Math.min(v.getLow(), w.getNum()));}}}/*** 還是用深度優(yōu)先搜索，結(jié)合以上兩種規(guī)則，值進(jìn)行一次遍歷得到* */public void findArt(Vertex_v1 v){v.setKnow(true);v.setNum(counter++);v.setLow(v.getNum());for (Vertex_v1 w : v.getVertexList()) {if(!w.isKnow()){w.setPath(v);findArt(w);if(w.getLow() >= v.getNum()){System.out.println(v.getNum() + " is an articulation point");}v.setLow(Math.min(v.getLow(), w.getLow()));}else if(v.getPath().compareTo(w) != 0){//此處不能寫(xiě)成： v.setLow(Math.min(v.getLow(), w.getLow()));因?yàn)榇朔N情況是在最后二次范文邊路徑的時(shí)候得到，可能w的Low已經(jīng)被修改成更小的值v.setLow(Math.min(v.getLow(), w.getNum()));}}}}

• 以上算法中assignNum通過(guò)執(zhí)行一次先序遍歷計(jì)算Num，然后在后續(xù)遍歷計(jì)算Low，第三次遍歷可以用來(lái)檢查哪些頂點(diǎn)滿(mǎn)足割點(diǎn)的標(biāo)準(zhǔn)，但是執(zhí)行了三次遍歷比較浪費(fèi)，我們將兩個(gè)方法合成為findArt，在同一個(gè)遞歸中完成，得出算法。

上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–圖論-最短路徑算法應(yīng)用
下一篇：數(shù)據(jù)結(jié)構(gòu)與算法–貪婪算法：模擬調(diào)度問(wèn)題

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法--图论-深度优先搜索及其应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。