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