第4章基本搜索和遍歷方法PPT課件

1、第4章 基本搜索和遍歷方法 1 1 第4章 基本搜索和遍歷方法 4.1 基本概念 4.2 圖的搜索和遍歷 4.3 雙連通分量 4.4 與或圖 第4章 基本搜索和遍歷方法 4.1 基本概念 2 2 搜索和遍歷是計(jì)算機(jī)問題求解最常用的技術(shù)之一。 搜索（search）是一種通過系統(tǒng)地檢查給定數(shù)據(jù)對(duì)象 的每個(gè)結(jié)點(diǎn)，尋找一條從開始結(jié)點(diǎn)到答案結(jié)點(diǎn)的路徑， 最終輸出問題解的求解方法。 遍歷(traversal)要求系統(tǒng)地檢查數(shù)據(jù)對(duì)象的每個(gè)結(jié) 點(diǎn)。 根據(jù)被遍歷的數(shù)據(jù)對(duì)象的結(jié)構(gòu)不同，可分成樹遍歷和 圖遍歷。 第4章 基本搜索和遍歷方法 4.1 基本概念 狀態(tài)空間用于描述所求問題的各種可能的情況，每一種情 況對(duì)應(yīng)

2、于狀態(tài)空間中的一個(gè)狀態(tài)。 初始狀態(tài)：代表搜索開始。 目標(biāo)狀態(tài)（答案狀態(tài)）：一個(gè)或多個(gè)狀態(tài)代表已經(jīng)求得問 題解的情況。 問題的狀態(tài)空間常用一棵樹或一個(gè)圖表示。樹（圖）中的 一個(gè)結(jié)點(diǎn)代表問題的一個(gè)狀態(tài)，問題的狀態(tài)空間中的所有 狀態(tài)形成一棵狀態(tài)空間樹（圖）。 問題的求解過程:從起始狀態(tài)出發(fā)，以某種次序系統(tǒng)地檢 查狀態(tài)空間中的每一個(gè)狀態(tài)，搜索代表問題解的答案狀態(tài) 的過程。 3 3 一般來說，使用搜索技術(shù)來求解計(jì)算機(jī)問題，需要使用 狀態(tài)空間的概念精確地描述問題。 第4章 基本搜索和遍歷方法 無知搜索（盲目搜索或窮舉搜索），是最簡(jiǎn)單的搜索狀態(tài) 空間樹的方法。 按照事先約定的某種次序，系統(tǒng)地在狀態(tài)空間中搜索

3、目標(biāo) 狀態(tài)，而無須對(duì)狀態(tài)空間有較多了解。 4 4 有知搜索：運(yùn)用問題的相關(guān)知識(shí)，克服無知搜索的盲目性， 有效地指導(dǎo)搜索過程，使之盡快到達(dá)答案狀態(tài)。 啟發(fā)式搜索：采用經(jīng)驗(yàn)法則的搜索方法。 啟發(fā)式方法一邊搜索，一邊評(píng)估達(dá)到目標(biāo)狀態(tài)的剩余距離， 這種評(píng)估依賴于已有的關(guān)于問題領(lǐng)域的知識(shí)和經(jīng)驗(yàn)規(guī)則。 第4章 基本搜索和遍歷方法 4.2 圖的搜索和遍歷 4.2.1 搜索方法 在樹形結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)是它的孩子結(jié)點(diǎn)。 在圖形結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)是鄰接于該結(jié)點(diǎn)的所有 鄰接點(diǎn)。 5 5 遍歷：遵循某種次序，系統(tǒng)地訪問一個(gè)數(shù)據(jù)結(jié)構(gòu)的全部元素。 實(shí)現(xiàn)遍歷運(yùn)算的關(guān)鍵是規(guī)定結(jié)點(diǎn)被訪問的次序。 第4章

4、基本搜索和遍歷方法 6 6 為深入認(rèn)識(shí)搜索算法的特點(diǎn)，將被搜索的結(jié)點(diǎn)按其狀態(tài) 分成4類：未訪問、未檢測(cè)、已檢測(cè)和正擴(kuò)展。 未訪問狀態(tài)：一個(gè)結(jié)點(diǎn)x尚未訪問； 未檢測(cè)狀態(tài)：結(jié)點(diǎn)x自身已訪問，但x的后繼結(jié)點(diǎn)尚未全部訪問； 已檢測(cè)狀態(tài)：當(dāng)算法訪問了x的所有后繼結(jié)點(diǎn)時(shí)，就稱x已由此 算法檢測(cè)； 正擴(kuò)展?fàn)顟B(tài)：算法正從結(jié)點(diǎn)x出發(fā)，訪問x的某個(gè)后繼結(jié)點(diǎn),x被 稱為擴(kuò)展結(jié)點(diǎn)，簡(jiǎn)稱E-結(jié)點(diǎn)。 在算法執(zhí)行的任何時(shí)刻，最多只有一個(gè)結(jié)點(diǎn)為E-結(jié)點(diǎn)，但可以 有多個(gè)結(jié)點(diǎn)處于未檢測(cè)狀態(tài)。 第4章 基本搜索和遍歷方法 由于一個(gè)搜索算法總是從一個(gè)未檢測(cè)結(jié)點(diǎn)出發(fā)，獲取 下一個(gè)被訪問的結(jié)點(diǎn)，因此，保存所有未檢測(cè)結(jié)點(diǎn) 對(duì)于搜索算法是十

5、分重要的。 活結(jié)點(diǎn)：指未檢測(cè)結(jié)點(diǎn)。 死結(jié)點(diǎn)：指已檢測(cè)結(jié)點(diǎn)。 在搜索算法的執(zhí)行中，需要有一個(gè)數(shù)據(jù)結(jié)構(gòu)保存這些 活結(jié)點(diǎn)，被稱為活結(jié)點(diǎn)表。 7 7 依據(jù)如何選擇E-結(jié)點(diǎn)的規(guī)則不同，得到兩種不同的搜索 算法：深度優(yōu)先搜索和廣度優(yōu)先搜索。 第4章 基本搜索和遍歷方法 8 8 4.2.2 鄰接表類 設(shè)有向圖G=(V,E)有n個(gè)結(jié)點(diǎn)。圖4-1(b)給出了圖4-1(a) 的鄰接表存儲(chǔ)結(jié)構(gòu)。 第4章 基本搜索和遍歷方法 4.2.3 廣度優(yōu)先搜索 9 9 廣度優(yōu)先搜索：一個(gè)結(jié)點(diǎn)x一旦成為E結(jié)點(diǎn)，算法將依次訪 問完它的全部未訪問的后繼結(jié)點(diǎn)。每訪問一個(gè)結(jié)點(diǎn)，就將 它加入活結(jié)點(diǎn)表。直到x檢測(cè)完畢，算法才從活結(jié)點(diǎn)表另 選

6、一個(gè)活結(jié)點(diǎn)作為E結(jié)點(diǎn)。 廣度優(yōu)先搜索以隊(duì)列作為活結(jié)點(diǎn)表，因而也被稱為FIFO搜索。 第4章 基本搜索和遍歷方法 1010 為了實(shí)現(xiàn)搜索，也為了形象地刻畫圖搜索算法的執(zhí)行過程， 算法中使用白色、灰色和黑色分別代表結(jié)點(diǎn)處于未訪問、未 檢測(cè)和已檢測(cè)三種不同狀態(tài)。 E結(jié)點(diǎn)是灰色結(jié)點(diǎn)，任何時(shí)刻至多有一個(gè)灰色結(jié)點(diǎn)處于擴(kuò)展 狀態(tài)。 使用結(jié)點(diǎn)的顏色替代標(biāo)志位標(biāo)記一個(gè)結(jié)點(diǎn)是否已訪問。 為了保持搜索的軌跡，廣度優(yōu)先搜索為每個(gè)頂點(diǎn)著色：白色、 灰色或黑色。算法開始前所有頂點(diǎn)都是白色，隨著搜索的進(jìn) 行，各頂點(diǎn)會(huì)逐漸變成灰色，然后成為黑色。 第4章 基本搜索和遍歷方法 1.廣度優(yōu)先遍歷算法 1111 假設(shè)初始時(shí)圖G的所

7、有結(jié)點(diǎn)都為白色結(jié)點(diǎn)，那么從圖中某個(gè)結(jié) 點(diǎn)u出發(fā)的廣度優(yōu)先搜索圖的過程可以描述為： 訪問結(jié)點(diǎn)u，結(jié)點(diǎn)u著灰色； 然后依次訪問u的各個(gè)白色鄰接點(diǎn)，將它們著灰色； 訪問完結(jié)點(diǎn)u的所有白色鄰接點(diǎn)，結(jié)點(diǎn)u著黑色； 接著再依次訪問分別與這些鄰接點(diǎn)相鄰接的白色結(jié)點(diǎn) 隊(duì)列Q保存搜索過程中產(chǎn)生的活結(jié)點(diǎn)。 第4章 基本搜索和遍歷方法 1212 舉例：廣度優(yōu)先搜索在一個(gè)無向圖（結(jié)點(diǎn)S開始）上的 執(zhí)行過程 第4章 基本搜索和遍歷方法 1313 第4章 基本搜索和遍歷方法 2.廣度優(yōu)先樹 1414 算法BFS同時(shí)可生成一棵廣度優(yōu)先樹（森林）。 初始時(shí)，樹中只包含搜索的源結(jié)點(diǎn)作為根結(jié)點(diǎn)。在搜索中，對(duì) 于E結(jié)點(diǎn)u，每發(fā)現(xiàn)一

8、個(gè)白色結(jié)點(diǎn)v，便將結(jié)點(diǎn)v和邊添加 到樹中。 在廣度優(yōu)先樹中，稱結(jié)點(diǎn)u是結(jié)點(diǎn)v的雙親結(jié)點(diǎn)。如果結(jié)點(diǎn)v是 從根結(jié)點(diǎn)到結(jié)點(diǎn)w的路徑上的一個(gè)結(jié)點(diǎn)，則稱v是w的祖先，w是 v的后裔。 由于從一個(gè)給定的起始結(jié)點(diǎn)u出發(fā)的廣度優(yōu)先搜索，只能訪問 從u出發(fā)有路徑可達(dá)的那些結(jié)點(diǎn)。如果要遍歷整個(gè)有向圖，還 需從圖中另選未訪問的結(jié)點(diǎn)作為起始結(jié)點(diǎn)，再次進(jìn)行廣度優(yōu) 先搜索。 第4章 基本搜索和遍歷方法 1515 圖4-2給出了以結(jié)點(diǎn)0為起點(diǎn)，廣度優(yōu)先遍歷圖4-1(a)的 有向圖G所得到的廣度優(yōu)先森林，它包含兩棵廣度優(yōu)先 樹。 返回返回 01 236 5 4 01 236 5 4 圖G的廣度優(yōu)先森林 第4章 基本搜索和遍歷

9、方法 課堂練習(xí) 對(duì)于下面一個(gè)圖及其存儲(chǔ)結(jié) 構(gòu)，寫出以v2、v8為起始點(diǎn) 的廣度優(yōu)先遍歷序列，并畫 出廣度優(yōu)先樹。 1616 v1 v2 v3 v4 v5v6v7 v8 0 1 v1 2 v2 3 v3 4 v4 5 v5 6 v6 7 v7 8 v8 v2v3 v1v4v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 第4章 基本搜索和遍歷方法 1717 參考答案： 以v2為起始點(diǎn)：v2-v1-v4-v5-v3-v8-v6-v7 以v8為起始點(diǎn)：v8-v4-v5-v2-v1-v3-v6-v7 v1 v2 v3 v4 v5 v6v7 v8 v1 v2 v3 v4v5 v6v7

10、 v8 第4章 基本搜索和遍歷方法 4.2.4 深度優(yōu)先搜索 1818 深度優(yōu)先搜索： 訪問E結(jié)點(diǎn)x的某個(gè)后繼結(jié)點(diǎn)y后，立即使y成為新的E結(jié)點(diǎn)， 去訪問y的后繼結(jié)點(diǎn)，直到完全檢測(cè)結(jié)點(diǎn)y后，x才能再次 成為E結(jié)點(diǎn)，繼續(xù)訪問x的其他未訪問的后繼結(jié)點(diǎn)。 深度優(yōu)先搜索使用堆棧為活結(jié)點(diǎn)表。 第4章 基本搜索和遍歷方法 1.深度優(yōu)先遍歷算法 1919 初始時(shí)，圖G的所有結(jié)點(diǎn)都為白色結(jié)點(diǎn)，從圖中某個(gè)結(jié)點(diǎn) u出發(fā)的深度優(yōu)先搜索過程DFS可以描述為： （1）訪問結(jié)點(diǎn)u,對(duì)結(jié)點(diǎn)u著灰色； （2）依次從u的白色鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索圖G。 為了訪問有向圖中的所有結(jié)點(diǎn)，必須從圖中另選白色結(jié)點(diǎn) 為起始結(jié)點(diǎn)，再次進(jìn)行深

11、度優(yōu)先搜索?？赡苄枰貜?fù)多次， 直到圖中結(jié)點(diǎn)均已訪問。 第4章 基本搜索和遍歷方法 2020 為便于分析深度優(yōu)先搜索算法的執(zhí)行情況，在搜索中為 每個(gè)結(jié)點(diǎn)添加時(shí)間戳。 深度優(yōu)先搜索對(duì)每個(gè)結(jié)點(diǎn)u加蓋兩個(gè)時(shí)間戳du和fu： 第1個(gè)時(shí)間：當(dāng)結(jié)點(diǎn)u著灰色時(shí)，由du記錄； 第2個(gè)時(shí)間：當(dāng)結(jié)點(diǎn)u著黑色時(shí)，由fu記錄。 在時(shí)刻du之前結(jié)點(diǎn)u為白色，在時(shí)刻du和fu之間為灰 色， fu以后變?yōu)楹谏?初始時(shí)，對(duì)所有結(jié)點(diǎn)u， du = fu=0 ，時(shí)鐘的初值為0. 第4章 基本搜索和遍歷方法 2121 圖2說明了深度優(yōu)先搜索在有向圖（u出發(fā)）上的執(zhí)行過程。 第4章 基本搜索和遍歷方法 2222 第4章 基本搜索和

12、遍歷方法 2323 加粗的實(shí)線邊-樹枝 虛線邊-非樹枝的邊，分別標(biāo)明B、 C、F以表示反向邊、交叉邊、正向 邊。 第4章 基本搜索和遍歷方法 2.深度優(yōu)先樹 2424 算法同時(shí)可生成一棵深度優(yōu)先樹。 初始時(shí)，樹中只包含搜索的源結(jié)點(diǎn)作為根結(jié)點(diǎn)。 在搜索中，一個(gè)結(jié)點(diǎn)，每發(fā)現(xiàn)一個(gè)白色結(jié)點(diǎn)，便將結(jié)點(diǎn)及邊 添加到樹中。 對(duì)比對(duì)比 01 236 5 4 01 236 5 4 圖G的深度優(yōu)先森林 第4章 基本搜索和遍歷方法 2525 4.深度優(yōu)先搜索的性質(zhì) 定理 4-2 括號(hào)定理 在對(duì)有向圖或無向圖G=(V,E)的任何深度優(yōu)先搜索中，對(duì)于圖 中任意兩結(jié)點(diǎn)u和v，下述三個(gè)條件中有且僅有一條成立： (1)區(qū)間d

13、u,fu和區(qū)間dv,fv是完全分離的，且在 深度優(yōu)先森林中，u和v互不為后裔； (2)區(qū)間du,fu完全包含區(qū)間dv,fv，且在深度優(yōu) 先樹中v是u的后裔； (3)區(qū)間dv,fv完全包含區(qū)間du,fu，且在深度優(yōu) 先樹中u是v的后裔； 第4章 基本搜索和遍歷方法 5.邊的分類 2626 （1）樹邊(tree edge) ：深度優(yōu)先森林的邊。 （2）反向邊B(back edge) ：深度優(yōu)先樹中從后裔到祖先的邊， 環(huán)也被認(rèn)為是反向邊。 （3）正向邊F(forward edge) ：深度優(yōu)先樹中從祖先到后裔的 非樹邊。 （4）交叉邊C(cross edge) ：其余的邊。 當(dāng)一條邊既是反向邊又是

14、正向邊時(shí)，則認(rèn)為它是反 向邊。 第4章 基本搜索和遍歷方法 課堂練習(xí) 對(duì)于下圖及其鄰接表，寫 出以v2、v8為起始點(diǎn)的深 度優(yōu)先遍歷序列，并畫出 深度優(yōu)先樹，標(biāo)出邊的分 類。 2727 0 1 v1 2 v2 3 v3 4 v4 5 v5 6 v6 7 v7 8 v8 v2v3 v1v4v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 v1 v2 v3 v4 v5v6v7 v8 第4章 基本搜索和遍歷方法 參考答案： 以v2為起始點(diǎn)：v2-v1-v3-v6-v7-v4-v8-v5 以v8為起始點(diǎn)：v8-v4-v2-v1-v3-v6-v7-v5 2828 v1 v2 v3 v

15、4 v5 v6 v7 v8 B B v1 v2 v3 v4 v5 v6 v7 v8 B B 第4章 基本搜索和遍歷方法 2929 4.3 雙連通分量 4.3.1 基本概念 雙連通圖： 一個(gè)無向圖的任意兩個(gè)結(jié)點(diǎn)之間至少有兩條不同的路徑相通。 針對(duì)無向圖 關(guān)節(jié)點(diǎn)： 在一個(gè)無向連通圖G=(V,E)中，可能存在某個(gè)（或多個(gè)）結(jié) 點(diǎn)a，使得一旦刪除a及其相關(guān)聯(lián)的邊，圖G不再是連通圖， 則結(jié)點(diǎn)a稱為圖G的關(guān)節(jié)點(diǎn)。 橋： 如果刪除圖G的某條邊b,該圖分離成兩個(gè)非空子圖，則稱邊b 是圖G的橋。 第4章 基本搜索和遍歷方法 3030 圖4-5(a)中的圖G有哪些關(guān)節(jié)點(diǎn)？哪條邊是橋？ (a)無向連通圖G 01 3

16、 2 6 5 4 7 (b)刪除圖G的關(guān)節(jié)點(diǎn)1 (c)刪除圖G的橋 0 3 2 6 5 4 7 01 3 2 6 5 4 7 第4章 基本搜索和遍歷方法 3131 雙連通分量：無向連通圖G的極大雙連通子圖。 一個(gè)無向圖可以分成多個(gè)雙連通分量，它們將圖中的邊劃 分為若干個(gè)子集（不是將結(jié)點(diǎn)劃分子集）。 雙連通圖：無向連通圖G中不包含任何關(guān)節(jié)點(diǎn)。 01 3 2 6 5 4 7 第4章 基本搜索和遍歷方法 3232 從圖中可以看出： 1.兩個(gè)雙連通分 量至多有一個(gè)公 共結(jié)點(diǎn)，且此結(jié) 點(diǎn)必為關(guān)節(jié)點(diǎn)。 2.兩個(gè)雙連通分 量不可能共有同 一條邊。 3.每個(gè)雙連通分 量至少包含兩個(gè) 結(jié)點(diǎn)（除非無向 圖只有一個(gè)

17、結(jié)點(diǎn)） (a)無向連通圖G 01 3 2 6 5 4 7 雙連通分量 1 2 4 6 5 7 1 6 0 3 2 第4章 基本搜索和遍歷方法 3333 對(duì)于一個(gè)無向連通圖G，下列說法是等價(jià)的： （1）圖G是雙連通的； （2）圖G的任意兩個(gè)結(jié)點(diǎn)之間存在簡(jiǎn)單回路； （3）圖G中不包含關(guān)節(jié)點(diǎn)。 簡(jiǎn)單回路：在 一個(gè)回路中， 出現(xiàn)的邊互不 相同。 第4章 基本搜索和遍歷方法 4.3.2 發(fā)現(xiàn)關(guān)節(jié)點(diǎn) 在網(wǎng)絡(luò)應(yīng)用中，通常不希望網(wǎng)絡(luò)中存在關(guān)節(jié)點(diǎn)。因?yàn)檫@意味著 一旦在這些位置出現(xiàn)故障，勢(shì)必導(dǎo)致大面積的通信中斷。 因此判定一個(gè)無向圖是否雙連通圖，在圖中發(fā)現(xiàn)關(guān)節(jié)點(diǎn)及求圖 的雙連通分量是很有實(shí)際意義的問題。 3434

18、 一個(gè)無向連通圖不是雙連通圖的充要條件是圖中存在關(guān)節(jié)點(diǎn)。 在無向圖中識(shí)別關(guān)節(jié)點(diǎn)的最簡(jiǎn)單做法是：從圖G中刪除一個(gè) 結(jié)點(diǎn)a和該結(jié)點(diǎn)的關(guān)聯(lián)邊，再檢查圖G的連通性。如果圖G因 此而不再是連通圖，則結(jié)點(diǎn)a是關(guān)節(jié)點(diǎn)。 第4章 基本搜索和遍歷方法 3535 需借助圖的深度優(yōu)先生成樹來識(shí)別關(guān)節(jié)點(diǎn)。 假設(shè)從某個(gè)頂點(diǎn)V0出發(fā)對(duì)連通圖進(jìn)行深度優(yōu)先搜索，則 可得到一棵深度優(yōu)先生成樹，樹上包含圖的所有頂點(diǎn)。 第4章 基本搜索和遍歷方法 3636 a hg c bf de a b c d e f g h 2 3 4 5 6 7 8 例如:下列連通圖中的關(guān)節(jié)點(diǎn)？ 結(jié)點(diǎn)a,c是關(guān)節(jié)點(diǎn) 深度優(yōu)先生成樹(a為根結(jié)點(diǎn)) 結(jié)點(diǎn)的深度

19、 優(yōu)先數(shù)，記 錄了結(jié)點(diǎn)被 訪問的先后 次序 第4章 基本搜索和遍歷方法 3737 性質(zhì)4-3 給定無向連通圖G=(V,E),S=(V,T)是圖G的一棵 深度優(yōu)先樹，圖中結(jié)點(diǎn)a是一個(gè)關(guān)節(jié)點(diǎn)，當(dāng)且僅當(dāng) （1）a是根，且a至少有兩個(gè)孩子。 （2）或者a不是根，且a的某棵子樹上沒有指向a的祖先的 反向邊。 第4章 基本搜索和遍歷方法 求圖G關(guān)節(jié)點(diǎn)的算法 3838 深度優(yōu)先數(shù)：在深度優(yōu)先搜索中對(duì)每個(gè)結(jié)點(diǎn)u加蓋兩個(gè)時(shí)間 戳。其中，du記錄結(jié)點(diǎn)u被訪問的時(shí)間，也稱為結(jié)點(diǎn)的深 度優(yōu)先數(shù)； 為了實(shí)現(xiàn)這一算法，需要對(duì)圖中每個(gè)結(jié)點(diǎn)定義一個(gè)與優(yōu)先數(shù) 有關(guān)的量Low。 最低深度優(yōu)先數(shù)：Lowu表示從結(jié)點(diǎn)u出發(fā)，經(jīng)過某條

20、路徑 可以達(dá)到深度優(yōu)先樹其他結(jié)點(diǎn)的最小優(yōu)先數(shù)； 第4章 基本搜索和遍歷方法 3939 從結(jié)點(diǎn)u出發(fā)，有兩種途徑可以達(dá)到樹中其他結(jié)點(diǎn)： 一、自結(jié)點(diǎn)u經(jīng)過一條反向邊到達(dá)某個(gè)結(jié)點(diǎn)x； 二、自結(jié)點(diǎn)u出發(fā)，經(jīng)過u的某個(gè)孩子w，以及一條由w出 發(fā)的由樹邊組成的一條路徑和反向邊到達(dá)某個(gè)結(jié)點(diǎn)y； Lowu是結(jié)點(diǎn)u通過一條子孫路徑和至多隨后一條反向邊所 能到達(dá)的結(jié)點(diǎn)的最低深度優(yōu)先數(shù)。 第4章 基本搜索和遍歷方法 4040 定義 4-1：Lowu定義如下： Lowu=min du, min Loww | w是u的孩子， min dx | (u,x)是一條反向邊 圖4-9深度優(yōu)先搜索和深度優(yōu)先數(shù) 01 3 2 6

21、5 4 7 0 7 1 2 3 4 5 6 如果u不是根， 當(dāng)且僅當(dāng)結(jié)點(diǎn)u 有一個(gè)孩子w， 其Lowwdu 時(shí)，u是一個(gè)關(guān) 節(jié)點(diǎn) 第4章 基本搜索和遍歷方法 4141 圖中每個(gè)結(jié)點(diǎn)邊上的偶對(duì)(d,Low)代 表該結(jié)點(diǎn)的相應(yīng)值。 例如， 結(jié)點(diǎn)2邊上的(1,0)代表d2=1， Low2=0. 圖4-10結(jié)點(diǎn)的d和Low值 0 13 2 6 5 4 7 (0,0) (6,4) (5,4) (4,4) (3,1) (2,1) (1,0) (7,0) 第4章 基本搜索和遍歷方法 4.3.3 構(gòu)造雙連通圖 4242 發(fā)現(xiàn)關(guān)節(jié)點(diǎn)和求雙連通分量的目的是為了構(gòu)造雙連通網(wǎng)絡(luò)， 提高可靠性，改善網(wǎng)絡(luò)的性能。 一個(gè)非雙連通的圖，如果已經(jīng)求得原圖的關(guān)結(jié)點(diǎn)和雙連通 分量，便可對(duì)原圖添加若干邊使之成為雙連通圖。 添加邊