數(shù)據(jù)結構 第6章-圖(g)課件

第六章圖本章的主要內(nèi)容是:圖的邏輯結構圖的存儲結構及實現(xiàn)圖的連通性最小生成樹最短路徑AOV網(wǎng)與拓撲排序AOE網(wǎng)與關鍵路徑歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學領域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學的歐拉方程，復變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學占28%，天文學占11%，彈道學、航海學、建筑學等占3%。1733年，年僅26歲的歐拉擔任了彼得堡科學院數(shù)學教授。1741年到柏林擔任科學院物理數(shù)學所所長，直到1766年，重回彼得堡，沒有多久，完全失明。歐拉在數(shù)學上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。圖論——歐拉18世紀時，歐洲有一個風景秀麗的小城哥尼斯堡，那里的普萊格爾河上有七座橋。將河中的兩個島和河岸連結，城中的居民經(jīng)常沿河過橋散步，于是他們提出了一個問題：一個人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點？大家都試圖找出問題的答案，但是誰也解決不了這個問題…………

這就是哥尼斯堡七橋問題，一個著名的圖論問題。

哥尼斯堡七橋問題哥尼斯堡七橋問題

1727年在歐拉20歲的時候，被俄國請去在圣彼得堡（原列寧格勒）的科學院做研究。他的德國朋友告訴了他這個曾經(jīng)令許多人困惑的問題。

歐拉并沒有馬上跑到哥尼斯堡去走走或看看。而是他先把這個難題化成了這樣的問題來處理：把兩岸和小島縮成一點，橋化為邊，于是“七橋問題”就等價于下圖中所畫圖形的一筆畫問題了，這個圖如果能夠一筆畫完的話，對應的“七橋問題”也就解決了。哥尼斯堡七橋問題

經(jīng)過研究，歐拉發(fā)現(xiàn)了一筆畫的規(guī)律。他認為，能一筆畫的圖形必須是連通圖。連通圖就是指一個圖形各部分總是有邊相連的，這道題中的圖就是連通圖。

但是，不是所有的連通圖都可以一筆畫完的。能否一筆畫完是由圖的奇、偶點的數(shù)目來決定的。那么什么叫奇、偶點呢？與奇數(shù)（單數(shù)）條邊相連的點叫做奇點；與偶數(shù)（雙數(shù)）條邊相連的點叫做偶點。如右圖中的①、④為奇點，②、③為偶點。哥尼斯堡七橋問題

2．凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須把一個奇點為起點，另一個奇點為終點。例如下圖的線路是：①→②→③→①→④哥尼斯堡七橋問題

3．其他情況的圖都不能一筆畫出。

?請同學們告訴我，哥尼斯堡七橋問題的答案找到了沒有？

?

留一道作業(yè)：下面的五環(huán)標志可否一筆畫成？如何畫？6.1圖的邏輯結構如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。若頂點vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

如果圖的任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V46.1圖的邏輯結構圖的基本術語

簡單圖：在圖中，若不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖簡單圖V1V2V3V4V5

數(shù)據(jù)結構中討論的都是簡單圖。6.1圖的邏輯結構圖的基本術語

鄰接、依附無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和頂點vj。V1V2V3V4V5V1的鄰接點：V2、V4V2的鄰接點：V1、V3、V5在線性結構中，數(shù)據(jù)元素之間僅具有線性關系；在樹結構中，結點之間具有層次關系；在圖結構中，任意兩個頂點之間都可能有關系。FECBAD線性結構ABCDEF樹結構V1V2V3V4V5圖結構不同結構中邏輯關系的對比在線性結構中，元素之間的關系為前驅和后繼；在樹結構中，結點之間的關系為雙親和孩子；在圖結構中，頂點之間的關系為鄰接。FECBAD線性結構ABCDEF樹結構V1V2V3V4V5圖結構不同結構中邏輯關系的對比含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條弧？

6.1圖的邏輯結構含有n個頂點的無向完全圖有n×(n-1)/2條邊。含有n個頂點的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V4稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)。6.1圖的邏輯結構圖的基本術語

頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)。V1V2V3V4V56.1圖的邏輯結構圖的基本術語

在具有n個頂點、e條邊的無向圖G中，各頂點的度之和與邊數(shù)之和的關系？?==niievTD12)(V1V2V3V46.1圖的邏輯結構圖的基本術語

在具有n個頂點、e條邊的有向圖G中，各頂點的入度之和與各頂點的出度之和的關系？與邊數(shù)之和的關系？evODvIDiiii==??==11)()(nn權：是指對邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權的圖，也稱網(wǎng)圖。6.1圖的邏輯結構圖的基本術語

V1V2V3V42785路徑：在無向圖G=(V,E)中，從頂點vp到頂點vq之間的路徑是一個頂點序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向圖，則路徑也是有方向的，頂點序列滿足<vij-1,vij>∈E。6.1圖的邏輯結構圖的基本術語

V1V2V3V4V5一般情況下，圖中的路徑不惟一。V1到V4的路徑：V1V4

V1V2V3V4V1V2V5V3V4路徑長度：6.1圖的邏輯結構圖的基本術語

非帶權圖——路徑上邊的個數(shù)帶權圖——路徑上各邊的權之和V1V4：長度為8V1V2V3V4：長度為7V1V2V5V3V4：長度為15V1V2V3V4V5256328回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。6.1圖的邏輯結構圖的基本術語

V1V2V3V4V5V1V2V3V4連通圖：在無向圖中，如果從一個頂點vi到另一個頂點vj(i≠j)有路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。

6.1圖的邏輯結構圖的基本術語

如何求得一個非連通圖的連通分量?1.含有極大頂點數(shù)；2.依附于這些頂點的所有邊。連通分量1

6.1圖的邏輯結構V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2圖的基本術語

連通分量是對無向圖的一種劃分。強連通圖：在有向圖中，對圖中任意一對頂點vi和vj

(i≠j)，若從頂點vi到頂點vj和從頂點vj到頂點vi均有路徑，則稱該有向圖是強連通圖。強連通分量：非強連通圖的極大強連通子圖。

6.1圖的邏輯結構圖的基本術語

如何求得一個非連通圖的連通分量?6.1圖的邏輯結構圖的基本術語

V1V2V3V4強連通分量1

強連通分量2V1V3V4V2生成樹：n個頂點的連通圖G的生成樹是包含G中全部頂點的一個極小連通子圖。

生成森林：在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個非連通圖的生成森林。

如何理解極小連通子圖?6.1圖的邏輯結構圖的基本術語

多——構成回路少——不連通含有n-1條邊V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林6.1圖的邏輯結構圖的抽象數(shù)據(jù)類型定義

ADTGraphData

頂點的有窮非空集合和邊的集合OperationInitGraph

前置條件：圖不存在輸入：無功能：圖的初始化輸出：無后置條件：構造一個空的圖6.1圖的邏輯結構

DFSTraverse

前置條件：圖已存在輸入：遍歷的起始頂點v

功能：從頂點v出發(fā)深度優(yōu)先遍歷圖輸出：圖中頂點的一個線性排列后置條件：圖保持不變

BFSTraverse

前置條件：圖已存在輸入：遍歷的起始頂點v

功能：從頂點v出發(fā)廣度優(yōu)先遍歷圖輸出：圖中頂點的一個線性排列后置條件：圖保持不變6.1圖的邏輯結構DestroyGraph

前置條件：圖已存在輸入：無功能：銷毀圖輸出：無后置條件：釋放圖所占用的存儲空間GetVex

前置條件：圖已存在輸入：頂點v

功能：在圖中查找頂點v的數(shù)據(jù)信息輸出：頂點v的數(shù)據(jù)信息后置條件：圖保持不變endADT6.1圖的邏輯結構圖的遍歷操作圖的遍歷是在從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次。

6.1圖的邏輯結構抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數(shù)據(jù)。圖的遍歷操作要解決的關鍵問題①在圖中，如何選取遍歷的起始頂點？6.1圖的邏輯結構在線性表中，數(shù)據(jù)元素在表中的編號就是元素在序列中的位置，因而其編號是唯一的；在樹中，將結點按層序編號，由于樹具有層次性，因而其層序編號也是唯一的；在圖中，任何兩個頂點之間都可能存在邊，頂點是沒有確定的先后次序的，所以，頂點的編號不唯一。為了定義操作的方便，將圖中的頂點按任意順序排列起來，比如，按頂點的存儲順序。解決方案：從編號小的頂點開始。②從某個起點始可能到達不了所有其它頂點，怎么辦？6.1圖的邏輯結構圖的遍歷操作要解決的關鍵問題解決方案：多次調用從某頂點出發(fā)遍歷圖的算法。下面僅討論從某頂點出發(fā)遍歷圖的算法。③因圖中可能存在回路，某些頂點可能會被重復訪問，那么如何避免遍歷不會因回路而陷入死循環(huán)。④在圖中，一個頂點可以和其它多個頂點相連，當這樣的頂點訪問過后，如何選取下一個要訪問的頂點？

6.1圖的邏輯結構圖的遍歷操作要解決的關鍵問題解決方案：附設訪問標志數(shù)組visited[n]。解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。約翰·霍普克洛夫特1939年生于西雅圖。1961年進入斯坦福大學研究生院深造，1962年獲碩士學位，1964年獲博士學位。畢業(yè)后先后在普林斯頓大學、斯坦福大學等著名學府工作，也曾任職于一些科學研究機構如NSF（美國科學基金會）和NRC（美國國家研究院）。羅伯特·陶爾揚1948年4月30日生于加利福尼亞州。1969年本科畢業(yè)，進入斯坦福大學研究生院，1972年獲得博士學位。1986年圖靈獎獲得者6.1圖的邏輯結構1.深度優(yōu)先遍歷

基本思想：⑴訪問頂點v；⑵從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；⑶

重復上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。

6.1圖的邏輯結構深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V72.廣度優(yōu)先遍歷

基本思想：⑴訪問頂點v；⑵依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk；⑶分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。6.1圖的邏輯結構廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：V1V1廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7廣度優(yōu)先遍歷序列?入隊序列?出隊序列?6.1圖的邏輯結構V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V86.2圖的存儲結構及實現(xiàn)是否可以采用順序存儲結構存儲圖?圖的特點：頂點之間的關系是m:n，即任何兩個頂點之間都可能存在關系（邊），無法通過存儲位置表示這種任意的邏輯關系，所以，圖無法采用順序存儲結構。如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點、如何存儲邊。鄰接矩陣（數(shù)組表示法）基本思想：用一個一維數(shù)組存儲圖中頂點的信息，用一個二維數(shù)組（稱為鄰接矩陣）存儲圖中各頂點之間的鄰接關系。6.2圖的存儲結構及實現(xiàn)假設圖G＝(V，E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：arc[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣6.2圖的存儲結構及實現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4主對角線為0且一定是對稱矩陣。如何求頂點i的度？無向圖的鄰接矩陣6.2圖的存儲結構及實現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。如何判斷頂點i和j之間是否存在邊？無向圖的鄰接矩陣6.2圖的存儲結構及實現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4測試鄰接矩陣中相應位置的元素arc[i][j]是否為1。如何求頂點i的所有鄰接點？無向圖的鄰接矩陣6.2圖的存儲結構及實現(xiàn)V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4將數(shù)組中第i

行元素掃描一遍，若arc[i][j]為1，則頂點j

為頂點i的鄰接點。6.2圖的存儲結構及實現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4有向圖的鄰接矩陣一定不對稱嗎？不一定，例如有向完全圖。6.2圖的存儲結構及實現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點i的出度？鄰接矩陣的第i行元素之和。6.2圖的存儲結構及實現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求頂點i的入度？鄰接矩陣的第i列元素之和。6.2圖的存儲結構及實現(xiàn)有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判斷從頂點i到頂點j是否存在邊？測試鄰接矩陣中相應位置的元素arc[i][j]是否為1。網(wǎng)圖的鄰接矩陣6.2圖的存儲結構及實現(xiàn)網(wǎng)圖的鄰接矩陣可定義為：

arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞

∞

∞

∞087∞∞0arc=鄰接矩陣存儲無向圖的類constintMaxSize=10;template<classT>classMgraph{public:MGraph(Ta[],intn,inte);~MGraph()

voidDFSTraverse(intv);voidBFSTraverse(intv);private:Tvertex[MaxSize];intarc[MaxSize][MaxSize];intvertexNum,arcNum;};6.2圖的存儲結構及實現(xiàn)鄰接矩陣中圖的基本操作——構造函數(shù)確定圖的頂點個數(shù)和邊的個數(shù)；2.輸入頂點信息存儲在一維數(shù)組vertex中；3.初始化鄰接矩陣；4.依次輸入每條邊存儲在鄰接矩陣arc中；4.1輸入邊依附的兩個頂點的序號i,j；4.2將鄰接矩陣的第i行第j列的元素值置為1；4.3將鄰接矩陣的第j行第i列的元素值置為1；6.2圖的存儲結構及實現(xiàn)template<classT>MGraph::MGraph(Ta[],intn,inte){vertexNum=n;arcNum=e;for(i=0;i<vertexNum;i++)vertex[i]=a[i];for(i=0;i<vertexNum;i++)//初始化鄰接矩陣

for(j=0;j<vertexNum;j++)arc[i][j]=0;for(k=0;k<arcNum;k++)//依次輸入每一條邊{cin>>i>>j;//邊依附的兩個頂點的序號arc[i][j]=1;arc[j][i]=1;//置有邊標志

}}6.2圖的存儲結構及實現(xiàn)鄰接矩陣中圖的基本操作——構造函數(shù)鄰接矩陣中圖的基本操作——深度優(yōu)先遍歷template<classT>voidMGraph::DFSTraverse(intv)

{cout<<vertex[v];visited[v]=1;for(j=0;j<vertexNum;j++)if(arc[v][j]==1&&visited[j]==0)

DFSTraverse(j);}6.2圖的存儲結構及實現(xiàn)鄰接矩陣中圖的基本操作——廣度優(yōu)先遍歷template<classT>voidMGraph::BFSTraverse(intv)

{front=rear=-1;//假設采用順序隊列且不會發(fā)生溢出cout<<vertex[v];visited[v]=1;Q[++rear]=v;while(front!=rear){v=Q[++front];

for(j=0;j<vertexNum;j++)if(arc[v][j]==1&&visited[j]==0){cout<<vertex[j];visited[j]=1;Q[++rear]=j;}}}6.2圖的存儲結構及實現(xiàn)鄰接表鄰接表存儲的基本思想：對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維數(shù)組構成了頂點表。

6.2圖的存儲結構及實現(xiàn)圖的鄰接矩陣存儲結構的空間復雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？假設圖G有n個頂點e條邊，則存儲該圖需要O(n2)。鄰接表有兩種結點結構：頂點表結點和邊表結點。vertexfirstedge

adjvex

next

頂點表邊表vertex：數(shù)據(jù)域，存放頂點信息。

firstedge：指針域，指向邊表中第一個結點。

adjvex：鄰接點域，邊的終點在頂點表中的下標。next：指針域，指向邊表中的下一個結點。

6.2圖的存儲結構及實現(xiàn)structArcNode{intadjvex;ArcNode*next;};template<classT>structVertexNode{

Tvertex;

ArcNode*firstedge;};定義鄰接表的結點

6.2圖的存儲結構及實現(xiàn)vertexfirstedge

adjvex

next103∧23∧1∧01∧V1V2

V3V40123vertexfirstedge6.2圖的存儲結構及實現(xiàn)V1V3V4V2無向圖的鄰接表邊表中的結點表示什么？每個結點對應圖中的一條邊，鄰接表的空間復雜度為O(n+e)。103∧23∧1∧01∧V1V2

V3V40123vertexfirstedge6.2圖的存儲結構及實現(xiàn)V1V3V4V2無向圖的鄰接表如何求頂點i的度？頂點i的邊表中結點的個數(shù)。如何判斷頂點i和頂點j之間是否存在邊?測試頂點i的邊表中是否存在終點為j的結點。6.2圖的存儲結構及實現(xiàn)103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2無向圖的鄰接表6.2圖的存儲結構及實現(xiàn)有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點i的出度？頂點i的出邊表中結點的個數(shù)。6.2圖的存儲結構及實現(xiàn)有向圖的鄰接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點i的入度？各頂點的出邊表中以頂點i為終點的結點個數(shù)。6.2圖的存儲結構及實現(xiàn)有向圖的鄰接表V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求頂點i的所有鄰接點？遍歷頂點i的邊表，該邊表中的所有終點都是頂點i的鄰接點。6.2圖的存儲結構及實現(xiàn)網(wǎng)圖的鄰接表V1V2V3V4278521V1V2

V3V40123vertexfirstedge∧52∧83∧70∧鄰接表存儲有向圖的類constintMaxSize=10;//圖的最大頂點數(shù)template<classT>classALGraph{public:ALGraph(Ta[],intn,inte);~ALGraph;voidDFSTraverse(intv);

voidBFSTraverse(intv);private:VertexNodeadjlist[MaxSize];

intvertexNum,arcNum;};6.2圖的存儲結構及實現(xiàn)鄰接表中圖的基本操作——構造函數(shù)

1.確定圖的頂點個數(shù)和邊的個數(shù)；2.輸入頂點信息，初始化該頂點的邊表；3.依次輸入邊的信息并存儲在邊表中；3.1輸入邊所依附的兩個頂點的序號i和j；3.2生成鄰接點序號為j的邊表結點s；

3.3將結點s插入到第i個邊表的頭部；6.2圖的存儲結構及實現(xiàn)template<classT>ALGraph::ALGraph(Ta[],intn,inte){vertexNum=n;arcNum=e;

for(i=0;i<vertexNum;i++)

//輸入頂點信息，初始化邊表{

adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}

6.2圖的存儲結構及實現(xiàn)鄰接表中圖的基本操作——構造函數(shù)

sfor(k=0;k<arcNum;k++)//輸入邊的信息存儲在邊表中{

cin>>i>>j;

s=newArcNode;s->adjvex=j; s->next=adjlist[i].firstedge;adjlist[i].firstedge=s;}}6.2圖的存儲結構及實現(xiàn)12V1V2

V3V40123∧∧∧∧①②鄰接表中圖的基本操作——深度優(yōu)先遍歷template<classT>voidALGraph::DFSTraverse(intv){

cout<<adjlist[v].vertex;visited[v]=1;p=adjlist[v].firstedge;while(p!=NULL)

{j=p->adjvex;if(visited[j]==0)DFSTraverse(j);

p=p->next;}}6.2圖的存儲結構及實現(xiàn)鄰接表中圖的基本操作——廣度優(yōu)先遍歷template<classT>voidALGraph::BFSTraverse(intv)

{front=rear=-1;cout<<adjlist[v].vertex;visited[v]=1;Q[++rear]=v;while(front!=rear){v=Q[++front];p=adjlist[v].firstedge;while(p!=NULL)

{j=p->adjvex;if(visited[j]==0){cout<<adjlist[j].vertex;visited[j]=1;Q[++rear]=j;}p=p->next;}}}6.2圖的存儲結構及實現(xiàn)十字鏈表鄰接表6.2圖的存儲結構及實現(xiàn)逆鄰接表將鄰接表與逆鄰接表合二為一?為什么要合并？V1V2V3V412∧3∧0v1v2v3v4∧01231∧3∧0∧2∧v1v2v3v4012303∧十字鏈表的結點結構vertexfirstinfirstout頂點表結點tailvexheadvexheadlinktaillink邊表結點tailvex：弧的起點在頂點表中的下標；headvex：弧的終點在頂點表中的下標；headlink：入邊表指針域；taillink：出邊表指針域。6.2圖的存儲結構及實現(xiàn)vertex：數(shù)據(jù)域，存放頂點信息；firstin：入邊表頭指針；firstout：出邊表頭指針；3031∧3210V1V2V3V423

∧0102∧6.2圖的存儲結構及實現(xiàn)十字鏈表存儲有向圖∧∧V1V2V3V4∧∧∧v3v4v4v1v1v2v1v3v4v2圖的存儲結構的比較——鄰接矩陣和鄰接表O（n2）O（n+e）O（n2）O（n+e）空間性能時間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一6.2圖的存儲結構及實現(xiàn)6.3圖的連通性要想判定一個無向圖是否為連通圖，或有幾個連通分量，通過對無向圖遍歷即可得到結果。非連通圖：需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。

連通圖：僅需從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索（或廣度優(yōu)先搜索），便可訪問到圖中所有頂點。

無向圖的連通性count=0;2.for(圖中每個頂點v)2.1if(v尚未被訪問過)

2.1.1count++;2.1.2從v出發(fā)遍歷該圖；3.if(count==1)

cout<<"圖是連通的";

elsecout<<"圖中有"<<count<<"個連通分量";求無向圖的連通分量6.3圖的連通性有向圖的連通性⑴從某頂點出發(fā)進行深度優(yōu)先遍歷，并按其所有鄰接點都訪問（即出棧）的順序將頂點排列起來。⑵從最后完成訪問的頂點出發(fā)，沿著以該頂點為頭的弧作逆向的深度優(yōu)先遍歷。若不能訪問到所有頂點，則從余下的頂點中最后訪問的那個頂點出發(fā)，繼續(xù)作逆向的深度優(yōu)先遍歷，直至有向圖中所有頂點都被訪問到為止。⑶每一次逆向深度優(yōu)先遍歷所訪問到的頂點集便是該有向圖的一個強連通分量的頂點集。6.3圖的連通性（a）深度優(yōu)先生成樹（b）廣度優(yōu)先生成樹生成樹6.3圖的連通性V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8由深度優(yōu)先遍歷得到的為深度優(yōu)先生成樹，由廣度優(yōu)先遍歷得到的為廣度優(yōu)先生成樹。

一個連通圖的生成樹可能不唯一，由不同的遍歷次序、從不同頂點出發(fā)進行遍歷都會得到不同的生成樹。

對于非連通圖，通過圖的遍歷，將得到的是生成森林。

結論：6.3圖的連通性生成樹生成樹的代價：設G=（V，E）是一個無向連通網(wǎng)，生成樹上各邊的權值之和稱為該生成樹的代價。

最小生成樹：在圖G所有生成樹中，代價最小的生成樹稱為最小生成樹。應用舉例——最小生成樹最小生成樹最小生成樹的概念可以應用到許多實際問題中。例：在n個城市之間建造通信網(wǎng)絡，至少要架設n-1條通信線路，而每兩個城市之間架設通信線路的造價是不一樣的，那么如何設計才能使得總造價最小？MST性質假設G=(V,E)是一個無向連通網(wǎng)，U是頂點集V的一個非空子集。若(u,v)是一條具有最小權值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。應用舉例——最小生成樹頂點集UV－Uu'vv'u頂點集T1T2基本思想：設G=(V,E)是具有n個頂點的連通網(wǎng)，T=(U,TE)是G的最小生成樹，T的初始狀態(tài)為U={u0}（u0∈V），TE={}，重復執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價最小的邊(u,v)并入集合TE，同時v并入U，直至U=V。關鍵:是如何找到連接U和V-U的最短邊。

普里姆（Prim）算法

應用舉例——最小生成樹利用MST性質，可以用下述方法構造候選最短邊集：對應V-U中的每個頂點，保留從該頂點到U中的各頂點的最短邊。U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725應用舉例——最小生成樹ABEDCFPrim算法

Prim算法

應用舉例——最小生成樹251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,(F,D)25,(F,E)26}Prim算法

應用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}

Prim算法

應用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}

Prim算法

應用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C,D,E}V-U={B}cost={(E,B)12}

Prim算法

應用舉例——最小生成樹251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}數(shù)組lowcost[n]：用來保存集合V-U中各頂點與集合U中頂點最短邊的權值，lowcost[v]=0表示頂點v已加入最小生成樹中；數(shù)組adjvex[n]：用來保存依附于該邊（集合V-U中各頂點與集合U中頂點的最短邊）在集合U中的頂點。數(shù)據(jù)結構設計表示頂點vi和頂點vk之間的權值為w，其中：vi∈V-U且vk∈Ulowcost[i]=wadjvex[i]=k應用舉例——最小生成樹如何用數(shù)組lowcost和adjvex表示候選最短邊集？

i

數(shù)組B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U輸出adjvexlowcostA34A46A∞A∞A19{A}{B,C,D,E,F}(AF)19adjvexlowcostA34F25F25F26

{A,F}{B,C,D,E}(FC)25adjvexlowcostA34

C17F26

{A,F,C}{B,D,E}(CD)17adjvexlowcostA34

F26

{A,F,C,D}{B,E}(FE)26adjvexlowcostE12

{A,F,C,D,E}{B}(EB)12adjvexlowcost

{A,F,C,D,E,B}{}

應用舉例——最小生成樹1.初始化兩個輔助數(shù)組lowcost和adjvex；2.輸出頂點u0，將頂點u0加入集合U中；3.重復執(zhí)行下列操作n-1次

3.1在lowcost中選取最短邊，取adjvex中對應的頂點序號k；

3.2輸出頂點k和對應的權值；

3.3將頂點k加入集合U中；

3.4調整數(shù)組lowcost和adjvex；應用舉例——最小生成樹Prim算法——偽代碼

克魯斯卡爾（Kruskal）算法

基本思想：設無向連通網(wǎng)為G＝(V,E)，令G的最小生成樹為T＝(U,TE)，其初態(tài)為U＝V，TE＝{}，然后，按照邊的權值由小到大的順序，考察G的邊集E中的各條邊。若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊作為最小生成樹的邊加入到T中，同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個連通分量，則舍去此邊，以免造成回路，如此下去，當T中的連通分量個數(shù)為1時，此連通分量便為G的一棵最小生成樹。

應用舉例——最小生成樹251234192646382025ABEDCF應用舉例——最小生成樹ABEDCF連通分量＝{A},{B},{C},{D},{E},{F}251234192646382025ABEDCF應用舉例——最小生成樹ABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}251234192646382025ABEDCF應用舉例——最小生成樹ABEDCF連通分量＝{A},{B,E},{C},{D},{F}12連通分量＝{A,F},{B,E},{C},{D}19251234192646382025ABEDCF應用舉例——最小生成樹ABEDCF連通分量＝{A,F},{B,E},{C},{D}12連通分量＝{A,F},{B,E},{C,D}1920251234192646382025ABEDCF應用舉例——最小生成樹ABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}192025251234192646382025ABEDCF應用舉例——最小生成樹ABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}192025261.初始化：U=V；TE={}；2.循環(huán)直到T中的連通分量個數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點u、v位于T的兩個不同連通分量，則

2.2.1將邊(u，v)并入TE；

2.2.2將這兩個連通分量合為一個；

2.3在E中標記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選?。粦门e例——最小生成樹Kruskal算法——偽代碼在非網(wǎng)圖中，最短路徑是指兩頂點之間經(jīng)歷的邊數(shù)最少的路徑。

應用舉例——最短路徑最短路徑

BAEDCAE：1ADE：2ADCE：3ABCE：3應用舉例——最短路徑最短路徑

在網(wǎng)圖中，最短路徑是指兩頂點之間經(jīng)歷的邊上權值之和最短的路徑。

BAEDC105030101002060AE：100ADE：90ADCE：60ABCE：70問題描述：給定帶權有向圖G＝(V,E)和源點v∈V，求從v到G中其余各頂點的最短路徑。

單源點最短路徑問題

應用舉例——最短路徑應用實例——計算機網(wǎng)絡傳輸?shù)膯栴}：怎樣找到一種最經(jīng)濟的方式，從一臺計算機向網(wǎng)上所有其它計算機發(fā)送一條消息。迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法——Dijkstra算法?；舅枷耄涸O置一個集合S存放已經(jīng)找到最短路徑的頂點，S的初始狀態(tài)只包含源點v，對vi∈V-S，假設從源點v到vi的有向邊為最短路徑。以后每求得一條最短路徑v,…,vk，就將vk加入集合S中，并將路徑v,…,vk,vi與原來的假設相比較，取路徑長度較小者為最短路徑。重復上述過程，直到集合V中全部頂點加入到集合S中。Dijkstra算法應用舉例——最短路徑

集合

V-S集合

SvkvviDijkstra算法的基本思想應用舉例——最短路徑ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100應用舉例——最短路徑Dijkstra算法ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100應用舉例——最短路徑BDijkstra算法ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90應用舉例——最短路徑BDDijkstra算法ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60應用舉例——最短路徑BDCDijkstra算法ABAEDC105030101002060Dijkstra算法S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60應用舉例——最短路徑BDCE圖的存儲結構：帶權的鄰接矩陣存儲結構

數(shù)組dist[n]：每個分量dist[i]表示當前所找到的從始點v到終點vi的最短路徑的長度。初態(tài)為：若從v到vi有弧，則dist[i]為弧上權值；否則置dist[i]為∞。數(shù)組path[n]：path[i]是一個字符串，表示當前所找到的從始點v到終點vi的最短路徑。初態(tài)為：若從v到vi有弧，則path[i]為vvi；否則置path[i]空串。數(shù)組s[n]：存放源點和已經(jīng)生成的終點，其初態(tài)為只有一個源點v。

設計數(shù)據(jù)結構

:應用舉例——最短路徑迪杰斯特拉算法的主要步驟如下：(1)g為用鄰接矩陣表示的帶權圖。將v0到其余頂點的路徑長度初始化為權值；

S←{v0}，dist［i］=g.arcs［v0］［vi］；(2)選擇vk，使得vk為目前求得的下一條從v0出發(fā)的最短路徑的終點。(3)修改從v0出發(fā)到集合V-S上任一頂點vi的最短路徑的長度。

如果dist［k］+g.arcs［k］［i］<dist［i］

則修改dist［i］為:dist［k］+g.arcs［k］［i］(4)重復(2)、(3)n-1次，即可按最短路徑長度的遞增順序，逐個求出v0到圖中其它每個頂點的最短路徑。實例：求圖7.26中v0頂點到其它各頂點的最短路徑

v0v2v5v4v1v3201531050104515353020012345012345∞5010∞45∞∞∞15∞10∞20∞∞15∞∞∞20∞∞35∞∞∞∞30∞∞∞∞∞3∞∞圖7.26一個帶權有向圖及其鄰接矩陣應用舉例——最短路徑終點從V0到各終點的dist[i]值和最短距離V110∞45∞V250/2545∞V345//45∞V4///45∞////

加入S集合的頂點{V0}V2V3V1V4無最短路徑值10254545

V5

50∞dist［k］+g.arcs［k］［i］<dist［i］每一對頂點之間的最短路徑

問題描述：給定帶權有向圖G＝(V,E)，對任意頂點vi,vj∈V（i≠j），求頂點vi到頂點vj的最短路徑。

應用舉例——最短路徑解決辦法1：每次以一個頂點為源點，調用Dijkstra算法n次。顯然，時間復雜度為O(n3)。解決辦法2：弗洛伊德提出的求每一對頂點之間的最短路徑算法——Floyd算法，其時間復雜度也是O(n3)，但形式上要簡單些?；舅枷耄簩τ趶膙i到vj的弧，進行n次試探：首先考慮路徑vi,v0,vj是否存在，如果存在，則比較vi,vj和vi,v0,vj的路徑長度，取較短者為從vi到vj的中間頂點的序號不大于0的最短路徑。在路徑上再增加一個頂點v1，依此類推，在經(jīng)過n次比較后，最后求得的必是從頂點vi到頂點vj的最短路徑。

Floyd算法應用舉例——最短路徑04116023∞0有向網(wǎng)圖鄰接矩陣Floyd算法應用舉例——最短路徑acb346112Floyd算法應用舉例——最短路徑acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化Floyd算法應用舉例——最短路徑acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代dist0

=0411602370path0

=

abacbabccacab

Floyd算法應用舉例——最短路徑acb346112第2次迭代dist0

=0411602370path0

=

abacbabccacabdist1

=046602370path1

=

ababc

babccacabFloyd算法應用舉例——最短路徑acb346112第3次迭代dist2

=046502370path2

=

ababcbcabccacabdist1

=046602370path1

=

ababcbabccacab圖的存儲結構：帶權的鄰接矩陣存儲結構

數(shù)組dist[n][n]：存放在迭代過程中求得的最短路徑長度。迭代公式：數(shù)組path[n][n]：存放從vi到vj的最短路徑，初始為path[i][j]="vivj"。設計數(shù)據(jù)結構dist-1[i][j]=arc[i][j]dist

k[i][j]=min{distk-1[i][j],distk-1[i][k]+distk-1[k][j]}0≤k≤n-1應用舉例——最短路徑voidFloyd(MGraphG){for(i=0;i<G.vertexNum;i++)

for(j=0;j<G.vertexNum;j++)

{dist[i][j]=G.arc[i][j];

if(dist[i][j]!=∞)

path[i][j]=G.vertex[i]+G.vertex[j];

elsepath[i][j]="";}應用舉例——最短路徑Floyd算法——C++描述

for(k=0;k<G.vertexNum;k++)

for(i=0;i<G.vertexNum;i++)

for(j=0;j<G.vertexNum;j++)

if(dist[i][k]+dist[k][j]<dist[i][j]){

dist[i][j]=dist[i][k]+dist[k][j];

path[i][j]=path[i][k]+path[k][j];}}應用舉例——最短路徑Floyd算法——C++描述AOV網(wǎng)：在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系，稱這樣的有向圖為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。

應用舉例——拓撲排序AOV網(wǎng)什么是工程？工程有什么共性？AOV網(wǎng)中出現(xiàn)回路意味著什么？AOV網(wǎng)：在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系，稱這樣的有向圖為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。

應用舉例——拓撲排序AOV網(wǎng)2.AOV網(wǎng)中不能出現(xiàn)回路。AOV網(wǎng)特點：1.AOV網(wǎng)中的弧表示活動之間存在的某種制約關系。

什么是工程？工程有什么共性？編號課程名稱先修課C1高等數(shù)學無C2計算機導論無C3離散數(shù)學C1C4程序設計C1,C2C5數(shù)據(jù)結構C3，C4C6計算機原理C2，C4C7數(shù)據(jù)庫原理C4，C5，C6應用舉例——拓撲排序C1C2C3C4C6C5C7AOV網(wǎng)拓撲序列：設G=(V，E)是一個具有n個頂點的有向圖，V中的頂點序列v1,v2,…,vn稱為一個拓撲序列，當且僅當滿足下列條件：若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。拓撲排序：對一個有向圖構造拓撲序列的過程稱為拓撲排序。應用舉例——拓撲排序拓撲排序拓撲序列使得AOV網(wǎng)中所有應存在的前驅和后繼關系都能得到滿足?；舅枷耄孩艔腁OV網(wǎng)中選擇一個沒有前驅的頂點并且輸出；⑵從AOV網(wǎng)中刪去該頂點，并且刪去所有以該頂點為尾的??；⑶

重復上述兩步，直到全部頂點都被輸出，或AOV網(wǎng)中不存在沒有前驅的頂點。

應用舉例——拓撲排序拓撲排序拓撲排序的結果？應用舉例——拓撲排序拓撲排序C1C2C3C4C6C5C7拓撲序列：C1,C2,C3,C4,C5,C6,C7

應用舉例——拓撲排序拓撲排序C1C2C3C4C6C4拓撲序列：C1,C2,C3,說明AOV網(wǎng)中存在回路。設計數(shù)據(jù)結構

1.圖的存儲結構：采用鄰接表存儲，在頂點表中增加一個入度域。頂點表結點

in

vertexfirstedge2.棧S：存儲所有無前驅的頂點。應用舉例——拓撲排序(a)一個AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲

012345

invertexfirstedge3A∧0B1C3D0E2F

∧

0

3∧

0

0

5∧

2

3∧

3

5∧ABCDEF應用舉例——拓撲排序拓撲排序應用舉例——拓撲排序拓撲排序012345

invertexf