數(shù)據(jù)結(jié)構(gòu)-基于Python語(yǔ)言（微課版） 課件T20-圖(表示法)

表示法第十一章：圖

主講：周翔回顧一棵二叉樹(shù)前序遍歷和中序遍歷序列如下所示：前序：DACEBHFGI；中序：DCBEHAGIF;試畫(huà)出二叉樹(shù)結(jié)構(gòu)，并簡(jiǎn)述求算過(guò)程。請(qǐng)思考對(duì)任一棵二叉樹(shù)都可以用哪種方式來(lái)存儲(chǔ)，并述其優(yōu)劣預(yù)習(xí)檢查什么是圖圖有哪些遍歷方法本章目標(biāo)3圖的存儲(chǔ)方式最短路徑拓?fù)渑判蜿P(guān)鍵路徑重點(diǎn)了解掌握2圖的遍歷最小生成樹(shù)圖的定義與基本術(shù)語(yǔ)1什么是圖圖結(jié)構(gòu)研究數(shù)據(jù)元素之間多對(duì)多的關(guān)系。圖中的結(jié)點(diǎn)沒(méi)有明確的層級(jí)，也沒(méi)有先后次序。圖中結(jié)點(diǎn)間的關(guān)系可以是任意的：任意一個(gè)結(jié)點(diǎn)都可以有零個(gè)或多個(gè)前驅(qū)，也可以有零個(gè)或多個(gè)后繼，亦都可以作為起始結(jié)點(diǎn)或終結(jié)結(jié)點(diǎn)。什么是圖六度空間理論：你和任何一個(gè)陌生人之間所間隔的人不會(huì)超過(guò)6個(gè)，也就是說(shuō)，最多通過(guò)6個(gè)中間人你就能夠認(rèn)識(shí)任何一個(gè)陌生人。什么是圖圖（Graph）是一種數(shù)據(jù)結(jié)構(gòu)，將其簡(jiǎn)化為頂點(diǎn)（Vertrx）和邊（Edge）的組合，采用形式化的定義，定義一個(gè)圖。Graph=(V,R)V是頂點(diǎn)的非空有限集R是邊的有限集，可為空集圖的基本術(shù)語(yǔ)頂點(diǎn)與鄰接點(diǎn)：若有P<x,y>∈V表示在頂點(diǎn)x與頂點(diǎn)y之間的一條連線，則稱x、y為該邊的兩個(gè)頂點(diǎn)，同時(shí)稱x與y互為鄰接點(diǎn)，即頂點(diǎn)x是頂點(diǎn)y的鄰接點(diǎn)，頂點(diǎn)y也是頂點(diǎn)x的鄰接點(diǎn)。稱邊P<x,y>依附于頂點(diǎn)x和頂點(diǎn)y，或者說(shuō)邊P<x,y>與頂點(diǎn)x、頂點(diǎn)y相關(guān)聯(lián)。若(u,v)是一條無(wú)向邊，則稱u和v互為鄰接點(diǎn)，稱邊(u,v)與兩個(gè)頂點(diǎn)互相關(guān)聯(lián)若<u,v>是一條有向邊，則稱頂點(diǎn)u鄰接到頂點(diǎn)v；頂點(diǎn)v鄰接自頂點(diǎn)u，稱弧<u,v>與頂點(diǎn)u和v互相關(guān)聯(lián)圖的基本術(shù)語(yǔ)有向圖與無(wú)向圖：若這條線從x指向y，則稱x為起始點(diǎn)（弧尾），稱y為終結(jié)點(diǎn)（弧頭），稱這條邊為?。╝rc），此時(shí)的圖為有向圖。若當(dāng)P<x,y>∈V時(shí)必有P<y,x>∈V，則E是對(duì)稱的，結(jié)點(diǎn)x、結(jié)點(diǎn)y不分起始和終結(jié)，此時(shí)以無(wú)序?qū)?x,y)來(lái)表示x與y之間的一條邊，這樣的圖稱為無(wú)向圖。有向圖無(wú)向圖3214532145圖的基本術(shù)語(yǔ)弧尾邊?。?,2＞弧頭弧圖的基本術(shù)語(yǔ)有向圖：

G1={V,R}

V(G1)={1,2,3,4}

R(G1)={<1,2>,<1,3>,<2,4>,<3,2>,<4,3>}無(wú)向圖：

G2={V,R}

V(G2)={1,2,3,4,5}

R(G2)={(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}有序?qū)o(wú)序?qū)D的基本術(shù)語(yǔ)已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1，2，3，4，5，6，7}；E={(1，2)3，(1，3)5，(1，4)8，(2，5)10，(2，3)6，(3，4)15，(3，5)12，(3，6)9，(4，6)4，(4，7)20，(5，6)18，(6，7)25}。圖的基本術(shù)語(yǔ)頂點(diǎn)的度（degree）是指依附于某頂點(diǎn)vi的邊數(shù)，通常記為T(mén)D(vi)。無(wú)向圖頂點(diǎn)的度：關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記為D(v)。有向圖頂點(diǎn)的度：以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，稱為v的入度，記為ID(v)；以頂點(diǎn)v為起點(diǎn)的邊的數(shù)目，稱為v的出度，記為OD(v)；頂點(diǎn)v的度則定義為該頂點(diǎn)的入度與出度之和，即D(v)=ID(v)+OD(v)。邊數(shù)和結(jié)點(diǎn)度數(shù)的關(guān)系圖的基本術(shù)語(yǔ)路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑存在一個(gè)圖G=(V,E)，從一個(gè)頂點(diǎn)p到另一個(gè)頂點(diǎn)q的路徑為一個(gè)頂點(diǎn)序列，假設(shè)這個(gè)序列為(p,v1,v2,…,vn,q)，此序列就是p到q的一條路徑。路徑長(zhǎng)度指一條路徑上經(jīng)過(guò)的邊的數(shù)目。若一條路徑上除去起點(diǎn)和終點(diǎn)，其余頂點(diǎn)各不相同，則稱此路徑為簡(jiǎn)單路徑。回路（環(huán)）、簡(jiǎn)單回路回路：起點(diǎn)和終點(diǎn)相同的路徑稱為回路或環(huán)或圈。起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)或圈。圖的基本術(shù)語(yǔ)圖G1G2路①1,2,4,3②1,2③1,3④2,4,3⑤3,2,4,3⑥2,4,3,2⑦……①1,2,3,4②1,2,3,4,1③3,2,5④…簡(jiǎn)單路①②③④⑤⑥①②③回路⑤⑥②圖的基本術(shù)語(yǔ)連通圖與強(qiáng)連通圖連通圖（無(wú)向圖）：在無(wú)向圖G中，若從頂點(diǎn)u到頂點(diǎn)v有一條路徑，則稱頂點(diǎn)u和v在圖G中是連通的。若V(G)中任意2個(gè)不同的頂點(diǎn)u和v都是連通的，則稱G為連通圖強(qiáng)連通圖（有向圖）：在有向圖G中，若對(duì)于V(G)中任意2個(gè)不同的頂點(diǎn)u和v，都存在從u到v以及從v到u的路徑，則稱G是強(qiáng)連通圖。圖的基本術(shù)語(yǔ)

非連通圖

連通圖

強(qiáng)連通圖

非強(qiáng)連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1V5V4圖的基本術(shù)語(yǔ)稀疏圖：有很少條邊的圖（e<nlogn）稠密圖：相反于稀疏圖的圖。賦權(quán)圖和網(wǎng)：權(quán)是具有某種實(shí)際意義的數(shù)，比如，2個(gè)頂點(diǎn)之間的距離，耗費(fèi)等若無(wú)向圖的每條邊都帶一個(gè)權(quán)，則稱相應(yīng)的圖為賦權(quán)無(wú)向圖。若有向圖的每條邊都帶一個(gè)權(quán)，則稱相應(yīng)的圖為賦權(quán)有向圖。圖的基本術(shù)語(yǔ)賦權(quán)圖和網(wǎng)與邊或者弧有關(guān)的數(shù)據(jù)信息稱為權(quán)（weight）邊上帶有權(quán)值的圖稱為網(wǎng)圖或者網(wǎng)絡(luò)（network）圖的基本術(shù)語(yǔ)完全圖具有最多的邊數(shù)，任一對(duì)頂點(diǎn)都有邊相連完全圖：設(shè)|V|=n,|E|=e。對(duì)無(wú)向圖G，若e=n(n-1)/2，則稱G為完全的無(wú)向圖對(duì)有向圖G，若e=n(n-1)，則稱G為完全的有向圖有向完全圖無(wú)向完全圖圖的基本術(shù)語(yǔ)設(shè)G=(V,E)是一個(gè)圖假設(shè)有兩個(gè)圖分別為G=(V,E)和G′=(V′,E′)，若V′是V的子集，E′是E的子集，則稱圖G′是圖G的子集。圖的基本術(shù)語(yǔ)圖的抽象數(shù)據(jù)類型ADTADTGraph{ 數(shù)據(jù)對(duì)象V： 一個(gè)集合，該集合中的所有元素具有相同的特性。 數(shù)據(jù)關(guān)系R：R＝{VR} VR={<x,y>|P(x,y)^(x,y∈V)} 基本操作： CreateGraph(G)：創(chuàng)建圖G. DestroyGraph(G)：銷毀圖G. LocateVertex(G,v)：返回頂點(diǎn)v在圖G中的位置，若沒(méi)有頂點(diǎn)v， 則返回值為"空"(－1). GetVertex(G,i)：返回圖G中第i個(gè)頂點(diǎn)的值，若i大于圖G中頂點(diǎn) 數(shù)，則返回值為"空"(－1).圖的抽象數(shù)據(jù)類型ADT 基本操作： FirstAdjVertex(G,v)：圖G中頂點(diǎn)v的第一個(gè)鄰接點(diǎn)。若v無(wú)鄰接 點(diǎn)或圖G中無(wú)頂點(diǎn)v， 則返回值為"空"(－1)。 NextAdjVertex(G,v,w)：圖G中頂點(diǎn)v的下一個(gè)鄰接點(diǎn)（緊跟在 w后面）。若w是v的最后一個(gè)鄰接點(diǎn)， 則函數(shù)返回值為"空"。 InsertVertex(G,u)：在圖G中增加一個(gè)頂點(diǎn)u。 DeleteVertex(G,v)：刪除圖G中頂點(diǎn)v及與頂點(diǎn)v相關(guān)聯(lián)的 ?。ㄟ叄?。 InsertArc(G,v,w)：在圖G中增加一條從頂點(diǎn)v到頂點(diǎn)w的弧。 DeleteArc(G,v,w)：刪除圖G中從頂點(diǎn)v到頂點(diǎn)w的?。ㄟ叄?。 TraverseGraph(G)：對(duì)圖G的每個(gè)頂點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。}圖的抽象數(shù)據(jù)類型ADT無(wú)向圖與有向圖的差別僅在于無(wú)向圖中的邊是頂點(diǎn)的無(wú)序?qū)Γ邢驁D中的邊是頂點(diǎn)的有序?qū)λ钥梢詫⒁粋€(gè)無(wú)向圖當(dāng)作一個(gè)有向圖來(lái)處理。圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣（AdjacencyMatrix）鄰接表（AdjacencyList）十字鏈表鄰接多重表圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣設(shè)圖A=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖,圖的鄰接矩陣是一個(gè)二維數(shù)組A

[n][n]，定義：鄰接矩陣存儲(chǔ)法中，使用一個(gè)線性表來(lái)存儲(chǔ)圖中頂點(diǎn)信息，使用一個(gè)鄰接矩陣來(lái)存儲(chǔ)頂點(diǎn)的關(guān)系，也就是邊。通常使用一個(gè)一維數(shù)組和一個(gè)二維數(shù)組分別存儲(chǔ)線性表和鄰接矩陣故，圖的鄰接矩陣表示法也稱為：數(shù)組表示法圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣0123無(wú)向圖的鄰接矩陣是對(duì)稱的圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣012有向圖的鄰接矩陣可能是不對(duì)稱的圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣在無(wú)向圖中：統(tǒng)計(jì)第i行(列)1的個(gè)數(shù)可得頂點(diǎn)i的度。在有向圖中：統(tǒng)計(jì)第i行1的個(gè)數(shù)可得頂點(diǎn)i的出度，統(tǒng)計(jì)第i列1的個(gè)數(shù)可得頂點(diǎn)i的入度。圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣1：無(wú)向圖的鄰接矩陣是對(duì)稱矩陣，所以可采用壓縮存儲(chǔ)法（下三角），其存儲(chǔ)空間只需＿＿＿。2：有向圖的鄰接矩陣一定不是對(duì)稱矩陣，對(duì)嗎？3：有向圖的鄰接矩陣需要＿＿＿＿＿＿個(gè)存儲(chǔ)空間。n(n-1)/2不對(duì)！有可能是對(duì)稱矩陣n2圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣網(wǎng)的鄰接矩陣63129542031圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣用鄰接矩陣實(shí)現(xiàn)有向圖只須將實(shí)現(xiàn)有向網(wǎng)中邊的權(quán)值表示方式按如下修改即可每條邊的邊權(quán)規(guī)定為1，邊權(quán)為0時(shí)表示無(wú)邊用鄰接矩陣實(shí)現(xiàn)無(wú)向圖邊權(quán)規(guī)定為1，邊權(quán)為0時(shí)表示無(wú)邊一條邊可看作兩條相反方向的弧，如：插入一條邊(i,j)的操作：圖的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣鄰接矩陣表示法優(yōu)點(diǎn)：易于操作，容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊、找頂點(diǎn)的鄰接點(diǎn)等等。缺點(diǎn)：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊;空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。解決方法：鄰接表表示法圖的存儲(chǔ)結(jié)構(gòu)——鄰接表圖的鄰接表存儲(chǔ)是一種鏈?zhǔn)酱鎯?chǔ)與順序存儲(chǔ)相結(jié)合的存儲(chǔ)結(jié)構(gòu)。鄰接表存儲(chǔ)法既能保留鄰接矩陣存儲(chǔ)法的優(yōu)點(diǎn)，又能很好地解決矩陣存儲(chǔ)的缺點(diǎn)。這種結(jié)構(gòu)為圖中的每一個(gè)頂點(diǎn)創(chuàng)建一個(gè)鏈表，鏈表中的結(jié)點(diǎn)為這個(gè)頂點(diǎn)的鄰接點(diǎn)，這個(gè)結(jié)點(diǎn)稱作表結(jié)點(diǎn)或邊結(jié)點(diǎn)。同時(shí)為每一個(gè)頂點(diǎn)的鏈表設(shè)置一個(gè)頭結(jié)點(diǎn)，為了實(shí)現(xiàn)隨機(jī)訪問(wèn)，通常將這些頭結(jié)點(diǎn)以順序結(jié)構(gòu)的形式存儲(chǔ)。鄰接表存儲(chǔ)在矩陣存儲(chǔ)的基礎(chǔ)上實(shí)現(xiàn)了存儲(chǔ)空間的有效利用。圖的存儲(chǔ)結(jié)構(gòu)——鄰接表對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊的信息鏈接起來(lái)，每個(gè)結(jié)點(diǎn)設(shè)為3個(gè)域；每個(gè)單鏈表有一個(gè)頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。adjvexnextarcinfodatafirstarc表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置鏈域，指向vi下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi

信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)圖的存儲(chǔ)結(jié)構(gòu)——鄰接表無(wú)向圖的鄰接表ABCDvexdatafirstarcABCD0123adjvexnextarc

130210表頭結(jié)點(diǎn)表邊表注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的圖的存儲(chǔ)結(jié)構(gòu)——鄰接表有向圖的鄰接表鄰接表(出邊表)ABCABC012

102

vexdatafirstarcadjvexnextarcABC012

011vexdatafirstarcadjvexnextarc逆鄰接表(入邊表)圖的存儲(chǔ)結(jié)構(gòu)——鄰接表有向網(wǎng)(帶權(quán)圖)的鄰接表BACD69528ABCD0123

1

53

62

83

2(出邊表)(頂點(diǎn)表)1

9vexdatafirstarcadjvexinfonextarc圖的存儲(chǔ)結(jié)構(gòu)——鄰接表優(yōu)點(diǎn)：使用鄰接表存儲(chǔ)比鄰接矩陣節(jié)省空間，不必存儲(chǔ)不存在的邊（?。┼徑颖泶鎯?chǔ)法表示圖時(shí)，鄰接表不唯一；假設(shè)頂點(diǎn)為vi。對(duì)于無(wú)向圖，頂點(diǎn)單鏈表中表結(jié)點(diǎn)的數(shù)目即為該頂點(diǎn)的度。對(duì)于有向圖，單鏈表中表結(jié)點(diǎn)的數(shù)目是vi的出度；鄰接表中adjvex域值為i的表結(jié)點(diǎn)的數(shù)目是該頂點(diǎn)的入度。缺點(diǎn)：結(jié)構(gòu)較復(fù)雜如建立逆鄰接表，方便計(jì)算入度，但實(shí)際上，一條邊需分別在鄰接表與逆鄰接表中存儲(chǔ)解決方法：十字鏈表（優(yōu)點(diǎn)：一條弧只被存放一次）圖的存儲(chǔ)結(jié)構(gòu)——十字鏈表在逆鄰接表的基礎(chǔ)上，在頭結(jié)點(diǎn)中新增一個(gè)域，這個(gè)域中的指針指向以該頂點(diǎn)為弧尾的第一個(gè)鄰接點(diǎn)；同時(shí)在表結(jié)點(diǎn)中增加兩個(gè)域，一個(gè)域用來(lái)存放鄰接邊弧頭的編號(hào)，一個(gè)域用來(lái)存放鄰接邊的弧頭指針。用這些結(jié)點(diǎn)鏈接起來(lái)的圖元素有些類似于稀疏矩陣的十字鏈表存儲(chǔ)，這種存儲(chǔ)方式稱為圖的十字鏈表存儲(chǔ)。邊結(jié)點(diǎn)表中的結(jié)點(diǎn)的表示：info：邊結(jié)點(diǎn)的數(shù)據(jù)域，保存邊的權(quán)值等。tailVex：本條邊的出發(fā)結(jié)點(diǎn)的地址。headVex：本條邊的終止結(jié)點(diǎn)的地址。hLink：終止結(jié)點(diǎn)相同的邊中的下一條邊的地址。tLink：出發(fā)結(jié)點(diǎn)相同的邊中的下一條邊的地址。圖的存儲(chǔ)結(jié)構(gòu)——十字鏈表圖的存儲(chǔ)結(jié)構(gòu)——十字鏈表弧結(jié)點(diǎn)：0312info35189013tailvex=0headvex=1hlink=?。?,3＞地址31tlink=?。?,2＞地址02info存儲(chǔ)弧的相關(guān)信息：如權(quán)值3結(jié)點(diǎn)表中的結(jié)點(diǎn)的表示：data：結(jié)點(diǎn)的數(shù)據(jù)域，保存結(jié)點(diǎn)的數(shù)據(jù)值。firstIn：結(jié)點(diǎn)的指針域，給出自該結(jié)點(diǎn)出發(fā)的的第一條邊的邊結(jié)點(diǎn)的地址。firstOut：結(jié)點(diǎn)的指針場(chǎng)，給出進(jìn)入該結(jié)點(diǎn)的第一條邊的邊結(jié)點(diǎn)的地址。圖的存儲(chǔ)結(jié)構(gòu)——十字鏈表圖的存儲(chǔ)結(jié)構(gòu)——十字鏈表頂點(diǎn)結(jié)