【正文】 1 圖搜索基礎(chǔ) 2 樹的定義和基本術(shù)語(yǔ) 定義： 樹 (Tree) 是 n (n≥0) 個(gè)結(jié)點(diǎn)的有限集。 若 n = 0， 稱 為空樹； 若 n 0，則 它滿足如下兩個(gè)條件： (1) 有且僅有一個(gè)特定的稱為 根 (Root) 的結(jié)點(diǎn)； (2) 其余結(jié)點(diǎn)可分為 m (m≥0) 個(gè)互不相交的有限集 T1, T2, T3, …, Tm，其中每一個(gè)集合本身又是一棵樹，并稱為 根的 子樹 (SubTree)。 樹的定義是一個(gè)遞歸的定義。 3 樹的邏輯結(jié)構(gòu)： 樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼結(jié)點(diǎn) 但至多只能有一個(gè)直接前趨結(jié)點(diǎn)。 T3 T2 T1 基本術(shù)語(yǔ)： 結(jié)點(diǎn)的 度： 結(jié)點(diǎn)擁有的子樹數(shù)。 度 = 0 葉子 終端結(jié)點(diǎn) 度 ≠ 0 分支結(jié)點(diǎn) 非終端 結(jié)點(diǎn) 根結(jié)點(diǎn)以 外的分支 結(jié)點(diǎn)稱為 內(nèi)部結(jié)點(diǎn) 樹的 度： 樹內(nèi)各結(jié)點(diǎn)的度的最大值。 雙親 孩子 兄弟 結(jié)點(diǎn)的 祖先： 從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。 結(jié)點(diǎn)的 子孫： 以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)。 第 1 層 第 2 層 第 3 層 第 4 層 堂兄弟 雙親在同一層的結(jié)點(diǎn) 樹的 深度： 樹中結(jié)點(diǎn)的最大層次。 有序樹： 樹中結(jié)點(diǎn)的各子樹從左至右有次序 (最左邊的為第一個(gè)孩子 )。 無(wú)序樹： 樹中結(jié)點(diǎn)的各子樹無(wú)次序。 結(jié)點(diǎn)： 數(shù)據(jù)元素 + 指向子樹的分支 森林： 是 m (m≥0) 棵互不相交的樹的集合。 一棵樹可以看成是一個(gè)特殊的森林。 把根結(jié)點(diǎn)刪除樹就變成了森林。 給森林中的各子樹加上一個(gè)雙親結(jié)點(diǎn)，森林就變成了樹。 樹 森林 一定是 不一定是 E F G H I A B C D J K L M 4 定義： 圖 (Graph) 是 一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，由頂 點(diǎn)集合及頂點(diǎn)間的關(guān)系 (也稱弧或邊 )集合組成?？? 以表示為： G＝ (V, {VR}) 其中 V 是 頂點(diǎn) 的有窮非空集合； VR 是 頂點(diǎn)之間關(guān)系 的有窮集合，也叫做 弧 或 邊 集合。弧 是頂點(diǎn)的有序?qū)Γ? 邊是頂點(diǎn)的無(wú)序?qū)?。 圖的定義和基本術(shù)語(yǔ) 5 度： 無(wú)向圖 中頂點(diǎn) v 的度是和 v 相關(guān)聯(lián)的邊的數(shù)目，記為 TD(v)。 v2 v1 v3 v4 v5 入度： 有向圖 中以頂點(diǎn) v 為終點(diǎn)的弧數(shù)目稱為 v 的入度，記 ID(v)。 出度： 有向圖 中以頂點(diǎn) v 為起點(diǎn)的弧數(shù)目稱為 v 的出度，記 OD(v)。 度： 入度和出度之和，即： TD(v) = ID(v) + OD(v)。 v2 v1 v3 v4 如果頂點(diǎn) vi 的度為 TD(vi)，則一個(gè)有 n 個(gè)頂點(diǎn) e 條邊 (弧 ) 的圖，滿足如下關(guān)系： ???niivTDe1)(21終端頂點(diǎn) ：有向圖中把出度為 0的頂點(diǎn)稱為終端頂點(diǎn)。 6 路徑： 從頂點(diǎn) v到 v180。的路徑是一個(gè)頂點(diǎn)序列 (v= vi, 0, vi, 1, …, vi, m=v180。)， 滿足 (vi, j1, vi, j)?VR 或 vi, j1, vi, j ?VR (1 ? j ? m)。 對(duì)于有向圖，路徑也是有向的。 v2 v1 v3 v4 v5 v2 v1 v3 v4 路徑長(zhǎng)度： 路徑上邊或弧的數(shù)目。 回路 (環(huán) )： 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。 簡(jiǎn)單路徑： 序列中頂點(diǎn) (兩端點(diǎn)除外 )不重復(fù)出現(xiàn)的路徑。 簡(jiǎn)單回路 (簡(jiǎn)單環(huán) )： 前后兩端點(diǎn)相同的簡(jiǎn)單路徑。 連通： 無(wú)向圖中從頂點(diǎn) v到 v180。有路徑，則說 v和 v180。是連通的 。 連通圖： 無(wú)向圖中任意兩個(gè)頂點(diǎn)都是連通的。 v2 v1 v3 v4 v5 7 連通分量： 無(wú)向圖的極大連通子圖；任何連通圖的連通分量只有一個(gè)，即其本身；非連通圖有多個(gè)連通分量 (非連通圖的每一個(gè)連通部分 )。 v2 v1 v3 v4 v5 v2 v1 v3 v4 v5 強(qiáng)連通圖： 有向圖 G中，若對(duì)于 V(G)中任意兩個(gè)不同的頂點(diǎn) vi和 vj，都存在從 vi到 vj以及從 vj到 vi的路徑，則稱 G是強(qiáng)連通圖。 v2 v1 v3 v4 強(qiáng)連通分量： 有向圖的極大強(qiáng)連通子圖；任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其本身；非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。 v2 v1 v3 v4 v2 v1 v3 v4 8 ? ?????????????中的邊或弧不是或：若中的邊或弧是或：若 VR v v v v VR v v v v ji,Ajijijiji,),(0,),(1 對(duì)于一個(gè)具有 n個(gè)頂點(diǎn)的圖，可用兩個(gè)數(shù)組存儲(chǔ)。其中一個(gè)一維數(shù)組存儲(chǔ)數(shù)據(jù)元素 (頂點(diǎn) )的信息，另一個(gè)二維數(shù)組 (圖的鄰接矩陣 )存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系 (邊或弧 )信息。 鄰接矩陣： 設(shè) G = (V, {VR}) 是具有 n 個(gè)頂點(diǎn)的圖，頂點(diǎn)的順序依次為 {v1, v2, …, vn}，則 G 的鄰接矩陣是具有如下性質(zhì)的 n 階方陣： 圖的存儲(chǔ)結(jié)構(gòu)之?dāng)?shù)組表示法 (鄰接矩陣表示法 ) 9 ??????????????????0011000101110101010101010??????????????0001100000000110v2 v1 v3 v4 G1 v2 v1 v3 v4 v5 G2 v1 v2 v3 v4 v1 v2 v3 v4 v5 v1 v2 v3 v4 v1 v2 v3 v4 v5 特點(diǎn)： ? 無(wú)向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有 n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為 n(n1)/2。 ? 有向圖鄰接矩陣不一定對(duì)稱；有 n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為 n178。，空間復(fù)雜度 O(n2)，用于稀疏圖時(shí)空間浪費(fèi)嚴(yán)重。 ? 無(wú)向圖中頂點(diǎn) vi的度 TD(vi) 是鄰接矩陣中第 i行 1的個(gè)數(shù)。 ? 有向圖中 頂點(diǎn) vi的 出度 是鄰接矩陣中第 i行 1的個(gè)數(shù)。 頂點(diǎn) vi的 入 度 是鄰接矩陣中第 i列 1的個(gè)數(shù)。 10 網(wǎng)的鄰接矩陣可定義為： ? ????????????中的邊或弧不是或：若中的邊或弧是或：若 VR v v v v VR v v v v wji,Ajijijijiij,