【正文】 e() 開始 r = 0？ Y 申請(qǐng)結(jié)點(diǎn)空間 r = 0？ 顯示“溢出” 結(jié)束 根結(jié)點(diǎn)的處理 N Y N rleft = 0。若 aj的左子非空 ,則繼續(xù)尋找合適的插入位置 。 最短路徑 ? 研究的是類似于交通調(diào)度一類的帶權(quán)有向圖問題 。 – 輸出序列即為拓?fù)渑判蛐蛄?。例如課程間優(yōu)先關(guān)系有向圖問題 。 – 從 U={u0} （ u0 ? V） ， TE= 空開始； – 重復(fù)執(zhí)行： 在所有 u?U， v ?VU的邊 （ u， v）?E中找一條代價(jià)最小的邊 （ u0， v0） 并入 TE，同時(shí) u0并入 U， 直到 U=V為止； – 此時(shí) TE中必有 n1條邊 ， 則 T=（ V， TE） 為 N的最小生成樹 。一棵生成樹的代價(jià)就是樹上各邊 （ 弧 ） 的代價(jià)之和 。 ? INS_ARC(G,v,w) 在圖 G中插入一條從頂點(diǎn) v到頂點(diǎn) w的弧 。 ? GET_VERTEX（ G， i） 求圖 G中第 i個(gè)頂點(diǎn) 。 廣度優(yōu)先遍歷法舉例 遍歷過程 訪問頂點(diǎn) 所過邊 ?起始頂點(diǎn) V1 V1 ?訪問 V1的未被訪問過 的所有鄰接點(diǎn) V3,V2,V4 （ V1， V3） (V1,V2) (V1,V4) ?訪問 V3的未被訪問過 的所有的鄰接點(diǎn) V5 （ V3， V5） ?訪問 V2的未被訪問過 的所有的鄰接點(diǎn) 無 ?訪問 V4的未被訪問過 的所有的鄰接點(diǎn) V6 (V4,V6) ?所有頂點(diǎn)已被訪問 ,結(jié)束。即先訪問第 1個(gè)頂點(diǎn)所有鄰接點(diǎn)后，再訪問下一個(gè)頂點(diǎn)所有未被訪問的鄰接點(diǎn)。 top 。 top++。 p=G[v].firstarc。 printf(“%d ”,G[v].data)。 ARCNODE *p。 重復(fù)上述過程 ， 直到不存在未訪問過的鄰接點(diǎn)為止 。 出發(fā)點(diǎn)不同 ，任一頂點(diǎn)的鄰接點(diǎn)就不相同 ， 路徑也就不同 。j,amp。 snextarc = G[i].firstarc。amp。amp。i,amp。 k++ ) { scanf( “%d”, amp。 float w。 例如 G2的逆鄰接表為： 1 2 3 4 4 1 1 3 ^ ^ ^ ^ 顯然逆鄰接表的單鏈表中結(jié)點(diǎn)的個(gè)數(shù)就是頂點(diǎn) Vi的入度。 ? 在鄰接表中 ， 每個(gè)頂點(diǎn)由三個(gè)域組成： ? 每個(gè)單鏈表附設(shè)一個(gè)頭結(jié)點(diǎn) ， 結(jié)構(gòu)為： adjvex data nextarc 頂點(diǎn) Vi的鄰接點(diǎn) 與邊或弧有關(guān)的權(quán)值 指向 Vi的下一個(gè) 鄰接點(diǎn)的指針 Vexdata firstarc 指向 Vi單鏈表的第一個(gè)結(jié)點(diǎn) 存放 Vi信息 鄰接表存儲(chǔ)結(jié)構(gòu)描述 C語言描述 define VTXNUM n struct arode { int adjvex； float data； struct arode *nextarc； }； typedef struct arode ARCNODE ； struct headnode { int data ； ARCNODE * firstarc ； } adjlist[VTXNUM]； 無向圖 G1的鄰接表 V1 V2 V3 V4 ^ V3 V2 V1 V4 ^ V3 ^ V1 V2 ^ V2 頂點(diǎn) Vi的度恰好就是 第 i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。 例 ， G2中 ， V2的出度為 0（ 第 2行的元素之和為 0） ， V1的入度為 1（ 第 1列的元素之和為 1） 。 有向圖鄰接矩陣 ? 定義 設(shè)圖 G=（ V， E） 是有 n（ n ? 1） 個(gè)頂點(diǎn)的圖 ， 則 G的鄰接矩陣是具有下述性質(zhì)的 nxn的方陣 ， 元素為： 1 當(dāng) 〈 Vi， Vj? E 時(shí) A[ i， j] = 0 當(dāng) 〈 Vi， Vj? E 時(shí) 例如 ， G2的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 4x4 1 3 2 4 G2 無向圖鄰接矩陣 ? 定義 設(shè)圖 G=（ V， E）是有 n（ n ? 1）個(gè)頂點(diǎn)的圖，則 G的鄰接矩陣是具有下述性質(zhì)的對(duì)稱陣，元素為： 1 當(dāng) (Vi， Vj） ? E 時(shí) A[ i， j] =A[j,i] = 0 當(dāng) (Vi， Vj） ? E 時(shí) 例如， G1的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4 o o o o v1 v2 v3 v4 G1 求圖中頂點(diǎn)的度 ? 借助鄰接矩陣 ,可以很容易地求出圖中頂點(diǎn)的度 。 但借助數(shù)組可以用來表示頂點(diǎn)之間的關(guān)系 。 ? 網(wǎng) （ Network） 帶權(quán)的圖稱為網(wǎng) 。G的生成樹不是唯一的 。 如圖 G4所示 。 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 連通圖、強(qiáng)連通圖、連通分 量 1 2 ? 連通圖（ Connected Graph） 在無向圖中，若每一對(duì)頂點(diǎn)間都有路徑，稱此圖是連通圖。 路徑可能是不唯一的 。 例如 G2中頂點(diǎn) 1的出度為 2。 例如 ， G1中 V2的度為 3， V4的度為 1。 如圖 G G2中的Ｖ Ｖ 2， 1， 2。 弧是有序的 ， 〈 Vx， Vy〉 表示從Vx到 Vy。記為： （ Vx， Vy） 。如圖 G2所示。 在 DS中 ， 只討論圖在計(jì)算機(jī)中的實(shí)現(xiàn)和操作 。教學(xué)目標(biāo) ? 了解有關(guān)圖的 – 基本概念 – 存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) – 遍歷算法 教學(xué)要求 ? 通過本單元學(xué)習(xí)，了解、掌握有關(guān)圖 : – 基本概念 ?有向圖、無向圖、連通圖、網(wǎng) – 存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) ?鄰接矩陣、鄰接表 – 遍歷及其它操作 ?深度優(yōu)先、廣度優(yōu)先遍歷 – 應(yīng)用 本單元涉及的內(nèi)容 ? 第 2章 – – – – ? P73~P90 一、 圖及其基本概念 ? 圖是一種較之線性表和樹形結(jié)構(gòu)更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu) 。 有關(guān)圖的理論 ， 在 “ 離散數(shù)學(xué) ”的圖論中有詳細(xì)論述和證明 。 ? 例 ， 圖 G1 = （ V， E） V={v1， v2， v3， v4} E={（ v1， v2） ， （ v1， v3） ， （ v2， v1） ， （ v2， v3） ， （ v2， v4） ， （ v3， v1） ， （ v3， v2） ， （ v4， v2） } o o o o v1 v2 v3 v4 G1 有向圖、無向圖 ? 有向圖（ Digraph） 圖 G中頂點(diǎn)的偶對(duì)若是有向的，形成的圖稱有向圖。 ? G2=（ V， E） V={ 1， 2， 3， 4} E={〈 1， 2〉 ， 〈 1， 3〉 ， 〈 3， 4〉 ， 〈 4， 1〉 } 1 3 2 4 G2 邊、弧 ? 邊 （ Edge） 頂點(diǎn)間的關(guān)系可描述為頂點(diǎn)的偶對(duì) ， 也稱為頂點(diǎn)的邊 。記為： 〈 Vx， Vy〉 。 弧 〈 Vx， Vy〉 表示為 ， Vx Vy 弧尾 弧頭 頂點(diǎn)、鄰接點(diǎn) ? 頂點(diǎn) （ Vertex） 圖中的數(shù)據(jù)元素 （ 結(jié)點(diǎn) ） 稱為頂點(diǎn) 。 Vx Vy Ｖ x、Ｖ y互為鄰接點(diǎn) Vx Vy Ｖ y是Ｖ x的鄰接點(diǎn) 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 頂點(diǎn)的度（ Degree） ? 無向圖中 ， 頂點(diǎn)的 度 是以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的條數(shù) 。 以某頂點(diǎn)為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度 （ Outdegree） 。 o o o o v1 v