【正文】 算法與數(shù)據(jù)結構 第 5章 圖與網 第 5章 圖與網 ?圖與網 是更為復雜的數(shù)據(jù)結構 ， 數(shù)據(jù)元素之間的關系既不是線性表中的一對一的鄰接關系 ， 也不是樹型結構中的一對多的層次關系 ， 而是一種 多對多 的網狀關系 ， 任意兩個數(shù)據(jù)元素之間都可能相關 。 ?由于許多問題都可以用圖或網來表示 ， 所以其應用已滲透到語言學 、 邏輯學 、 物理 、 化學 、 電子 、通訊 、 數(shù)學等諸多學科領域 。 第 5章 圖與網 圖與網的基本概念 圖與網的存儲結構 圖的遍歷 無向連通網的最小生成樹 有向網的最短路徑 有向無環(huán)圖及其應用 圖與網的基本概念 圖與網的定義 圖的相關術語 圖的定義 ?圖 （ graph） 是由非空的頂點集合 V和描述頂點間關系的?。?或邊 ） 的集合 E組成的二元組 ， 即 G=(V， E) ?其中： ?V={vi | vi∈ dataobject}， E={ vi , vj | vi , vj∈ V}， ?dataobject是具有相同性質的數(shù)據(jù)元素 （ 即頂點 ） 的集合； ?vi , vj表示從 vi到 vj有一條邊單向相連稱作弧 ， 且稱 vi為弧尾 （ 起點 ） ， vj為弧頭 （ 終點 ） ， 此時稱圖為 有向圖（ digraph） 。 ?若 vi , vj∈ E， 必有 vj , vi∈ E， 則可以用無序對 （ vi , vj）代替這兩個有序對 ， 即從 vi 到 vj有一條雙向邊 （ 即無向邊 ，也可看作雙向邊 ） 相連稱作邊 ， 此時圖稱為 無向圖（ undigraph） 。 圖的示例 ?G1=(V1， E1) ?其中： ?V1={v1， v2， v3， v4}， ?E1={v1， v2， v1， v3， v3， v4， v4， v1}； ?G2=(V2， E2) ?其中： ?V2={v1， v2， v3， v4， v5}， ?E2={(v1， v2)， (v1， v4)， (v2， v3)， (v2， v5)， (v3， v4)， (v3， v5)} 圖的定義（續(xù)） ?如果用 n表示圖中頂點數(shù)目 ， 用 e表示邊或弧的數(shù)目 ，且不考慮頂點到自身的邊或弧 ， 那么對于無向圖 e的取值范圍是 0到 n(n1)/2， 而對于有向圖 e的取值范圍為 0到 n(n1)。 ?把具有 n(n1)/2條邊的無向圖稱為 無向完全圖 ； ?把具有 n(n1)條弧的有向圖稱為 有向完全圖 ； ?有向完全圖和無向完全圖統(tǒng)稱 完全圖 （ pleted graph） 。 ?若圖中邊或弧的數(shù)目很少則稱為 稀疏圖 （ sparse graph） ， 反之邊或弧的數(shù)目接近完全圖則稱為 稠密圖 （ dense graph） 。 子圖的定義 ?假設有兩個圖 G=（ V， E） 和 G’=（ V’， E’） ， 如果V’ V且 E’ E， 則稱 G’是 G的 子圖 （ subgraph） 。 ?子圖示例如下： ??網的定義 ?把圖中與邊或弧相關的數(shù)稱之為 權 (weight)；權可以表示從一個頂點到另一個頂點的距離 、 時間 、 電流 、 電壓 、 耗費等 ， ?通常把這種帶權圖稱作 網 （ work） ； ?當然也可以依據(jù)邊或弧有無向網和有向網的概念 。 ?網的示例如下圖： 圖與網的基本概念 圖與網的定義 圖的相關術語 圖的相關術語 ?在 無向圖 中 ， 某個頂點的度 （ degree）是指所依附于該頂點的邊的數(shù)目 ， 頂點 v的度通常記作 TD（ V） 。 例如在無向圖 G2中 ， TD（ v1） =2， TD（ v2） =3， TD（ v3）=3， TD（ v4） =2， TD（ v5） =2。 ?在 有向圖 中要區(qū)別頂點的 入度 和 出度 的概念 ， ?入度 是指以頂點 V為終點的弧的數(shù)目 ， 通常記作 ID(V)； ?出度 是指以頂點 V為始點的弧的數(shù)目 ， 通常記作 OD(V)； ?頂點的 度 定義為入度和出度的和 ， 即 : TD（ V） =ID（ V） +OD（ V） 。 圖的相關術語（續(xù)） ?例如在有向圖 G1中 ， ?ID（ v1） =1， OD（ v1） =2， TD（ v1） =3； ?ID（ v2） =1， OD（ v2） =0， TD（ v2） =1； ?ID（ v3） =1， OD（ v3） =1， TD（ v3） =2； ?ID（ v4） =1， OD（ v4） =1， TD（ v4） =2。 ?一般地 ， 對于具有 n 個頂點 e條邊或弧的圖 ， 邊或弧的個數(shù)與各頂點的度 TD（ vi） 之間滿足如下關系： 圖的相關術語（續(xù)） ?在 無向圖 G=（ V， E） 中 ， 若 （ vp， vi1） ， （ vi1，vi2） … （ vin， vq） 都是 E中的邊 ， 則稱結點序列 vp， vi1， vi2 … vin， vq為從 vp到 vq的一條 路徑 ； ?在 有向圖 中 ， 則要求 vp， vi1， vi1， vi2 … vin， vq都是 E中的 弧 。 ?路徑 （ path） 長度 定義為路徑上邊或弧的數(shù)目； ?如有向圖 G1中有 v3， v4， v4， v1， v1， v2，所以說從 V3到 V2存在一條長度為 3的路徑； ?如無向圖 G2有 (v1， v2)， (v2， v5)和 (v1， v4)，(v4， v3)， (v3， v5)， 所以說從 V1到 V5存在一條長度各為 2和 3的路徑 。 圖的相關術語（續(xù)） ?如果頂點序列中不出現(xiàn)重復頂點 ， 則稱頂點序列為 簡單路徑 ， 例如前面所舉三條路徑的頂點序列分別為 v v v v2和 v v v5與 v v v v5， 均無重復頂點出現(xiàn)都是簡單路徑 。 ?第一個頂點和最后一個頂點相同 （ 即 vp =vq） 的簡單路徑稱為 簡單回路 或 環(huán) （ cycle） ， ?例如在有向圖 G1中的 v1， v3， v4， v1和無向圖 G2中的 v1，v4， v3， v2， v1與 v2， v3， v5， v2等都是簡單回路或環(huán) 。 圖的相關術語（續(xù)） ?在無向圖中 ， 如果從一個頂點 vi到另一個頂點vj 有路徑 ， 則稱 vi和 vj是 連通的 ；如果圖中任意兩個頂點 vi和 vj都是連通的 ， 則稱該無向圖是連通圖 （ connected graph） 。 例如無向圖 G2是連通圖 ， ?而如下無向圖 G5是 非連通圖 。 圖的相關術語（續(xù)） ?無向圖的極大連通子圖稱為圖的 連通分量 （ connected ponent） 。 ?例如下圖給出了無向圖 G5的兩個連通分量 。 圖的相關術語（續(xù)） ?在有向圖中 ， 如果對于任意兩個頂點 vi和 vj（ vi≠v j） 從 vi到 vj和從 vj到 vi都存在路徑 ， 則稱該有向圖為 強連通圖（ strong graph） 。 ?有向圖的極大強連通子圖稱為圖的 強連通分量 （ strongly connected ponent） 。 ?例如有向圖 G1不是強連通圖 ， 它的兩個強連通分量如下圖所示 。 圖的相關術語（續(xù)） ?一個連通圖的 生成樹 （ spanning tree） 是該圖的一個極小連通子圖 ， 它包含圖中全部的 n個頂點和連通這 n個頂點的 n1條邊 。 ?如果在生成樹上添加任意一條原圖中的其它邊必定會產生回路或環(huán)；換句話說 ， 有 n個頂點 n條或 n條以上邊的無向圖一定存在回路或環(huán) 。 如果 n個頂點的圖其邊數(shù)少于 n1條 ，則一定是非連通圖 。 ?例如無向圖 G2的一棵生成樹如下圖所示 。 圖的相關術語（續(xù)） ?在 非連通圖 中 ， 由每個連通分量都可以得到一個極小連通子圖 ， 即一棵生成樹 ， 這些連通分量的生成樹就構成了該非連通圖的 生成森林 。 ?對于有向圖 ， 其生成樹或生成森林必定是有向樹和有向森林 。 ?例如無向圖 G5的生成森林如下圖所示 。 第 5章 圖與網 圖與網的基本概念 圖與網的存儲結構 圖的遍歷 無向連通網的最小生成樹 有向網的最短路徑 有向無環(huán)圖及其應用 圖和網的存儲結構 ?由于圖的結構復雜 ， 其數(shù)據(jù)元素間存在著多對多的網狀關系 ， 所以無法用物理位置關系表示元素間的邏輯關系 ， 即不存在順序存儲結構； ?但可借用數(shù)組來表示元素間的邏輯關系 。 由于圖中頂點的度差別一般較大 ， 故也不宜采用多重鏈表存儲結構； ?但可根據(jù)圖的具體情況和需要進行的操作 ， 設計恰當?shù)慕Y點結構和表結構來存儲頂點信息和頂點間的關系 ， 圖與網的存儲結構 鄰接矩陣 鄰接表與逆鄰接表 鄰接多重表 鄰接矩陣 ?所謂 鄰接矩陣 （ adjacency matrix） 存儲結構 ， 就是用一維數(shù)組存儲圖或網的頂點信息 ， 用二維數(shù)組表示頂點之間的鄰接關系 （ 即鄰接矩陣 ） 。 ?若 G=（ V， E） 是具有 n個頂點的圖或網 ， G的鄰接矩陣 A是如下定義的 n階方陣： ?當 G是無向圖或有向圖時 ， 矩陣 A中元素定義為 鄰接矩陣（續(xù)） ?當 G是無向網或有向網時 ， 矩陣 A中元素定義為 ?其中： Wij表示邊或弧上的權值 ， ∞ 表示一個所用計算機上所允許的大于所有權值的數(shù)或者一個特殊的其它值 。 鄰接矩陣存儲結構舉例 鄰接矩陣存儲 鄰接矩陣存儲 鄰接矩陣存儲結構舉例 (續(xù) ) 鄰接矩陣存儲 鄰接矩陣存儲 鄰接矩陣存儲結構的特點 ?從圖的鄰接矩陣存儲表示容易看出該表示法具有如下特點： ?無向圖或網的鄰接矩陣一定是一個對稱矩陣 ， 因此在存儲鄰接矩陣時可以只存儲其上三角陣或下三角陣以節(jié)省存儲空間 。 ?對于無向圖或網 ， 其鄰接矩陣中第 i行 （ 或第 i列 ） 中非零元素 （ 或非 ∞ 元素 ） 的個數(shù)正好是第 i個頂點的度 。 即 鄰接矩陣存儲結構的特點 (續(xù) ) ?對于有向圖或網 ， 其鄰接矩陣中第 i行中非零元素 （ 或非∞ 元素 ） 的個數(shù)正好是第 i個頂點的出度 OD(vi)， 而第 i列中非零元素 （ 或非 ∞ 元素 ） 的個數(shù)正好是第 i個頂點的入度 ID(vi) 。 即 ?很容易確定圖或網中任意兩個頂點之間是否有邊或弧相連；但要確定圖或網中有多少條邊或弧則需要逐行逐列掃描方陣 ， 時間代價是 O(n2)， 這是該方法的局限性 。 鄰接矩陣存儲圖或網的類型定義 ?用一維數(shù)組存儲頂點信息 ， 用鄰接矩陣存儲頂點間關系信息的圖或網的形式描述如下： define maxvernum 100 define infinity maxinteger typedef struct {vertextype vex[maxvernum]。 int adjmatrix[maxvernum][maxvernum]。 int n,e。 /*定義頂點數(shù)和邊或弧數(shù)變量單元 */ }mgraph。 圖與網的存儲結構 鄰接矩陣 鄰接表與逆鄰接表 鄰接多重表 鄰接表 ?鄰接表 （ adjacency list） 是圖和網的一種鏈式存儲結構 。在鄰接表中 ， 對圖或網中的每個頂點建立一個單鏈表 ， 第 i個單鏈表中的結點是與 vi相關聯(lián)的邊所聯(lián)結的結點 （ 對有向圖是以頂點 vi為尾的弧所聯(lián)結的結點 ， 即弧頭結點 ） 。 ?每個結點由三個域組成 ， 其中：鄰接點域 adjvex指示與頂點vi鄰接的點在圖中的位置 ， 鏈域 next指示下一條邊或弧所聯(lián)結的結點 ， 數(shù)據(jù)域 info存儲和邊或弧相關的信息 （ 如網中的權值等 ） 。 每個單鏈表都附設一個表頭結點 ， 如下圖所示 。 鄰接表（續(xù)） ?除了設有鏈域 next指向鏈表中的第一個結點外 ， 還設有數(shù)據(jù)域 data存放頂點 vi的有關信息 （ 如頂點名 ， 頂點位置等 ） 。 ?這些表頭結點也可以組織為一個鏈表 ， 但通常以向量形式存儲于一維數(shù)組中 ， 以方便隨機訪問任一頂點的單鏈表 。 ?例如有向網 G3的鄰接表如下圖所示 。 鄰接表舉例 ?無向網 G4的鄰接表如下圖所示 。 鄰接表中結點和表頭結點的形式描述 ? 鄰接表中結點和表頭結點的形式描述定義如下： define maxvernum 100 typedef struct node /*定義表結點結構 */ {int adjvex,info。 struct node *next。 } nodetype。 typedef struct frontnode /*定義表