第3章-數(shù)據(jù)結(jié)構(gòu)(參考版)
2024-08-16 19:42本頁面
【正文】 然后，再順序訪問Ｗ １ ，Ｗ ２ ， … ，Ｗ ｔ 的所有的鄰接點(diǎn)（已被訪問過的頂點(diǎn)除外），再從這些被訪問的點(diǎn)出發(fā)，逐次進(jìn)行訪問，依次類推，直到所有頂點(diǎn)都被訪問到為止。 1 2 3 4 5 6 7 8 Ｖ １ → Ｖ ２ → Ｖ ４ → Ｖ ８ → Ｖ ５ → Ｖ ６ → Ｖ ３ → Ｖ ７ 50 167。然后，從Ｗ ２ 出發(fā)進(jìn)行如上的訪問。 ? 深度優(yōu)先搜索： ? 廣度優(yōu)先搜索： 49 167。 圖 V2 V1 V3 V4 V1 V2 V3 V4 2 4 ? 3 ? 2 ? 3 ? V1 ? V2 V3 V4 1 3 ? 2 4 ? 1 ? 出邊表 入邊表 48 167。 圖 二、存儲(chǔ) ? 相鄰矩陣表示法 ? 若 G是一個(gè)具有 n個(gè)節(jié)點(diǎn)的有向圖，則 G的相鄰矩陣為： A[i, j] = 1 若 (Vi,Vj)或 (Vj,Vi)是圖 G的邊 0 若 (Vi,Vj)或 (Vj,Vi)不是圖 G的邊 { V2 V1 V3 V4 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 V2 V1 V3 V4 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 46 167。 圖 一、定義 ? 有限的節(jié)點(diǎn)集合 K，對 K中節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)的個(gè)數(shù)不加限制，則就是圖結(jié)構(gòu) ? 用 G=(V, E)表示一個(gè)圖，圖的節(jié)點(diǎn)稱為頂點(diǎn)， V是有窮頂點(diǎn)的集合，節(jié)點(diǎn)的偶對稱為邊， E是邊的集合 ? 如果節(jié)點(diǎn)的偶對是無序的，則稱為 無向圖 ；如果節(jié)點(diǎn)的偶對是有序的，則稱為 有向圖 ? 在無向圖中，若頂點(diǎn) Vi與 Vj之間有一條邊 (Vi, Vj)，則稱 Vi與 Vj鄰接，稱邊 (Vi, Vj)依附于頂點(diǎn) Vi, Vj；依附于頂點(diǎn)邊的個(gè)數(shù)稱為 度 ? 在有向圖中，進(jìn)入該頂點(diǎn)的有向邊的個(gè)數(shù)為入度，由該頂點(diǎn)引出的有向邊的個(gè)數(shù)為出度， 度 =入度 +出度 44 167。 樹 三、存儲(chǔ)方式 ? 一般采用鏈表存儲(chǔ) 數(shù)據(jù) 指針 1 指針 2 …… 指針 m 指向直接 后繼節(jié)點(diǎn) A B C G H F D E 數(shù)據(jù) 指針 1 指針 2 指針 3 指針 4 A B C ? B D E F ? C G H ? D ? E ? F ? G ? H ? 42 167。 樹 ? 后根次序 ? 在后根次序下遍歷頭一棵樹樹根的子樹 ? 訪問頭一棵樹的根 ? 在后根次序下遍歷其他的樹 A B C G H F D E J I D I J E F B G H CA 40 167。 樹 A B C G H F D E J I A B C G H F D E J I (A(B(D)(E(I)(J))(F))(C(G)(H))) 樹形表示 文氏圖表示 嵌套括號表示 38 167。 樹 一、定義 ? 樹結(jié)構(gòu)是節(jié)點(diǎn)之間有分支的、層次的關(guān)系的結(jié)構(gòu) ? 樹結(jié)構(gòu)是非線性結(jié)構(gòu) ? 線性： 數(shù)據(jù)元素能按一定的順序進(jìn)行排列，其中除第一和最后一個(gè)外，其它元素都有一個(gè)唯一的前驅(qū)元素和后繼元素，即元素之間存在著唯一的關(guān)系 ? 樹 ? 樹是 n個(gè)節(jié)點(diǎn)的有窮集合 K，滿足： ①有且僅有一個(gè)節(jié)點(diǎn)沒有前驅(qū)，稱為樹的根 ②除根之外，其他節(jié)點(diǎn)有且僅有一個(gè)前驅(qū) ③任一節(jié)點(diǎn)都存在一個(gè)從根到該節(jié)點(diǎn)的節(jié)點(diǎn)序列 36 167
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1