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

表示法第十一章：圖

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

G1={V,R}

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

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

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序?qū)D的基本術(shù)語已知一個圖的頂點集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ù)語頂點的度（degree）是指依附于某頂點vi的邊數(shù)，通常記為TD(vi)。無向圖頂點的度：關(guān)聯(lián)于該頂點的邊的數(shù)目，記為D(v)。有向圖頂點的度：以頂點v為終點的邊的數(shù)目，稱為v的入度，記為ID(v)；以頂點v為起點的邊的數(shù)目，稱為v的出度，記為OD(v)；頂點v的度則定義為該頂點的入度與出度之和，即D(v)=ID(v)+OD(v)。邊數(shù)和結(jié)點度數(shù)的關(guān)系圖的基本術(shù)語路徑、路徑長度、簡單路徑存在一個圖G=(V,E)，從一個頂點p到另一個頂點q的路徑為一個頂點序列，假設(shè)這個序列為(p,v1,v2,…,vn,q)，此序列就是p到q的一條路徑。路徑長度指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除去起點和終點，其余頂點各不相同，則稱此路徑為簡單路徑?；芈罚ōh(huán)）、簡單回路回路：起點和終點相同的路徑稱為回路或環(huán)或圈。起點和終點相同的簡單路徑稱為簡單回路或簡單環(huán)或圈。圖的基本術(shù)語圖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④…簡單路①②③④⑤⑥①②③回路⑤⑥②圖的基本術(shù)語連通圖與強連通圖連通圖（無向圖）：在無向圖G中，若從頂點u到頂點v有一條路徑，則稱頂點u和v在圖G中是連通的。若V(G)中任意2個不同的頂點u和v都是連通的，則稱G為連通圖強連通圖（有向圖）：在有向圖G中，若對于V(G)中任意2個不同的頂點u和v，都存在從u到v以及從v到u的路徑，則稱G是強連通圖。圖的基本術(shù)語

非連通圖

連通圖

強連通圖

非強連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

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

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

信息鏈域，指向單鏈表的第一個結(jié)點圖的存儲結(jié)構(gòu)——鄰接表無向圖的鄰接表ABCDvexdatafirstarcABCD0123adjvexnextarc

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

102

vexdatafirstarcadjvexnextarcABC012

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

1

53

62

83

2(出邊表)(頂點表)1

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