|
當(dāng)我們在學(xué)習(xí)和臨摹垃圾回收(Garbage Collection, 縮寫為 GC)相關(guān)算法和源碼時候, 內(nèi)在細(xì)節(jié)離不開 這兩大類搜索算法支撐. 這就是構(gòu)建的背景?, 文章定位是科普掃盲?. 0. 引述與目錄[0] 知乎 - 節(jié)點 or 結(jié)點 ? [走進(jìn)科學(xué)] [1] 維基百科 - 廣度優(yōu)先搜索 [概念參照] [2] 維基百科 - 深度優(yōu)先搜索 [概念參照] [3] 維基百科 - 樹的遍歷 [概念參照] [4] CSDN - 二叉樹的深度優(yōu)先遍歷與廣度優(yōu)先遍歷 [盜圖] [5] 博客園 - 數(shù)據(jù)結(jié)構(gòu)之圖的基本概念 [遞歸抄襲] [6] 博客園 - 圖的遍歷之 深度優(yōu)先搜索和廣度優(yōu)先搜索 [深度抄襲] [7] github - 深度搜索和廣度搜索 [演示素材] 目錄 1. 概念介紹關(guān)于遍歷算法種類有很多很多, 這里選了最通用, 深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩類搜索算法進(jìn)行淺顯 講解(作者能力有限). 基礎(chǔ)有時候很有趣, 真的! ok, 那我們 go on. 深度優(yōu)先搜索算法(Depth-First-Search, 縮寫為 DFS), 是一種用于遍歷或搜索樹或圖的算法. 這個算法 會盡可能深的搜索樹的分支. 當(dāng)結(jié)點 v 的所在邊都己被探尋過, 搜索將回溯到發(fā)現(xiàn)結(jié)點 v 的那條邊的起始結(jié) 點. 這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點可達(dá)的所有結(jié)點為止. 如果還存在未被發(fā)現(xiàn)的結(jié)點, 則選擇其中一 個作為源結(jié)點并重復(fù)以上過程, 整個進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點都被訪問為止. 廣度優(yōu)先搜索算法(Breadth-First Search, 縮寫為 BFS), 又譯作寬度優(yōu)先搜索, 或橫向優(yōu)先搜索, 是一種 圖形搜索算法. 簡單的說, BFS 是從根結(jié)點開始, 沿著樹的寬度遍歷樹的結(jié)點. 如果所有結(jié)點均被訪問, 則算法 中止. 在計算機(jī)科學(xué)里, 樹的遍歷(也稱為樹的搜索)是圖的遍歷的一種, 指的是按照某種規(guī)則, 不重復(fù)地訪問某 種樹的所有結(jié)點的過程. 具體的訪問操作可能是檢查結(jié)點的值, 更新結(jié)點的值等. 不同的遍歷方式, 其訪問結(jié) 點的順序是不一樣的. 以下我們將二叉樹的廣度優(yōu)先和深度優(yōu)先遍歷算法歸類，但它們也適用于其它樹形結(jié) 構(gòu). 深度優(yōu)先遍歷(搜索) 前序遍歷(Pre-Order Traversal)
深度優(yōu)先搜索 - 前序遍歷: F -> B -> A -> D -> C -> E -> G -> I ->H 中序遍歷(In-Order Traversal)
深度優(yōu)先搜索 - 中序遍歷: A -> B -> C -> D -> E -> F -> G -> H -> I 后序遍歷(Post-Order Traversal)
深度優(yōu)先搜索 - 后序遍歷: A -> C -> E -> D -> B -> H -> I -> G -> F 廣度優(yōu)先遍歷(搜索) 層次遍歷(Level Order Traversal)
廣度優(yōu)先搜索 - 層次遍歷：F -> B -> G -> A -> D -> I -> C -> E -> H 通過閱讀和思考以上維基百科中提供的摘錄, 我們大致對兩類遍歷算法有了點直觀的認(rèn)知. 不知道有沒 有人有這樣的疑惑, 為什么寬度優(yōu)先搜索叫法沒有廣度優(yōu)先搜索這個叫法流傳廣, 明明在樹結(jié)構(gòu)中要好理解 多了呢? 乍看確實這樣, 但不要忘了樹結(jié)構(gòu)是一種特殊圖結(jié)構(gòu), 而復(fù)雜圖結(jié)構(gòu)可能沒有直觀從上到下, 從左到 右這種直觀的觀感了. 因而寬度優(yōu)先搜索名詞在一般化中顯得不夠準(zhǔn)確了. 哈哈哈. 另外一個認(rèn)知是關(guān)于必要 條件的. 例如深度和廣度優(yōu)先搜索包含很多不同遍歷相關(guān)相關(guān)算法, 不僅僅只有文章中介紹那幾個, 這點大家 要充分認(rèn)識. 2. 樹的例子
觀察圖片, 提示中可以發(fā)現(xiàn)前中后序遍歷定義是圍繞根結(jié)點訪問時機(jī)定義的(還存在潛規(guī)則, 默認(rèn)先左子 樹后右子樹). 下面我們通過具體的代碼來表達(dá)遍歷思路. 首先我們構(gòu)造樹結(jié)構(gòu) /** * 方便測試和描述算法, 用 int node 構(gòu)建 */ typedef int node_t; static void node_printf(node_t value) { printf(" %2d", value); } struct tree { struct tree * left; struct tree * right; node_t node; }; static inline struct tree * tree_new(node_t value) { struct tree * node = malloc(sizeof (struct tree)); node->left = node->right = NULL; node->node = value; return node; } static void tree_delete_partial(struct tree * node) { if (node->left) tree_delete_partial(node->left); if (node->right) tree_delete_partial(node->right); free(node); } void tree_delete(struct tree * root) { if (root) tree_delete_partial(root); } 2.1 前序遍歷static void tree_preorder_partial(struct stack * s) { struct tree * top; // 2.1 訪問棧頂結(jié)點, 并將其出棧 while ((top = stack_pop_top(s))) { // 2.2 做業(yè)務(wù)處理 node_printf(top->node); // 3. 如果根結(jié)點存在右孩子, 則將右孩子入棧 if (top->right) stack_push(s, top->right); // 4. 如果根結(jié)點存在左孩子, 則將左孩子入棧 if (top->left) stack_push(s, top->left); } } /* * 前序遍歷: * 根結(jié)點 -> 左子樹 -> 右子樹 * * 遍歷算法: * 1. 先將根結(jié)點入棧 2. 訪問棧頂結(jié)點, 做業(yè)務(wù)處理, 并將其出棧 3. 如果根結(jié)點存在右孩子, 則將右孩子入棧 4. 如果根結(jié)點存在左孩子, 則將左孩子入棧 重復(fù) 2 - 4 直到?？? */ void tree_preorder(struct tree * root) { if (!root) return; struct stack s[1]; stack_init(s); // 1. 先將根結(jié)點入棧 stack_push(s, root); // 重復(fù) 2 - 4 直到?？?/span> tree_preorder_partial(s); stack_free(s); } 2.2 中序遍歷static void tree_inorder_partial(struct tree * node, struct stack * s) { // 4. 重復(fù)第 2 - 3步, 直到?？詹⑶也淮嬖诖L問結(jié)點 while (!stack_empty(s) || node) { // 2. 將當(dāng)前結(jié)點的所有左孩子入棧, 直到左孩子為空 while (node) { // 1. 先將根結(jié)點入棧 stack_push(s, node); node = node->left; } // 3.1 彈出并訪問棧頂元素, node = stack_pop_top(s); // 3.2 做業(yè)務(wù)處理. node_printf(node->node); // 4.1 如果棧頂元素存在右孩子 node = node->right; } } /* * 中序遍歷: * 左子樹 -> 根結(jié)點 -> 右子樹 * * 遍歷算法: * 1. 先將根結(jié)點入棧 2. 將當(dāng)前結(jié)點的所有左孩子入棧, 直到左孩子為空 3. 彈出并訪問棧頂元素, 做業(yè)務(wù)處理. 4. 如果棧頂元素存在右孩子, 重復(fù)第 2 - 3步, 直到?？詹⑶也淮嬖诖L問結(jié)點 */ void tree_inorder(struct tree * root) { if (!root) return; struct stack s[1]; stack_init(s); tree_inorder_partial(root, s); stack_free(s); } 2.3 后序遍歷static void tree_postorder_partial(struct stack * s) { struct tree * top; // 記錄前一次出棧結(jié)點 struct tree * last = NULL; // 重復(fù) 1-2 直到?？?/span> while ((top = stack_top(s))) { // 2.2 如果我們發(fā)現(xiàn)它左右子結(jié)點都為空, 則可以做業(yè)務(wù)處理; // 2.3 或者，如果發(fā)現(xiàn)前一個出棧的結(jié)點是它的左結(jié)點或者右子結(jié)點,，則可以做業(yè)務(wù)處理; if ((!top->left && !top->right) || (last && (last == top->left || last == top->right))) { // 做業(yè)務(wù)處理 node_printf(top->node); // 出棧 stack_pop(s); // 記錄此次出棧結(jié)點 last = top; } else { // 2.4. 否則，表示這個結(jié)點是一個新的結(jié)點,，需要嘗試將其右左子結(jié)點依次入棧. if (top->right) stack_push(s, top->right); if (top->left) stack_push(s, top->left); } } } /* * 后序遍歷: * 左子樹 -> 右子樹 -> 根結(jié)點 * * 遍歷算法: * 1. 拿到一個結(jié)點, 先將其入棧, 則它一定在比較靠棧底的地方, 比較晚出棧 2. 在出棧時候判斷到底是只有左結(jié)點還是只有右結(jié)點或者是兩者都有或者是都沒有. 如果我們發(fā)現(xiàn)它左右子結(jié)點都為空, 則可以做業(yè)務(wù)處理; 或者,，如果發(fā)現(xiàn)前一個出棧的結(jié)點是它的左結(jié)點或者右子結(jié)點，則可以做業(yè)務(wù)處理; 否則,，表示這個結(jié)點是一個新的結(jié)點,，需要嘗試將其右左子結(jié)點依次入棧. 重復(fù) 1-2 直到棧空 */ void tree_postorder(struct tree * root) { if (!root) return; struct stack s[1]; stack_init(s); // 1. 先將根結(jié)點入棧 stack_push(s, root); // 重復(fù) 1 - 4 直到?？?/span> tree_postorder_partial(s); stack_free(s); } 思考上面深度優(yōu)先搜索三種方式, 大致會感覺, 占用?？臻g大小映象是 前序遍歷 < 中序遍歷 < 后序遍歷 (存在 特例). 可能, 這也是前序遍歷是樹深度優(yōu)先搜索算法中流傳最廣的原因. 對于樹的后序遍歷代碼實現(xiàn), 版本也有 好幾個. 有的很容易手寫, 很花哨偷巧, 這里推薦的是正規(guī)工程版本. 2.4 層次遍歷/* * 層次遍歷: * 根結(jié)點 -> 下一層 | 左結(jié)點 -> 右結(jié)點 * * 遍歷算法: * 1. 對于不為空的結(jié)點, 先把該結(jié)點加入到隊列中 * 2. 從隊中彈出結(jié)點, 并做業(yè)務(wù)處理, 嘗試將左結(jié)點右結(jié)點依次壓入隊列中 * 重復(fù) 1 - 2 指導(dǎo)隊列為空 */ void tree_level(struct tree * root) { if (!root) return; q_t q; q_init(q); // 1. 對于不為空的結(jié)點, 先把該結(jié)點加入到隊列中 q_push(q, root); do { // 2.1 從隊中彈出結(jié)點, 并做業(yè)務(wù)處理 struct tree * node = q_pop(q); node_printf(node->node); // 2.2 嘗試將左結(jié)點右結(jié)點依次壓入隊列中 if (node->left) q_push(q, node->left); if (node->right) q_push(q, node->right); // 重復(fù) 1 - 2 指導(dǎo)隊列為空 } while (q_exist(q)); q_free(q); } 上面思路非常正規(guī)直白, 也可以做語言配合算法進(jìn)行簡單優(yōu)化(推薦). /* * 層次遍歷: * 根結(jié)點 -> 下一層 | 左結(jié)點 -> 右結(jié)點 * * 遍歷算法: * 1. 開始結(jié)點判空, 決定是否繼續(xù) * 2. 構(gòu)建輔助隊列結(jié)構(gòu) * 3. 直接對結(jié)點做業(yè)務(wù)處理 * 4. 嘗試將不為空左結(jié)點右結(jié)點依次壓入隊列中 * 5. 隊列出隊賦值保存 * 重復(fù) 3 - 5 直到變量為空 */ void tree_level_optimize(struct tree * root) { // 1. 開始結(jié)點判空, 決定是否繼續(xù) if (!root) return; // 2. 構(gòu)建輔助隊列結(jié)構(gòu) q_t q; q_init(q); do { // 3. 直接對結(jié)點做業(yè)務(wù)處理 node_printf(root->node); // 4. 嘗試將不為空左結(jié)點右結(jié)點依次壓入隊列中 if (root->left) q_push(q, root->left); if (root->right) q_push(q, root->right); // 5. 隊列出隊賦值保存 root = q_pop(q); // 重復(fù) 3 - 5 直到變量為空 } while (root); q_free(q); } 2.5 搜索算法源碼3. 圖的例子本章會先對圖的深度優(yōu)先搜索和廣度優(yōu)先搜索進(jìn)行簡單介紹, 然后再給出 C 的源碼實現(xiàn). 3.0 圖的基本概念3.0.1 圖的定義定義: 圖(Graph)是由頂點的有窮非空集合和頂點之間邊的集合組成, 通常表示為: G(V, E), 其中, G 表示一個圖, V 是 圖 G 中頂點的集合, E 是 圖 G 中邊的集合. 在圖中需要注意的是: (1) 線性表中我們把數(shù)據(jù)元素叫元素, 樹中將數(shù)據(jù)元素叫結(jié)點, 在圖中數(shù)據(jù)元素, 我們則稱之為頂點(Vertex). (2) 線性表可以沒有元素, 稱為空表; 樹中可以沒有結(jié)點, 稱為空樹; 但是, 在圖中不允許沒有頂點(有窮非空性). (3) 線性表中的各元素是線性關(guān)系, 樹中的各元素是層次關(guān)系, 而, 圖中各頂點的關(guān)系是用邊來表示(邊集可以為 空). 3.0.2 圖的基本概念(1) 無向圖 如果圖中任意兩個頂點之間的邊都是無向邊(簡而言之就是沒有方向的邊), 則稱該圖為無向圖(Undirected graphs). (2) 有向圖
如果圖中任意兩個頂點之間的邊都是有向邊(簡而言之就是有方向的邊), 則稱該圖為有向圖(Directed graphs). (3) 完全圖 ① 無向完全圖: 在無向圖中, 如果任意兩個頂點之間都存在邊, 則稱該圖為無向完全圖. (含有 n 個頂點的無向完 全圖有 (n×(n-1))/2 條邊) 如下圖所示:
② 有向完全圖: 在有向圖中, 如果任意兩個頂點之間都存在方向互為相反的兩條弧, 則稱該圖為有向完全圖. (含 有 n 個頂點的有向完全圖有 n×(n-1) 條邊) 如下圖所示:
PS: 當(dāng)一個圖接近完全圖時, 則稱它為稠密圖(Dense Graph), 而當(dāng)一個圖含有較少的邊時, 則稱它為稀疏圖( Spare Graph). (4) 頂點的度 頂點 V 的度(Degree) 是指在圖中與 V 相關(guān)聯(lián)的邊的條數(shù). 對于有向圖來說, 有入度(In-degree)和出度 (Out-degree) 之分, 有向圖頂點的度等于該頂點的入度和出度之和. 例如 A -> B 標(biāo)識 A 出度為 1, B 入度為 1. (5) 鄰接 ① 若無向圖中的兩個頂點 V 和 W 存在一條邊(V, W), 則稱頂點 V 和 W 鄰接(Adjacent); ② 若有向圖中存在一條邊<V, W>，則稱 頂點 V 鄰接到 頂點 W ,，活 頂點 W 鄰接自 頂點 V; 以 (2) 有向圖 舉例, 有 <A, D> <B, A> <B, C> <C, A> 鄰接關(guān)系. (6) 弧頭和弧尾 有向圖中, 無箭頭一端的頂點通常被稱為"初始點"或"弧尾", 箭頭直線的頂點被稱為"終端點"或"弧頭". <A, D> 鄰接關(guān)系中, 頂點 A 就是弧尾, 頂點 D 就是弧頭. PS: 無向圖中的邊使用小括號"()"表示, 而有向圖中的邊使用尖括號"<>" 表示. (7) 路徑 在無向圖中, 若從頂點 V 出發(fā)有一組邊可到達(dá)頂點 W, 則稱頂點 V 到頂點 W 的頂點序列, 為從頂點 V 到頂點 W的 路徑(Path). (8) 連通 若從 V 到 W 有路徑可通, 則稱頂點 V 和頂點 W 是連通(Connected)的. (9) 權(quán)
有些圖的邊或弧具有與它相關(guān)的數(shù)字, 這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)(Weight). 有些圖的邊或弧具有與它相關(guān)的數(shù)字, 這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)(Weight). 3.0.3 圖最基礎(chǔ)的兩類存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)除了要存儲圖中的各個頂點本身的信息之外, 還要存儲頂點與頂點之間的關(guān)系, 因此, 圖的結(jié) 構(gòu)也比較復(fù)雜. 常用最基礎(chǔ)的兩類圖的存儲結(jié)構(gòu)有鄰接矩陣和鄰接表. 3.0.3.1 鄰接矩陣表示法圖的鄰接矩陣(Adjacency Matrix)存儲方式是用兩個數(shù)組來表示圖. 一個一維數(shù)組存儲圖中頂點信息, 一個 二維數(shù)組(稱為鄰接矩陣)存儲圖中的邊或弧的信息. (1) 無向圖
我們可以設(shè)置兩個數(shù)組, 頂點數(shù)組為 vertex[4] = {V0, V1, V2, V3}, 邊數(shù)組 edges[4][4] 為上圖右邊這樣的一個矩 陣. 對于矩陣的主對角線的值, 即 edges[0][0], edges[1][1], edges[2][2], edges[3][3], 全為 0, 因為不存在頂點 自己到自己的邊. (2) 有向圖 我們再來看一個有向圖樣例, 如下圖所示的左邊. 頂點數(shù)組為 vertex[4] = {V0, V1, V2, V3}, 弧數(shù)組 edges[4][4] 為下圖右邊這樣的一個矩陣. 主對角線上數(shù)值依然為 0. 但因為是有向圖, 所以此矩陣并不對稱, 比如由 V1 到 V0 有弧, 得到 edges[1][0] = 1, 而 V0 到 V1 沒有弧, 因此 edges[0][1] = 0.
不足: 由于存在 n 個頂點的圖需要 n*n 個數(shù)組元素進(jìn)行存儲, 當(dāng)圖為稀疏圖時, 使用鄰接矩陣存儲方法將會出 現(xiàn)大量 0 元素, 這會造成極大的空間浪費. 這時, 可以考慮使用鄰接表表示法來存儲圖中的數(shù)據(jù). 3.0.3.2 鄰接表表示法首先, 回憶我們烙印在身體里的線性表存儲結(jié)構(gòu), 順序存儲結(jié)構(gòu)因為存在預(yù)先分配內(nèi)存可能造成存儲空間 浪費的問題, 于是想到了鏈?zhǔn)酱鎯Φ慕Y(jié)構(gòu). 同樣的, 我們也可以嘗試對邊或弧使用鏈?zhǔn)酱鎯Φ姆绞絹肀苊饪臻g浪 費的問題. 鄰接表由表頭結(jié)點和表結(jié)點兩部分組成, 圖中每個頂點均對應(yīng)一個存儲在數(shù)組中的表頭結(jié)點. 如果這個表 頭結(jié)點所對應(yīng)的頂點存在鄰接結(jié)點, 則把鄰接結(jié)點依次存放于表頭結(jié)點所指向的單向鏈表中. (1) 無向圖: 下圖所示的就是一個無向圖的鄰接表結(jié)構(gòu).
從上圖中我們知道, 頂點表的各個結(jié)點由 data 和 firstedge 兩個域表示, data 是數(shù)據(jù)域, 存儲頂點的信息, firstedge 是指針域, 指向邊表的第一個結(jié)點, 即此頂點的第一個鄰接點. 邊表結(jié)點由 adjvex 和 next 兩個域組成. adjvex 是鄰接點域, 存儲某頂點的鄰接點在頂點表中的下標(biāo), next 則存儲指向邊表中下一個結(jié)點的指針. 例如: V1 頂點與 V0, V2 互為鄰接點, 則在 V1 的邊表中,，adjvex 分別為 V0 的 0 和 V2 的 2. PS: 對于無向圖來說, 使用鄰接表進(jìn)行存儲也會出現(xiàn)數(shù)據(jù)冗余的現(xiàn)象. 例如上圖中, 頂點 V0 所指向的鏈表中存 在一個指向頂點 V3 的同時，頂點 V3 所指向的鏈表中也會存在一個指向 V0 的頂點,。 (2) 有向圖: 若是有向圖, 鄰接表結(jié)構(gòu)是類似的,，但要注意的是有向圖由于有方向的. 因此, 有向圖的鄰接表分為 出邊表和入邊表(又稱逆鄰接表), 出邊表的表結(jié)點存放的是從表頭結(jié)點出發(fā)的有向邊所指的尾結(jié)點; 入邊表的表 結(jié)點存放的則是指向表頭結(jié)點的某個頂點, 如下圖所示.
(3) 帶權(quán)圖: 對于帶權(quán)值的網(wǎng)圖, 可以在邊表結(jié)點定義中再增加一個 weight 的數(shù)據(jù)域, 存儲權(quán)值信息即可, 如下 圖所示.
3.1 深度優(yōu)先搜索圖文介紹3.1.1 深度優(yōu)先搜索介紹圖的深度優(yōu)先搜索(Depth First Search)，我們再重復(fù)重復(fù)加深理解. 我們介紹下它的搜索步驟: 假設(shè)初始 狀態(tài)是圖中所有頂點均未被訪問, 則從某個 頂點(結(jié)點) v 出發(fā), 首先訪問該頂點, 然后依次從它的各個未被訪問 的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖, 直至圖中所有和 頂點 v 有路徑相通的頂點都被訪問到. 若此時, 尚有其他頂 點未被訪問到, 則另選一個未被訪問的頂點作起始點, 重復(fù)上述過程, 直至圖中所有頂點都被訪問到為止. 顯然,， 深度優(yōu)先搜索對于圖這類結(jié)構(gòu)很容易被遞歸過程所構(gòu)造. 3.1.2 深度優(yōu)先搜索圖解3.1.2.1 無向圖的深度優(yōu)先搜索下面以"無向圖"為例, 來對深度優(yōu)先搜索進(jìn)行演示.
對上面的 圖 G1 進(jìn)行深度優(yōu)先遍歷,，從 頂點 A 開始.
第1步: 訪問 A. 第2步: 訪問(A 的鄰接點) C. 在 第1步 訪問 A 之后, 接下來應(yīng)該訪問的是 A 的鄰接點, 即 "C, D, F" 中的一個. 但在本文的實現(xiàn)中, 頂點 ABCDEFG 是按照順序存儲，C在"D和F"的前面,，因此,，先訪問C. 第3步: 訪問(C 的鄰接點) B. 在 第2步 訪問 C 之后, 接下來應(yīng)該訪問 C 的鄰接點, 即 "B和D" 中一個(A已經(jīng)被訪問過，就不算在內(nèi)) . 而由于 B 在 D 之前, 先訪問 B. 第4步: 訪問(C 的鄰接點) D. 在 第3步 訪問了 C 的鄰接點 B 之后, B 沒有未被訪問的鄰接點; 因此, 返回訪問 C 的另一個鄰接點 D. 第5步: 訪問(A 的鄰接點) F. 前面已經(jīng)訪問了 A, 并且訪問完了 "A 的鄰接點 B 的所有鄰接點(包括遞歸的鄰接點在內(nèi))"; 因此, 此時 返回到訪問A的另一個鄰接點F,。 第6步: 訪問(F 的鄰接點) G. 第7步: 訪問(G 的鄰接點) E. 因此訪問順序是: A -> C -> B -> D -> F -> G -> E 3.1.2.2 有向圖的深度優(yōu)先搜索下面以"有向圖"為例, 來對深度優(yōu)先搜索進(jìn)行演示.
對上面的 圖 G2 進(jìn)行深度優(yōu)先遍歷, 從 頂點 A 開始.
第1步: 訪問 A. 第2步: 訪問 B. 在訪問了 A 之后, 接下來應(yīng)該訪問的是 A 的出邊的另一個頂點, 即頂點 B. 第3步: 訪問 C. 在訪問了 B 之后, 接下來應(yīng)該訪問的是 B 的出邊的另一個頂點, 即 頂點 C, E, F. 在本文實現(xiàn)的圖中, 頂 點 ABCDEFG 按照順序存儲, 因此先訪問 C. 第4步: 訪問 E. 接下來訪問 C 的出邊的另一個頂點, 即頂點 E. 第5步: 訪問 D. 接下來訪問 E 的出邊的另一個頂點, 即 頂點 B, D. 頂點 B 已經(jīng)被訪問過, 因此訪問 頂點 D. 第6步: 訪問 F. 接下應(yīng)該回溯"訪問 A 的出邊的另一個頂點 F". 第7步: 訪問 G. 因此訪問順序是: A -> B -> C -> E -> D -> F -> G 3.2 廣度優(yōu)先搜索圖文介紹3.2.1 廣度優(yōu)先搜索介紹廣度優(yōu)先搜索算法(Breadth First Search), 又稱為"寬度優(yōu)先搜索"或"橫向優(yōu)先搜索", 簡稱BFS. 它的遍歷 常規(guī)思路是: 從圖中某頂點(結(jié)點) v 出發(fā), 在訪問了 v 之后依次訪問 v 的各個未曾訪問過的鄰接點, 然后分別從 這些鄰接點出發(fā)依次訪問它們的鄰接點, 并使得"先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問 , 直至圖中所有已被訪問的頂點的鄰接點都被訪問到. 如果此時圖中尚有頂點未被訪問, 則需要另選一個未曾被 訪問過的頂點作為新的起始點, 重復(fù)上述過程, 直至圖中所有頂點都被訪問到為止. 換句話說, 廣度優(yōu)先搜索遍歷 圖的過程是以 v 為起點, 由近至遠(yuǎn), 依次訪問和 v 有路徑相通且'路徑長度'為 1, 2 ... 的頂點. 3.2.2 廣度優(yōu)先搜索圖解3.2.2.1 無向圖的廣度優(yōu)先搜索下面以"無向圖"為例, 來對廣度優(yōu)先搜索進(jìn)行演示. 還是以上面的 圖 G1 為例進(jìn)行說明.
第1步: 訪問 A. 第2步: 依次訪問 C, D, F. 在訪問了 A 之后,，接下來訪問 A 的鄰接點. 前面已經(jīng)說過, 在本文實現(xiàn)中, 頂點 ABCDEFG 按照順序存儲 的, C 在 "D 和 F" 的前面, 因此, 先訪問 C. 再訪問完 C 之后, 再依次訪問 D, F. 第3步: 依次訪問 B, G. 在 第2步 訪問完 C, D, F 之后, 再依次訪問它們的鄰接點. 首先訪問 C 的鄰接點 B, 再訪問 F 的鄰接點 G. 第4步: 訪問 E. 在 第3步 訪問完 B, G 之后, 再依次訪問它們的鄰接點. 只有 G 有鄰接點 E, 因此訪問 G 的鄰接點 E. 因此訪問順序是: A -> C -> D -> F -> B -> G -> E 3.2.2.2 有向圖的廣度優(yōu)先搜索下面以"有向圖"為例, 來對廣度優(yōu)先搜索進(jìn)行演示. 還是以上面的 圖 G2 為例進(jìn)行說明.
第1步: 訪問 A. 第2步: 訪問 B. 第3步: 依次訪問 C, E, F. 在訪問了 B 之后, 接下來訪問 B 的出邊的另一個頂點, 即 C, E, F. 前面已經(jīng)說過, 在本文實現(xiàn)中，頂點 ABCDEFG 按照順序存儲的, 因此會先訪問 C, 再依次訪問 E, F. 第4步: 依次訪問 D, G. 在訪問完 C, E, F 之后, 再依次訪問它們的出邊的另一個頂點. 還是按照 C, E, F 的順序訪問, C 的已經(jīng)全部 訪問過了, 那么就只剩下 E, F; 先訪問 E 的鄰接點 D, 再訪問 F 的鄰接點 G. 因此訪問順序是：A -> B -> C -> E -> F -> D -> G 3.3 搜索算法源碼3.3.1 鄰接矩陣圖表示的無向圖 (Matrix Undirected Graph)3.3.2 鄰接矩陣圖表示的有向圖 (Matrix Directed Graph)3.3.3 鄰接鏈表圖表示的無向圖 (List Undirected Graph)3.3.4 鄰接鏈表圖表示的有向圖 (List Directed Graph) |
|
|
