第7章圖（Graph）.ppt

1、第7章 圖（Graph）,圖是一種比樹更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。 1.線性表: 數(shù)據(jù)元素之間僅有線性關(guān)系. (每個(gè)elem只有一個(gè)直接前驅(qū)和一個(gè)直接后繼) 2.樹形結(jié)構(gòu):elem之間有明顯的層次關(guān)系. (每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素相關(guān),但只能和上一層中一個(gè)元素(雙親)相關(guān)) 3.圖形結(jié)構(gòu):結(jié)點(diǎn)之間的關(guān)系可以是任意的. (圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)聯(lián) ) 圖的應(yīng)用十分廣泛。最典型的應(yīng)用領(lǐng)域有電路分析、尋找最短路線、項(xiàng)目規(guī)劃、鑒別化合物、統(tǒng)計(jì)力學(xué)、遺傳學(xué)、控制論、語言學(xué)，乃至社會(huì)科學(xué)。實(shí)際上，在所有的數(shù)據(jù)結(jié)構(gòu)中，圖的應(yīng)用是最廣泛的。,7.1.1 圖的定義,1.圖（Graph）

2、是由集合V和集合E組成， 記為: G=(V,E). 圖中的數(shù)據(jù)元素V,稱為頂點(diǎn)(Vertice，也叫作節(jié)點(diǎn)或點(diǎn)). V:是頂點(diǎn)的有窮非空集合. E:邊的集合. （edge，兩個(gè)頂點(diǎn)之間的關(guān)系,也叫作弧或連線） 在圖7.1中，頂點(diǎn)v2 鄰接于頂點(diǎn)v1 ，而v1 鄰接至頂點(diǎn)v2 。邊關(guān)聯(lián)于頂點(diǎn)v1 而關(guān)聯(lián)至頂點(diǎn)v2 。頂點(diǎn)v2 鄰接至頂點(diǎn)v3 且鄰接于頂點(diǎn)v3 。邊是關(guān)聯(lián)于頂點(diǎn)v2 而關(guān)聯(lián)至頂點(diǎn)v3 。對(duì)于無向圖來說，“至”和“于”的含義是相同的。,1.帶方向的邊叫有向邊(directed edge)，簡(jiǎn)稱為??； 用頂點(diǎn)的有序?qū)Ρ硎?，和是不同?. 2. 而不帶方向的邊叫無向邊(undirecte

3、d edge)，簡(jiǎn)稱為邊。 用頂點(diǎn)的無序?qū)Ρ硎荆?vi ,vj)和(vj ,vi)表示同一條邊。 表示從頂點(diǎn)vi到vj 的一段弧 Vi：稱為邊的始點(diǎn)或者弧尾 Vj：稱為邊的終點(diǎn)或者弧頭,如果使用集合的表示方法，圖7.1中的兩個(gè)圖可以用如下方法表示： 1. 圖G1: G1=(V1，E1)； 其中頂點(diǎn)集 V1=v1，v2，v3，v4； 其中邊集 E1=( v1，v2)，(v1，v3)，(v2，v3)，(v1，v4)， (v3，v4) 2. 圖G2： G2=(V2，E2) 其中頂點(diǎn)集 V2= v1，v2，v3； 其中弧集 E2=， 如果圖中所有的邊都是無向邊，那么該圖叫做無向圖(undirected

4、 graph)，圖7.1中圖G1就是無向圖。 如果所有邊都是有向的，那么該圖叫做有向圖(directed graph)， 圖7.1中G2是一個(gè)有向圖。,對(duì)圖作一些限制： 第一，圖中不能有從頂點(diǎn)自身到自身的邊（即自身環(huán)），就是說不應(yīng)有形如(vx，vx)的邊或的弧。如圖 (a)所示的帶自身環(huán)的圖不討論。 第二，兩個(gè)頂點(diǎn)vt和vu之間相關(guān)聯(lián)的邊不能多于一條。如圖 (b)所示的多重圖也不討論。,(a)帶自身環(huán)的圖,（b）多重圖,7.1.2圖的術(shù)語 （1）完全圖(complete graph)：在有n個(gè)頂點(diǎn)的無向圖中，若有n(n-1)/2條邊，則稱此無向圖為完全無向圖，如圖7.3 （a）所示的圖G1。在

5、有n個(gè)頂點(diǎn)的有向圖中，若有n(n-1)條邊，則稱此圖為完全有向圖，如圖7.3(c)所示的圖G3。 完全圖中的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)都達(dá)到最大值。 （2）權(quán)(weight)：在某些圖的應(yīng)用中，邊（?。┥暇哂信c它相關(guān)的系數(shù)，稱之為權(quán)。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、花費(fèi)的代價(jià)、所需的時(shí)間和次數(shù)等。這種帶權(quán)圖也被稱為網(wǎng)絡(luò)(network)。,（3）鄰接頂點(diǎn)(adjacent vertex)：在無向圖G1中，若(u，v)是E(G)中的一條邊，則稱u和v互為鄰接頂點(diǎn)，并稱邊(u，v)依附于頂點(diǎn)u和v。 （4）頂點(diǎn)的度：頂點(diǎn)的度是指依附于某頂點(diǎn)vi的邊數(shù), 通常記為TD(vi)。 在有向圖中，要區(qū)

6、別頂點(diǎn)的入度和出度的概念。 所謂頂點(diǎn)vi的入度 過是指以vi為終點(diǎn)的弧的數(shù)目，記為ID(vi)； 所謂頂點(diǎn)vi的出度 過是指以vi為始點(diǎn)的弧的數(shù)目，記為OD(vi)。顯然的： TD(vi)=ID(vi)+OD(vi),例如: 1. 在圖7.1（G1）中頂點(diǎn)v1的度TD(v1)=3， 2. 在G2中頂點(diǎn)v2 的入度ID(v2)=2， 出度OD(v2 )=1， TD(v2 )=3。,可以證明，對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，頂點(diǎn)vi的度TD(vi)與頂點(diǎn)的個(gè)數(shù)及邊的數(shù)目滿足關(guān)系： 2e= 例： 2*11+1 2*22+2,（5）路徑與回路：路徑上邊的數(shù)目稱為路徑長(zhǎng)度。 下圖所示的無向圖中，頂點(diǎn)v1到

7、頂點(diǎn)v5的路徑有兩條，分別為(v1，v2，v3，v5)與(v1，v4，v5)，路徑長(zhǎng)度分別為3和2。 如果路徑的起點(diǎn)和終點(diǎn)相同(即vp=vq)，則稱此路徑為回路或環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑， 上圖所示的v1到v5的兩條路徑都為簡(jiǎn)單路徑。除第一頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其它頂點(diǎn)不重復(fù)出現(xiàn)的回路為簡(jiǎn)單回路或者簡(jiǎn)單環(huán)。,（6）路徑長(zhǎng)度（path length）：對(duì)于不帶權(quán)的圖，路徑長(zhǎng)度是指路徑上邊的數(shù)目。對(duì)于帶權(quán)圖，路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。 （7）簡(jiǎn)單路徑與回路(cycle):對(duì)于一路徑(v1, v2, vm)，若路徑上各頂點(diǎn)均不相同，則稱這條路徑為簡(jiǎn)單路徑。若路徑上第一個(gè)頂點(diǎn)v1和最后一個(gè)頂點(diǎn)vm相同，則稱這樣的路徑為回路或環(huán)。 （8）連通圖與連通分量(connected graph and connected component)：若從頂點(diǎn)vi到頂點(diǎn)vj (ij)有路徑，則vi和vj是連通的。,如果無向圖中任意兩個(gè)頂點(diǎn)vi和vj都是