《數(shù)據(jù)結(jié)構(gòu)》課件-第7章 圖

數(shù)據(jù)構(gòu)C語言描述結(jié)第7章

圖第7章圖知識目標理解圖的概念和有關(guān)術(shù)語；掌握鄰接矩陣表示法和鄰接表表示法；理解連通圖遍歷的基本思想；掌握圖的深度和廣度優(yōu)先搜索遍歷算法；理解生成樹和最小生成樹的有關(guān)概念和算法；理解拓撲排序的概念、步驟和背景；理解關(guān)鍵路徑和最短路徑的概念和算法。技能目標：能應(yīng)用圖的理論設(shè)計算法，解決實際問題。7.4最小生成樹7.1圖的邏輯結(jié)構(gòu)7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.5最短路徑7.6案例實現(xiàn)——有向無環(huán)圖及其應(yīng)用歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他一生共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。歐拉對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。圖論——歐拉能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？ABCD哥尼斯堡七橋問題

CADB七橋問題的圖模型哥尼斯堡七橋問題

歐拉回路的判定規(guī)則：1.如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；2.如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；3.如果沒有一個地方是通奇數(shù)橋的，則無論從哪里出發(fā)，都能找到歐拉回路。圖的定義圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G=(V，E)其中：G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。7.1圖的邏輯結(jié)構(gòu)如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。若頂點vi

和vj

之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

如果圖的任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖。V0V1V2V3V4V0V1V2V37.1圖的邏輯結(jié)構(gòu)7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語簡單圖：在圖中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)。非簡單圖非簡單圖簡單圖數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖V0V1V2V3V4V0V1V2V3V4V0V1V2V3V47.1圖的邏輯結(jié)構(gòu)鄰接、依附無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi,vj)依附于頂點vi和頂點vj。V0的鄰接點：V1、V3V1的鄰接點：V0、V2、V4V0V1V2V3V4圖的基本術(shù)語7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語鄰接、依附有向圖中，對于任意兩個頂點vi和頂點vj，若存在弧<vi，vj>，則稱頂點vi鄰接到頂點vj，頂點vj鄰接自頂點vi，同時稱弧<vi，vj>依附于頂點vi和頂點vj。其中vi為弧尾，vj為弧頭。V0V1V2V3V0的鄰接點：V1、V2V2的鄰接點：V3<V0，V1>中，V0為弧尾，V1為弧頭在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比V0V1V2V3V4圖結(jié)構(gòu)在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點之間的關(guān)系為鄰接。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V0V1V2V3V4圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。V0V1V2V0V1V2V3含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條弧？

含有n個頂點的無向完全圖有n×(n-1)/2條邊含有n個頂點的有向完全圖有n×(n-1)條弧7.1圖的邏輯結(jié)構(gòu)V0V1V2V0V1V2V37.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)。頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)。7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語在具有n個頂點、e條邊的無向圖G中，各頂點的度之和與邊數(shù)之和的關(guān)系？?==nievTD12)(iV0V1V2V3V47.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語V0V1V2V3在具有n個頂點、e條邊的有向圖G中，各頂點的入度之和與各頂點的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii====11)()(nn??7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語權(quán)（Weight）：指對邊賦予的有意義的數(shù)值量。網(wǎng)（Network）：邊上帶權(quán)的圖，也稱網(wǎng)圖。V0V1V2V32785哈夫曼樹中的權(quán)與網(wǎng)圖的權(quán)有何區(qū)別？74237.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語路徑（Path）：在無向圖G=(V,E)中，從頂點vp到頂點vq之間的路徑是一個頂點序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向圖，則路徑也是有方向的，頂點序列滿足<vij-1,vij>∈E。一般情況下，圖中的路徑不唯一V0到V3的路徑：

V0V3

V0V1V2V3V0V1V4V2V3V0V1V2V3V47.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語路徑長度：非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V0V3：長度為1V0V1V2V3：長度為3V0V1V4V2V3：長度為4V0V1V2V3V47.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語路徑長度：非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V0V3：長度為8V0V1V2V3：長度為7V0V1V4V2V3：長度為15256328V0V1V2V3V47.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語回路或環(huán)（Cycle）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路。V0V1V2V3V4V0V1V2V37.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語子圖：若圖G=（V，E），G'=（V'，E'），如果V'

V

且E'

E，則稱圖G’是G的子圖。V0V1V2V3V4V0V1V2V3V4V0V2V37.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語連通圖：在無向圖中，如果從一個頂點vi到另一個頂點vj（i≠j）有路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。如何求得一個非連通圖的連通分量?1.含有極大頂點數(shù)2.依附于這些頂點的所有邊7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語連通分量1V0V1V3V4V2V6V5V0V1V4V2V3V6V5連通分量2連通分量是對無向圖的一種劃分7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語強連通圖：在有向圖中，對圖中任意一對頂點vi和vj（i≠j），若從頂點vi到頂點vj和從頂點vj到頂點vi均有路徑，則稱該有向圖是強連通圖。強連通分量：非強連通圖的極大強連通子圖。如何求得一個非強連通圖的強連通分量?7.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語V0V1V2V3強連通分量1

強連通分量2V0V2V3V17.1圖的邏輯結(jié)構(gòu)圖的基本術(shù)語生成樹：n個頂點的連通圖G的生成樹是包含G中全部頂點的一個

極小連通子圖。生成森林：在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個非連通圖的生成森林。如何理解極小連通子圖?多——構(gòu)成回路少——不連通含有n-1條邊7.1圖的邏輯結(jié)構(gòu)V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成樹生成森林你和任何一個陌生人之間所間隔的人不會超過6個，也就是說，最多通過6個中間人你就能夠認識任何一個陌生人。7.1圖的邏輯結(jié)構(gòu)案例：六度空間理論7.1圖的邏輯結(jié)構(gòu)圖的抽象數(shù)據(jù)類型定義圖是一種與具體應(yīng)用密切相關(guān)的數(shù)據(jù)結(jié)構(gòu)，它的基本操作往往隨應(yīng)用不同而有很大差別。下面給出一個圖的抽象數(shù)據(jù)類型定義的例子，簡單起見，基本操作僅包含圖的遍歷，針對具體應(yīng)用，需要重新定義其基本操作。7.1圖的邏輯結(jié)構(gòu)圖的抽象數(shù)據(jù)類型定義ADTGraphData

頂點的有窮非空集合和邊的集合OperationCreateGraph(G)：輸入圖G的頂點和邊，建立圖G的存儲DestroyGraph(G)：釋放圖所占用的存儲空間LocateVertex(G,v)：在圖G中找到頂點v，返回該頂點在圖中的位置GetVertex(G,i)：在圖G中找到頂點v，返回該頂點的相關(guān)信息FirstAdjVertex(G,v)：在圖G中返回v的第一個鄰接點7.1圖的邏輯結(jié)構(gòu)NextAdjVertex(G,v,w)：在圖G中返回v的下一個鄰接點，若w為v的最后一個鄰接點，則返回空InsertVertex(G,v)：在圖G中增添一個新頂點vDeleteVertex(G,v)：在圖G中刪除頂點v以及所有和頂點v相關(guān)聯(lián)的弧或邊InsertArc(G,v,w)：在圖G中增添一條從頂點v到頂點w的邊或弧DeleteArc(G,v,w)：在圖G中刪除一條從頂點v到頂點w的邊或弧DFSTraverse(G,v)：從頂點v出發(fā)深度優(yōu)先遍歷圖GBFSTraverse(G,v)從頂點v出發(fā)廣度優(yōu)先遍歷圖GendADT7.2圖的存儲結(jié)構(gòu)圖的特點?頂點之間的關(guān)系是m:n，即任何兩個頂點之間都可能存在關(guān)系（邊），無法通過存儲位置表示這種任意的邏輯關(guān)系。如何存儲圖?鏈式存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：鄰接矩陣鄰接表十字鏈表鄰接多重表01頂點信息邊或弧的信息，即頂點之間的關(guān)系027.2圖的存儲結(jié)構(gòu)基本思想：建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表示各個頂點之間關(guān)系）。假設(shè)圖G＝(V，E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：arc[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它鄰接矩陣（數(shù)組表示法）7.2圖的存儲結(jié)構(gòu)無向圖的鄰接矩陣無向圖的鄰接矩陣的特點？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主對角線為0且一定是對稱矩陣。01

2

3頂點表鄰接矩陣7.2圖的存儲結(jié)構(gòu)無向圖的鄰接矩陣如何求頂點Vi的度？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3鄰接矩陣的Vi行（或Vi列）非零元素的個數(shù)。01

2

37.2圖的存儲結(jié)構(gòu)無向圖的鄰接矩陣如何判斷頂點Vi

和Vj

之間是否存在邊？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。01

2

37.2圖的存儲結(jié)構(gòu)無向圖的鄰接矩陣如何求頂點Vi

的所有鄰接點？(第一個鄰接點和下一個鄰接點)？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3將二維數(shù)組中對應(yīng)的Vi行元素掃描一遍，若arc[i][j]為1，則頂點Vj

為頂點Vi的鄰接點。01

2

37.2圖的存儲結(jié)構(gòu)無向圖的鄰接矩陣完全圖的鄰接矩陣的特點？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主對角線為0，其余都為1。01

2

37.2圖的存儲結(jié)構(gòu)有向圖的鄰接矩陣有向圖的鄰接矩陣一定不對稱嗎？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3不一定，例如有向完全圖。01

2

37.2圖的存儲結(jié)構(gòu)有向圖的鄰接矩陣如何求頂點Vi

的出度？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3鄰接矩陣中頂點Vi

所在的行元素之和。01

2

37.2圖的存儲結(jié)構(gòu)有向圖的鄰接矩陣如何求頂點Vi

的入度？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3鄰接矩陣中頂點Vi

所在的列元素之和。01

2

37.2圖的存儲結(jié)構(gòu)有向圖的鄰接矩陣如何判斷從頂點Vi到頂點Vj是否存在邊？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3測試鄰接矩陣中相應(yīng)位置的元素arc[i][j]是否為1。01

2

37.2圖的存儲結(jié)構(gòu)網(wǎng)圖的鄰接矩陣025∞∞0∞∞∞∞087∞∞0arc=V0V3V1V22785網(wǎng)圖的鄰接矩陣可定義為：arc[i][j]＝wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他缺點：存儲空間浪費大對于無向圖而言，可采用壓縮存儲法（下三角），其存儲空間只需n(n+1)/2。但對于有向圖而言，需要n2個存儲空間。優(yōu)點：便于運算，采用鄰接矩陣表示法，便于求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。鄰接矩陣所占的空間與邊數(shù)無關(guān)，適合于存儲稠密圖7.2圖的存儲結(jié)構(gòu)鄰接矩陣的特點

#defineMAX_VEX_NUM20/*定義圖中最大頂點個數(shù)*/typedefcharVertexType;/*定義頂點類型*/typedefstructGraph{VertexTypevexs[MAX_VEX_NUM];/*頂點集合*/int

AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];

/*鄰接矩陣*/intvexnum,arcnum;/*圖的當(dāng)前頂點數(shù)和弧(邊)數(shù)*/}MGraph;

MGraphG；G->vexnum=i;G->arcnum=j;G.vexs[i]==u；G->AdjMatrix[i][j]=17.2圖的存儲結(jié)構(gòu)鄰接矩陣表示法的C語言類型描述7.2圖的存儲結(jié)構(gòu)鄰接表鄰接表存儲的基本思想：對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維數(shù)組構(gòu)成了頂點表。圖的鄰接矩陣存儲結(jié)構(gòu)的空間復(fù)雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？假設(shè)圖G有n個頂點e條邊，則存儲該圖需要O(n2)。7.2圖的存儲結(jié)構(gòu)鄰接表鄰接表有兩種結(jié)點結(jié)構(gòu)：頂點表結(jié)點和邊表結(jié)點。vertexfirstedgeadjvexnext

頂點表邊表vertex：數(shù)據(jù)域，存放頂點信息。firstedge：指針域，指向邊表中第一個結(jié)點。adjvex：鄰接點域，邊的終點在頂點表中的下標。next：指針域，指向邊表中的下一個結(jié)點。7.2圖的存儲結(jié)構(gòu)鄰接表103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2圖的存儲結(jié)構(gòu)定義鄰接表的結(jié)點#defineMaxVertexNum100typedefstructnode{/*邊表結(jié)點*/

intadjvex;/*鄰接點域*/structnode*next;/*指向下一個鄰接點的指針域*/}EdgeNode;typedefstructvnode{/*頂點表結(jié)點*/VertexTypevertex;/*頂點域*/EdgeNode*firstedge;/*指向邊表中第一個結(jié)點*/}VertexNode;

adjvex

next

邊表vertexfirstedge頂點表7.2圖的存儲結(jié)構(gòu)定義鄰接表typedefVertexNodeAdjList[MaxVertexNum];typedefstruct{AdjListadjlist;/*鄰接表*/intn,e;/*頂點數(shù)和邊數(shù)*/}ALGraph;/*基于鄰接表的圖7.2圖的存儲結(jié)構(gòu)無向圖的鄰接表邊表中的結(jié)點表示什么？每個結(jié)點對應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+e)。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2圖的存儲結(jié)構(gòu)無向圖的鄰接表如何求頂點Vi的度？頂點Vi的邊表中結(jié)點的個數(shù)。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2圖的存儲結(jié)構(gòu)無向圖的鄰接表如何判斷頂點Vi和頂點Vj之間是否存在邊?測試頂點Vi的邊表中是否存在終點為Vj的結(jié)點。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2圖的存儲結(jié)構(gòu)有向圖的鄰接表如何求頂點Vi的出度？頂點Vi

的出邊表中結(jié)點的個數(shù)。12∧3∧0∧V0V1

∧V2V30123vertexfirstedgeV0V3V1V27.2圖的存儲結(jié)構(gòu)有向圖的鄰接表如何求頂點Vi的入度？各頂點的出邊表中以頂點Vi

為終點的結(jié)點個數(shù)。12∧3∧0∧V0V1

∧V2V30123vertexfirstedgeV0V3V1V27.2圖的存儲結(jié)構(gòu)有向圖的鄰接表如何求頂點Vi的所有鄰接點？遍歷頂點Vi

的邊表，該邊表中的所有終點都是頂點Vi的鄰接點。12∧3∧0∧V0V1

∧V2V30123vertexfirstedgeV0V3V1V27.2圖的存儲結(jié)構(gòu)網(wǎng)圖的鄰接表V0V1V2V3278521V0V1

V2V30123vertexfirstedge∧52∧83∧70∧7.2圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)的比較——鄰接矩陣和鄰接表O(n2)O(n+e)O(n2)O(n+e)空間性能時間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一圖的遍歷是在從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次。抽象操作，可以是對結(jié)點進行的各種處理，這里簡化為輸出結(jié)點的數(shù)據(jù)。7.3圖的遍歷圖的遍歷算法是求解圖的連通性問題、拓撲排序和關(guān)鍵路徑等算法的基礎(chǔ)。圖的遍歷操作圖的遍歷操作要解決的關(guān)鍵問題①在圖中，如何選取遍歷的起始頂點？在線性表中，數(shù)據(jù)元素在表中的編號就是元素在序列中的位置，因而其編號是唯一的；在樹中，將結(jié)點按層序編號，由于樹具有層次性，因而其層序編號也是唯一的；在圖中，任何兩個頂點之間都可能存在邊，頂點是沒有確定的先后次序的，所以，頂點的編號不唯一。

為了定義操作的方便，將圖中的頂點按任意順序排列起來，比如，按頂點的存儲順序。解決方案：從編號小的頂點開始。7.3圖的遍歷②從某個起點始可能到達不了所有其它頂點，怎么辦？解決方案：多次調(diào)用從某頂點出發(fā)遍歷圖的算法。下面僅討論從某頂點出發(fā)遍歷圖的算法。7.3圖的遍歷圖的遍歷操作要解決的關(guān)鍵問題③因圖中可能存在回路，某些頂點可能會被重復(fù)訪問，那么如何避免遍歷不會因回路而陷入死循環(huán)。④在圖中，一個頂點可以和其它多個頂點相連，當(dāng)這樣的頂點訪問過后，如何選取下一個要訪問的頂點？解決方案：附設(shè)訪問標志數(shù)組visited[n]。解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。7.3圖的遍歷圖的遍歷操作要解決的關(guān)鍵問題1.深度優(yōu)先遍歷基本思想：訪問頂點v；從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。7.3圖的遍歷深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8V1遍歷序列：V1V2V2V4V4V5V57.3圖的遍歷深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8V1遍歷序列：V1V2V2V4V4V5V8V87.3圖的遍歷深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8V1遍歷序列：V1V2V2V4V4V5V87.3圖的遍歷深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8V1遍歷序列：V1V7V2V4V5V8V3V3V6V6V77.3圖的遍歷1.深度優(yōu)先遍歷從頂點v出發(fā)圖的深度優(yōu)先遍歷算法的偽代碼：

1.訪問頂點v;visited[v]=1;2.w=頂點v的第一個鄰接點；3.while(w存在)3.1if(w未被訪問)從頂點w出發(fā)遞歸執(zhí)行該算法;3.2w=頂點v的下一個鄰接點;7.3圖的遍歷voidDFS(GraphG,intv)/*從第v個頂點出發(fā)深度優(yōu)先遍歷圖G*/{visited[v]=1；/*訪問頂點v，并置訪問標志數(shù)組相應(yīng)分量值*/

VisitFunc(v);/*訪問第v個頂點*/w=FirstAdjVex(G,v);while(w!=-1)/*鄰接點存在*/{if(!visited[w])DFS(G,w);/*對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS*/w=NextAdjVex(G,v,w);/*找下一個鄰接點*/}}對于FirstAdjVertex(G,v)以及NextAdjVertex(G,v,w)并沒有具體展開，若圖的存儲結(jié)構(gòu)不同，對應(yīng)操作的實現(xiàn)方法不同，時間耗費也不同。教材P195【算法7-3】以鄰接表為存儲結(jié)構(gòu)深度優(yōu)先遍歷圖G2.廣度優(yōu)先遍歷基本思想：訪問頂點v；依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk；分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。7.3圖的遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V17.3圖的遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V37.3圖的遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V57.3圖的遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V77.3圖的遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V87.3圖的遍歷2.廣度優(yōu)先遍歷從頂點v出發(fā)圖的廣度優(yōu)先遍歷算法的偽代碼：

1.初始化隊列Q;2.訪問頂點v;visited[v]=1;頂點v入隊列Q;3.while(隊列Q非空)3.1v=隊列Q的隊頭元素出隊;3.2w=頂點v的第一個鄰接點;3.3while(w存在)3.3.1如果w未被訪問，則訪問頂點w;visited[w]=1;頂點w入隊列Q；

3.3.2w=頂點v的下一個鄰接點；7.3圖的遍歷具體代碼

詳見教材P197生成樹的代價：設(shè)G=(V,E)是一個無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價。最小生成樹（MST）：在圖G所有生成樹中，代價最小的生成樹稱為最小生成樹。7.4最小生成樹（MST）最小生成樹的定義生成樹的代價：設(shè)G=(V,E)是一個無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價。最小生成樹（MinimumCostSpanningTree，MST）：在圖G所有生成樹中，代價最小的生成樹。最小生成樹的經(jīng)典應(yīng)用：在n個城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，每兩個城市之間架設(shè)通信線路的造價是不一樣的，而n個城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路，使總費用最少？7.4最小生成樹（MST）最小生成樹的定義數(shù)學(xué)模型：頂點———表示城市，有n個；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟代價；連通網(wǎng)——表示n個城市間通信網(wǎng)。顯然此連通網(wǎng)是一個生成樹假設(shè)G=(V,E)是一個無向連通網(wǎng)，U是頂點集V的一個非空子集，用于存放G的最小生成樹中的頂點。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。頂點集UV－Uu'vv'u頂點集T1T27.4最小生成樹（MST）最小生成樹MST性質(zhì)Prim（普里姆）算法：歸并頂點，與邊數(shù)無關(guān)，適于稠密網(wǎng)Kruskal（克魯斯卡爾）算法：歸并邊，適于稀疏網(wǎng)7.4最小生成樹（MST）如何求最小生成樹基本思想：設(shè)G=(V,E)是具有n個頂點的連通網(wǎng)，T=(U,TE)是G的最小生成樹，T的初始狀態(tài)為U={u0}（u0∈V），TE={}，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價最小的邊(u,v)并入集合TE，同時v并入U，直至U=V。7.4最小生成樹Prim算法的基本思想用偽代碼描述如下：1.初始化：U={u0}；TE={}；2.重復(fù)下述操作直到U=V：2.1在E中尋找最短邊(u，v)，且滿足u∈U，v∈V-U；

2.2U=U+{v}；2.3TE=TE+{(u，v)}；關(guān)鍵：是如何找到連接U和V-U的最短邊。普里姆（Prim）算法U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,

(A,E)∞,(A,F)19}251234192646381725ABEDCF7.4最小生成樹普里姆（Prim）算法U={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,

(F,D)25,(F,E)26}251234192646381725ABEDCF7.4最小生成樹普里姆（Prim）算法U={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}251234192646381725ABEDCF7.4最小生成樹普里姆（Prim）算法U={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}2512341926381725ABEDCF7.4最小生成樹普里姆（Prim）算法U={A,F,C,D,E}V-U={B}cost={(E,B)12}123419261725ABEDCF7.4最小生成樹普里姆（Prim）算法U={A,F,C,D,E,B}V-U={}1219261725ABEDCF7.4最小生成樹普里姆（Prim）算法7.4最小生成樹基本思想：從加權(quán)圖中選取權(quán)值最小的邊，與該邊相關(guān)聯(lián)的頂點被選擇；再從圖中選取權(quán)值最小的邊，若該邊使已經(jīng)選擇的頂點和邊構(gòu)成圈，則去掉該邊；重復(fù)步驟②，直到?jīng)]有未被選擇也未被去掉的邊，剩下的邊和圖的全部頂點構(gòu)成最小生成樹?？唆斔箍枺↘ruskal）算法251234192646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}7.4最小生成樹克魯斯卡爾（Kruskal）算法251234192646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}7.4最小生成樹克魯斯卡爾（Kruskal）算法12連通分量＝{A},{B,E},{C},{D},{F}251234192646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C},{D},{F}7.4最小生成樹克魯斯卡爾（Kruskal）算法12連通分量＝{A},{B,E},{C,D},{F}17251234192646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C,D},{F}7.4最小生成樹克魯斯卡爾（Kruskal）算法12連通分量＝{A,F},{B,E},{C,D}1917251234192646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C,D}7.4最小生成樹克魯斯卡爾（Kruskal）算法12連通分量＝{A,F,C,D},{B,E}191725251234192646381725ABEDCFABEDCF連通分量＝{A,F,C,D},{B,E}7.4最小生成樹克魯斯卡爾（Kruskal）算法12連通分量＝{A,F,C,D,B,E}19172526在非網(wǎng)圖中，最短路徑是指兩頂點之間經(jīng)歷的邊數(shù)最少的路徑。7.5最短路徑BAEDCAE：1ADE：2ADCE：3ABCE：3最短路徑在網(wǎng)圖中，最短路徑是指兩頂點之間經(jīng)歷的邊上權(quán)值之和最短的路徑。7.5最短路徑BAEDC最短路徑105030101002060AE：100ADE：90ADCE：60ABCE：70問題描述：給定帶權(quán)有向圖G＝(V,E)和源點v∈V，求從v到G中其余各頂點的最短路徑。應(yīng)用實例——計算機網(wǎng)絡(luò)傳輸?shù)膯栴}：怎樣找到一種最經(jīng)濟的方式，從一臺計算機向網(wǎng)上所有其它計算機發(fā)送一條消息。迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法——Dijkstra算法。7.5最短路徑單源點最短路徑問題基本思想：設(shè)置一個集合S存放已經(jīng)找到最短路徑的頂點，S的初始狀態(tài)只包含源點v，對vi∈V-S，假設(shè)從源點v到vi的有向邊為最短路徑。以后每求得一條最短路徑v,…,vk，就將vk加入集合S中，并將路徑v,…,vk,vi與原來的假設(shè)相比較，取路徑長度較小者為最短路徑。重復(fù)上述過程，直到集合V中全部頂點加入到集合S中。7.5最短路徑集合

V-S集合

Svkvvi迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)1007.5最短路徑迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)1007.5最短路徑迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)907.5最短路徑迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)607.5最短路徑迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B,D,C,

E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)607.5最短路徑迪杰斯特拉（Dijkstra）算法問題描述：給定帶權(quán)有向圖G＝(V,E)，對任意頂點vi,vj∈V（i≠j），求頂點vi到頂點vj的最短路徑。解決辦法1：每次以一個頂點為源點調(diào)用Dijkstra算法。顯然，時間復(fù)雜度為O(n3)。解決辦法2：弗洛伊德提出的求每一對頂點之間的最短路徑算法——Floyd算法，其時間復(fù)雜度也是O(n3)，但形式上要簡單些。7.5最短路徑每一對頂點之間的最短路徑基本思想：對于從vi到vj的弧，進行n次試探：首先考慮路徑vi,v0,vj是否存在，如果存在，則比較vi,vj和vi,v0,vj的路徑長度，取較短者為從vi到vj的中間頂點的序號不大于0的最短路徑。在路徑上再增加一個頂點v1，依此類推，在經(jīng)過n次比較后，最后求得的必是從頂點vi到頂點vj的最短路徑。7.5最短路徑弗洛伊德（Floyd）算法04116023∞0有向網(wǎng)圖鄰接矩陣7.5最短路徑弗洛伊德（Floyd）算法acb346112acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化7.5最短路徑弗洛伊德（Floyd）算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代

加入頂點adist0

=0411602370path0

=

abacbabccacab

7.5最短路徑弗洛伊德（Floyd）算法acb346112dist0

=0411602370path0

=

abacbabccacab第2次迭代

加入頂點bdist1

=046602370path1

=ababc

babccacab7.5最短路徑弗洛伊德（Floyd）算法acb346112dist1

=046602370path1

=ababcbabccacab第3次迭代

加入頂點cdist2

=0465