【正文】 ? ????????????中的邊或弧不是或：若中的邊或弧是或：若 VR v v v v VR v v v v wji,Ajijijijiij,),(,),(v2 v1 v3 v4 v5 v6 5 4 8 9 7 5 5 6 1 3 ??????????????????????????????????????????????????1356598475v1 v2 v3 v4 v5 v6 v1 v2 v3 v4 v5 v6 11 頂點(diǎn)表結(jié)點(diǎn) data firstarc 邊表結(jié)點(diǎn) adjvex nextarc info v2 v1 v3 v4 v5 G2 v1 v3 v4 v2 v5 0 1 2 3 4 3 ^ 1 4 2 ^ 0 4 3 ^ 1 2 ^ 0 2 ^ 1 鏈域 ，指示下一條邊或弧。 ? 有向圖中 頂點(diǎn) vi的 出度 是鄰接矩陣中第 i行 1的個(gè)數(shù)?？臻g復(fù)雜度 O(n2)，用于稀疏圖時(shí)空間浪費(fèi)嚴(yá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)： ? 無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有 n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為 n(n1)/2。 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ǔ)。 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)連通圖。 連通圖： 無向圖中任意兩個(gè)頂點(diǎn)都是連通的。有路徑，則說 v和 v180。 簡(jiǎn)單回路 (簡(jiǎn)單環(huán) )： 前后兩端點(diǎn)相同的簡(jiǎn)單路徑。 回路 (環(huán) )： 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。 對(duì)于有向圖，路徑也是有向的。的路徑是一個(gè)頂點(diǎn)序列 (v= vi, 0, vi, 1, …, vi, m=v180。 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)。 出度： 有向圖 中以頂點(diǎn) v 為起點(diǎn)的弧數(shù)目稱為 v 的出度，記 OD(v)。 圖的定義和基本術(shù)語 5 度： 無向圖 中頂點(diǎn) v 的度是和 v 相關(guān)聯(lián)的邊的數(shù)目，記為 TD(v)?？? 以表示為： G＝ (V, {VR}) 其中 V 是 頂點(diǎn) 的有窮非空集合； VR 是 頂點(diǎn)之間關(guān)系 的有窮集合，也叫做 弧 或 邊 集合。 給森林中的各子樹加上一個(gè)雙親結(jié)點(diǎn)，森林就變成了樹。 一棵樹可以看成是一個(gè)特殊的森林。 無序樹： 樹中結(jié)點(diǎn)的各子樹無次序。 第 1 層 第 2 層 第 3 層 第 4 層 堂兄弟 雙親在同一層的結(jié)點(diǎn) 樹的 深度： 樹中結(jié)點(diǎn)的最大層次。 雙親 孩子 兄弟 結(jié)點(diǎn)的 祖先： 從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。 T3 T2 T1 基本術(shù)語： 結(jié)點(diǎn)的 度： 結(jié)點(diǎn)擁有的子樹數(shù)。 樹的定義是一個(gè)遞歸的定義。1 圖搜索基礎(chǔ) 2 樹的定義和基本術(shù)語 定義： 樹 (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)。 3 樹的邏輯結(jié)構(gòu)： 樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼結(jié)點(diǎn) 但至多只能有一個(gè)直接前趨結(jié)點(diǎn)。 度 = 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)為根的子樹中的任一結(jié)點(diǎn)。 有序樹： 樹中結(jié)點(diǎn)的各子樹從左至右有次序 (最左邊的為第一個(gè)孩子 )。 結(jié)點(diǎn)： 數(shù)據(jù)元素 + 指向子樹的分支 森林： 是 m (m≥0) 棵互不相交的樹的集合。 把根結(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)系 (也稱弧或邊 )集合組成?；?是頂點(diǎn)的有序?qū)Γ? 邊是頂點(diǎn)的無序?qū)?。 v2 v1 v3 v4 v5 入度： 有向圖 中以頂點(diǎn) v 為終點(diǎn)的弧數(shù)目稱為 v 的入度，記 ID(v)。 度： 入度和出度之和，即： TD(v) = ID(v) + OD(v)。 6 路徑： 從頂點(diǎn) v到 v180。)， 滿足 (vi, j1, vi, j)?VR 或 vi, j1, vi, j ?VR (1 ? j ? m)。 v2 v1 v3 v4 v5 v2 v1 v3 v4 路徑