【正文】 第 7章 圖 本章中介紹下列主要內(nèi)容： ? 圖的定義 ? 圖的存儲結(jié)構(gòu) ? 圖的遍歷操作 ? 圖的幾個典型問題 第 7章 圖 圖 (Graph)是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 線性結(jié)構(gòu) ：是研究數(shù)據(jù)元素之間的一對一關(guān)系。在這種結(jié)構(gòu)中，除第一個和最后一個元素外，任何一個元素都有唯一的一個直接前驅(qū)和直接后繼。 樹結(jié)構(gòu) ：是研究數(shù)據(jù)元素之間的一對多的關(guān)系。在這種結(jié)構(gòu)中，每個元素對下 (層 )可以有 0個或多個元素相聯(lián)系，對上 (層 )只有唯一的一個元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。 圖結(jié)構(gòu) ：是研究數(shù)據(jù)元素之間的多對多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個元素之間可能存在關(guān)系。即結(jié)點之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。 圖的應(yīng)用極為廣泛，已滲入到諸如語言學、邏輯學、物理、化學、電訊、計算機科學以及數(shù)學的其它分支。 第 7章 圖 圖的基本概念 圖的定義和術(shù)語 一個圖 (G)定義為一個偶對 (V,E) ，記為 G=(V,E) 。其中： V是 頂點 (Vertex)的非空有限集合，記為 V(G)； E是無序集 Vamp。V的一個子集，記為 E(G) ，其元素是圖的 弧 (Arc)。 將頂點集合為空的圖稱為空圖。其形式化定義為： G=(V ， E) V={v|v?data object} E={v,w| v,w?V∧ p(v,w)} P(v,w)表示從頂點 v到頂點 w有一條直接通路。 弧 (Arc) ： 表示兩個頂點 v和 w之間存在一個關(guān)系，用頂點偶對 v,w表示。通常根據(jù)圖的頂點偶對將圖分為有向圖和無向圖。 有向圖 (Digraph)： 若圖 G的關(guān)系集合 E(G)中，頂點偶對 v,w的 v和 w之間是 有序 的 ，稱圖 G是有向圖。 在有向圖中，若 v,w?E(G) ，表示從頂點 v到頂點 w有一條 弧 。 其中： v稱為 弧尾 (tail)或 始點(initial node)， w稱為 弧頭 (head)或 終點 (terminal node) 。 定義和術(shù)語（ 2） 無向圖 (Undigraph)： 若圖 G的關(guān)系集合 E(G)中，頂點偶對 v,w的 v和 w之間是 無序 的，稱圖G是無向圖。 在無向圖中，若 ?v,w?E(G) ，有w,v?E(G) ，即 E(G)是對稱，則用無序?qū)?(v,w) 表示 v和 w之間的一條 邊 (Edge)，因此 (v,w) 和(w,v)代表的是同一條邊。 定義和術(shù)語（ 3） 例 1：設(shè)有有向圖 G1和無向圖 G2，形式化定義 ： G1=(V1 ， E1) V1={a,b,c,d,e} E1={a,b,a,c, a,e,c,d,c,e ,d,a,d,b,e,d} G2=(V2 ， E2) V2={a,b,c,d} E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)} a b c d (b) 無向圖 G2 (a) 有向圖 G1 a c b d e 完全無向圖 ： 對于無向圖，若圖中頂點數(shù)為 n ，用 e表示邊的數(shù)目，則 e ?[0， n(n1)/2] 。具有 n(n1)/2條邊的無向圖稱為完全無向圖。 完全無向圖另外的定義是： 對于無向圖 G=(V， E)，若 ?vi， vj ?V ，當 vi≠vj時，有 (vi ,vj)?E，即 圖中任意兩個不同的頂點間都有一條無向邊 ，這樣的無向圖稱為 完全無向圖 。 定義和術(shù)語（ 4） 完全有向圖 ：對于有向圖，若圖中頂點數(shù)為 n ，用e表示弧的數(shù)目，則 e?[0， n(n1)] 。具有 n(n1)條邊的有向圖稱為完全有向圖。 完全有向圖另外的定義是： 對于有向圖 G=(V， E)，若 ?vi， vj?V ，當 vi ≠vj時，有 vi ,vj?E∧ vj , vi ?E ，即 圖中任意兩個不同的頂點間都有一條弧 ，這樣的有向圖稱為 完全有向圖 。 定義和術(shù)語（ 5） 有很少邊或弧的圖（ en㏒ n）的圖稱為 稀疏圖 ，反之稱為 稠密圖 。 權(quán) (Weight)：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個頂點到另一個頂點的距離或耗費。 子圖和生成子圖 ：設(shè)有圖 G=(V， E)和 G’=(V’，E’)，若 V’?V且 E’?E ，則稱圖 G’是 G的 子圖 ；若 V’=V且 E’?E，則稱圖 G’是 G的一個 生成子圖 。 定義和術(shù)語（ 6） 頂點的鄰接 (Adjacent)： 對于無向圖 G=(V， E)，若邊(v,w)?E，則稱頂點 v和 w 互為 鄰接點 ，即 v和 w相鄰接。邊(v,w)依附 (incident)與頂點 v和 w 。 對于有向圖 G=(V ， E)，若有向弧 v,w?E，則稱頂點v “鄰接到 ” 頂點 w，頂點 w “鄰接自 ” 頂點 v ，弧 v,w 與頂點 v和 w “相關(guān)聯(lián) ” 。 頂點的度、入度、出度 ： 對于無向圖 G=(V， E)， ?vi?V，圖 G中 依附 于 vi的邊的數(shù)目稱為頂點 vi的 度 (degree)，記為 TD(vi)。 定義和術(shù)語（ 7） 顯然，在無向圖中，所有頂點度的和是圖中邊的2倍。 即 ∑TD(vi)=2e (i=1,2, … ,n， e為圖的邊數(shù) )。 對有向圖 G=(V， E)，若 ?vi ?V ，圖 G中 以 vi作為起點 的有向邊 (弧 )的數(shù)目稱為頂點 vi的 出度(Outdegree)，記為 OD(vi) ； 以 vi作為終點 的有向邊(弧 )的數(shù)目稱為頂點 vi的 入度 (Indegree)，記為 ID(vi) 。頂點 vi的 出度 與 入度 之和稱為 vi的 度 ，記為 TD(vi) 。即 TD(vi)=OD(vi)+ID(vi) 定義和術(shù)語（ 8） 路徑 (Path)、路徑長度、回路 (Cycle) ：對無向圖 G=(V， E)，若從頂點 vi經(jīng)過若干條邊能到達 vj，稱頂點 vi和 vj是 連通 的，又稱頂點 vi到 vj有 路徑 。 對有向圖 G=(V， E)，從頂點 vi到 vj有 有向路徑 ，指的是從頂點 vi經(jīng)過若干條有向邊 (弧 )能到達 vj。 或 路徑 是圖 G中連接兩頂點間所經(jīng)過的頂點序列。 Path=vi0vi1… vim ， vij?V且 (vij1, vij)?E j=1,2, … ,m 定義和術(shù)語（ 9） 路徑上邊或有向邊 (弧 )的數(shù)目稱為該路徑的 長度 。 在一條路徑中，若 沒有重復(fù)相同 的頂點，該路徑稱為 簡單路徑 ；第一個頂點和最后一個頂點相同的路徑稱為 回路 (環(huán) )；在一個回路中，若除第一個與最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路稱為 簡單回路 (簡單環(huán) )。 定義和術(shù)語（ 10） 連通圖、圖的連通分量 ：對無向圖 G=(V， E)，若?vi ， vj ?V， vi和 vj都是連通的，則稱圖 G是 連通圖 ，否則稱為 非連通圖 。若 G是非連通圖，則 極大的連通子圖 稱為 G的 連通分量 。 對有向圖 G=(V， E)，若 ?vi ， vj ?V，都有 以 vi為起點 ， vj 為終點 以及以 vj為起點， vi為終點的有向路徑，稱圖 G是 強連通圖 ，否則稱為 非強連通圖 。若 G是非強連通圖，則 極大的強連通子圖 稱為 G的 強連通分量 。 “ 極大 ” 的含義：指的是對子圖再增加圖 G中的其它頂點，子圖就不再連通。 定義和術(shù)語（ 11） 生成樹、生成森林 ： 一個連通圖 (無向圖 )的生成樹是一個極小連通子圖，它 含有圖中全部 n個頂點 和只有足以構(gòu)成一棵樹的 n1條邊 ，稱為圖的 生成樹 ，如圖72所示。 關(guān)于無向圖的生成樹的幾個結(jié)論： ◆ 一棵有 n個頂點的生成樹有且僅有 n1條邊； ◆ 如果一個圖有 n個頂點和小于 n1條邊，則是非連通圖； a d b c 圖 72 圖 G2的一棵生成樹 ◆ 如果多于 n1條邊，則一定有環(huán)； ◆ 有 n1條邊的圖不一定是生成樹。 有向圖的 生成森林 是這樣一個子圖，由若干棵 有向樹 組成，含有圖中全部頂點。 有向樹 是只有一個頂點的入度為 0 ，其余頂點的入度均為 1的有向圖，如圖 73所示。 網(wǎng) ： 每個邊 (或弧 )都附加一個權(quán)值的圖，稱為 帶權(quán)圖 。 帶權(quán)的連通圖 (包括弱連通的有向圖 )稱為 網(wǎng)或網(wǎng)絡(luò) 。網(wǎng)絡(luò)是工程上常用的一個概念，用來表示一個工程或某種流程，如圖 74所示。 圖 73 有向圖及其生成森林 a b c d e (a) 有向圖 (b) 生成森林 a c b d e 3 5 4 1 2 6 a b c d e 3 圖 74 帶權(quán)有向圖 圖的抽象數(shù)據(jù)類型定義 圖是一種數(shù)據(jù)結(jié)構(gòu) ， 加上一組基本操作就構(gòu)成了圖的抽象數(shù)據(jù)類型 。 圖的抽象數(shù)據(jù)類型定義如下： ADT Graph{ 數(shù)據(jù)對象 V： 具有相同特性的數(shù)據(jù)元素集合 ， 稱為頂點集 。 數(shù)據(jù)關(guān)系 R： R={VR} VR={v,w|v,w| v,w?V∧ p(v,w) ， v,w表示 從 v到 w的弧， P(v,w)定義了弧 v,w的信息 } 基本操作 P： Create_Graph() ： 圖的創(chuàng)建操作 。 初始條件：無。 操作結(jié)果：生成一個沒有頂點的空圖 G。 GetVex(G, v) ： 求圖中的頂點 v的值。 初始條件：圖 G存在， v是圖中的一個頂點。 操作結(jié)果：生成一個沒有頂點的空圖 G。 … … DFStraver(G,V)：從 v出發(fā)對圖 G深度優(yōu)先遍歷。 初始條件：圖 G存在。 操作結(jié)果：對圖 G深度優(yōu)先遍歷，每個頂點訪問且只訪問一次。 } ADT Graph 圖的存儲結(jié)構(gòu) 圖的存儲結(jié)構(gòu)比較復(fù)雜，其復(fù)雜性主要表現(xiàn)在： ◆ 任意頂點之間可能存在聯(lián)系，無法以數(shù)據(jù)元素在存儲區(qū)中的 物理位置來表示元素之間的關(guān)系 。 ◆ 圖中頂點的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點設(shè)計結(jié)構(gòu)，則會浪費很多存儲單元，反之按每個頂點自己的度設(shè)計不同的結(jié)構(gòu)，又會影響操作。 圖的常用的存儲結(jié)構(gòu)有： 鄰接矩陣 、 鄰接鏈表 、十字鏈表 、 鄰接多重表 和 邊表 。 鄰接矩陣 (數(shù)組 )表示法 基本思想 ： 對于有 n個頂點的圖，用一維數(shù)組vexs[n]存儲頂點信息，用二維數(shù)組 A[n][n]存儲頂點之間關(guān)系的信息。該二維數(shù)組稱為 鄰接矩陣 。在鄰接矩陣中，以頂點在 vexs數(shù)組中的下標代表頂點，鄰接矩陣中的元素 A[i][j]存放的是頂點 i到頂點 j之間關(guān)系的信息。 1 無向圖 無權(quán)圖的鄰接矩陣 無向無權(quán)圖 G=(V， E)有 n(n≧ 1)個頂點，其鄰接矩陣是 n階對稱方陣，如圖 75所示。其元素的定義如下： (a) 無向圖 a b c d 圖 75 無向無權(quán)圖的數(shù)組存儲 (b) 頂點矩陣 vexs a b c d 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 (c) 鄰接矩陣 1 若 (vi , vj)?E，即 vi , vj鄰接 0 若 (vi , vj)?E，即 vi , vj不鄰接 A[i][j]= 1 無向圖 帶權(quán)圖的鄰接矩陣 無向帶權(quán)圖 G=(V， E) 的鄰接矩陣如圖 76所示。其元素的定義如下： (a) 帶權(quán)無向圖 (b) 頂點矩陣 圖 76 無向帶權(quán)圖的數(shù)組存儲 (c) 鄰接矩陣 3 5 4 1 2 6 a b c d e 3 vexs a b c d e ∞ 6 2 ∞ ∞ 6 ∞ 3 4 3 2 3 ∞ 1 ∞