5-1引言v第5章圖七巧板涂色問題【問題】假設(shè)有下圖所示七巧板，使用至多4種不同顏色對七巧板涂色，要求每個區(qū)域涂一種顏色，相鄰區(qū)域的顏色互不相同。求涂色方案。抽象ABEDCFGDAFECGB【想法——數(shù)據(jù)模型】將七巧板的每個區(qū)域看成一個頂點，如果兩個區(qū)域相鄰，則這兩個頂點之間有邊相連，從而將七巧板抽象為圖結(jié)構(gòu)。【問題】某公司生產(chǎn)若干種化學(xué)制品，其中有些制品如果放在一起可能產(chǎn)生化學(xué)反應(yīng)，因此公司必須將倉庫分成相互隔離的若干區(qū)，請設(shè)計合理的倉庫分區(qū)。國際學(xué)術(shù)會議【想法——數(shù)據(jù)模型】將成員看成一個頂點，如果兩個成員可以直接交談，則這兩個頂點之間有邊相連，從而將分組問題抽象為圖結(jié)構(gòu)——二部圖。ABEDCF【問題】出席某國際會議的六個成員A、B、C、D、E、F，假設(shè)A會講漢語、法語和日語，B會講德語、日語和俄語，C會講英語和法語，D會講漢語和西班牙語，E會講英語和德語，F(xiàn)會講俄語和西班牙語，如將此六人分成兩組，能否出現(xiàn)同一組內(nèi)任意兩人不能直接交談的情況？V1={A,E,F}V2={B,C,D}【問題】排課問題。教室構(gòu)成一組頂點，課程構(gòu)成一組頂點，如果A教室可以安排B課程，則頂點A和B之間有一條邊。農(nóng)夫過河問題【問題】農(nóng)夫過河問題。一個農(nóng)夫帶著一只狼、一只羊和一筐菜，想從河一邊（左岸）乘船到另一邊（右岸），由于船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河，但是如果沒有農(nóng)夫看管，則狼會吃羊，羊會吃菜。其給出過河方案?！鞠敕ā獢?shù)據(jù)模型】用0表示在河的左岸，用1表示在河的右岸，將每一個可能的狀態(tài)抽象為一個頂點，邊表示狀態(tài)轉(zhuǎn)移發(fā)生的條件。左岸河右岸農(nóng)夫

狼

羊

菜

0000農(nóng)夫

羊

1010農(nóng)夫和羊0000010000010101001010101011110111111110教學(xué)計劃編排【問題】已知計算機專業(yè)的核心課程如下表所示，編制合適的教學(xué)計劃?！鞠敕ā獢?shù)據(jù)模型】用頂點表示課程，如果從頂點

ci到

cj之間存在邊<ci,cj>，則表示課程

ci是課程

cj的先修課。課程編號課程名稱先修課程c1程序設(shè)計基礎(chǔ)無c2電子技術(shù)基礎(chǔ)無c3離散數(shù)學(xué)c1c4數(shù)據(jù)結(jié)構(gòu)c1c5計算機原理c1c2c6操作系統(tǒng)c3c4c5c7計算機網(wǎng)絡(luò)c4c5c6c8數(shù)據(jù)庫原理及應(yīng)用c4c5c2c1c3c4c5c8c6c7社交網(wǎng)絡(luò)路徑規(guī)劃關(guān)于圖結(jié)構(gòu)什么是圖？在邏輯上有什么特點？有哪些基本術(shù)語？如何存儲圖結(jié)構(gòu)？在不同的存儲結(jié)構(gòu)上，如何實現(xiàn)圖的基本操作？最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑5-2圖的邏輯結(jié)構(gòu)v第五章圖圖的定義和基本術(shù)語圖的抽象數(shù)據(jù)類型定義學(xué)什么？歐拉1707年出生在瑞士，19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線、多面體的歐拉定理、立體解析幾何的歐拉變換公式、四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)、微分方程的歐拉方程、數(shù)論的歐拉常數(shù)、變分學(xué)的歐拉方程、復(fù)變函數(shù)的歐拉公式等等。歐拉對哥尼斯堡七橋問題的提出和解答開創(chuàng)了圖論的研究。圖的遍歷操作5-2-1圖的定義和基本術(shù)語v第五章圖圖的定義圖：由頂點的集合和頂點之間邊的集合組成，通常表示為：

數(shù)據(jù)元素G=(V，E)頂點的集合頂點之間邊的集合v0v1v2v4v3空表、空棧、空隊列、空樹、空二叉樹、空圖、零圖等均表示一種可能的狀態(tài)，一般作為條件判斷V

=

Φ的圖稱為空圖，V

≠

Φ但E

=Φ的圖稱為零圖。v0v1無向邊：表示為(vi,vj)，頂點vi和vj之間的邊沒有方向v2v4v3無向圖：圖中任意兩個頂點之間的邊都是無向邊v0v1有向邊（弧）：表示為<vi,vj>，從vi到vj的邊有方向v2v4有向圖：圖中任意兩個頂點之間的邊都是有向邊圖（邊是否有方向）無向圖有向圖圖的分類權(quán)：對邊賦予的有意義的數(shù)值量v0v1v2v4v3帶權(quán)圖（網(wǎng)圖）：邊上帶權(quán)的圖v0v1v2v427852785635423樹結(jié)構(gòu)中，權(quán)通常賦予在結(jié)點圖（邊上是否帶權(quán)）非帶權(quán)圖帶權(quán)圖圖的分類v0v1v2v4v3稠密圖：邊數(shù)很多的圖v0v1v2v4v3稀疏圖：邊數(shù)很少的圖圖（邊數(shù)的多寡）稠密圖稀疏圖圖的分類圖的邏輯關(guān)系鄰接、依附：無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和頂點vjv0v1v2v4v3v0的鄰接點：v1、v4v2的鄰接點：v1、v3v0v1v2v4鄰接、依附：有向圖中，對于任意兩個頂點vi和頂點vj，若存在弧<vi，vj>，則稱頂點vi鄰接到

vj，頂點vj鄰接自vi，同時稱弧<vi，vj>依附于頂點vi和頂點vjv0的鄰接點：v1、v4v2的鄰接點：v0a1ai-1aiana2ACBDEFv0v1v2v4v3線性結(jié)構(gòu)中，數(shù)據(jù)元素之間具有線性關(guān)系，邏輯關(guān)系表現(xiàn)為前驅(qū)-后繼；樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系，邏輯關(guān)系表現(xiàn)為雙親-孩子圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系，邏輯關(guān)系表現(xiàn)為鄰接

圖的邏輯關(guān)系完全圖無向完全圖：無向圖中，任意兩個頂點之間都存在邊v0v1v2v4v0v1v2有向完全圖：有向圖中，任意兩個頂點之間都存在方向相反的兩條弧n個頂點的無向完全圖有多少條邊？n×(n-1)/2

n個頂點的有向完全圖有多少條??？n×(n-1)

度、入度和出度頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)頂點的入度：在有向圖中，頂點v

的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v

的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)；v0v1v2v4TD(v0)=2，TD(v3)=3ID(v0)=1，OD(v0)=2

v0v1v2v4v3v0v1v2v4v0v1v2v4v3在具有n個頂點、e條邊的無向圖中，各頂點的度之和與邊數(shù)之和有什么關(guān)系？在具有n個頂點、e條邊的有向圖中，各頂點的入度之和與各頂點的出度之和有什么關(guān)系？與邊數(shù)之和有什么關(guān)系？度、入度和出度路徑、回路v0v1v2v4v3路徑：在無向圖中，頂點vp和頂點vq之間的路徑是一個頂點序列(vp=vi0,vi1,…,vim=vq)，其中(vij-1,vij)∈E(1≤j≤m)頂點v0和頂點v4之間的路徑：v0v4、v0v1v3v4、v0v1v2v3v4、從頂點v0到頂點v4的路徑：v0v4、v0v1v4路徑：在有向圖中，從頂點vp到頂點vq的路徑是一個頂點序列(vp=vi0,vi1,…,vim=vq)，其中<vij-1,vij>∈E(1≤j≤m)v0v1v2v4v0v1v2v4v3簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路。不致混淆的情況下，路徑和回路都是簡單的路徑、回路v0v1v2v4回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑v0v1v2v4v3子圖：若圖G=(V,E)，G'=(V',E')，如果V'

V

且E'

E，則稱圖G'是G的子圖子圖v0v1v0v1v3v0v1v2v3v0v1v2v4v3v0v2v3v0v1v3v0v1v2v3v0v1v2v4v3連通頂點：在無向圖中，如果頂點vi和頂點vj(i≠j)之間有路徑，則稱頂點vi和vj是連通的連通圖連通圖：在無向圖中，如果任意兩個頂點都是連通的，則稱該無向圖是連通圖v0v1v2v3v6v4v5對于非連通圖，實際處理中會有什么問題？從某頂點出發(fā)進行遍歷，不能訪問所有頂點連通分量連通分量：非連通圖的極大連通子圖含有極大頂點數(shù)依附于這些頂點的所有邊v0v1v2v3v6v4v5v0v1v2v3連通分量1v6v4v5連通分量2連通分量是對無向圖的一種劃分強連通圖、強連通分量強連通頂點：在有向圖中，如果從頂點vi到頂點vj和從頂點vj到頂點vi均有路徑，則稱頂點vi和vj是強連通的強連通圖：在有向圖中，如果任意兩個頂點都是強連通的，則稱該有向圖是強連通圖v0v1v2v3v0v1v2v3強連通分量：非強連通圖的極大連通子圖強連通分量1強連通分量2v0v2v4v15-2-2圖的抽象數(shù)據(jù)類型定義v第五章圖圖的抽象數(shù)據(jù)類型定義圖是一種與具體應(yīng)用密切相關(guān)的數(shù)據(jù)結(jié)構(gòu)，基本操作有很大差別ADTGraphDataModel

頂點的有窮非空集合和頂點之間邊的集合Operation

CreateGraph：圖的建立DestroyGraph：圖的銷毀DFTraverse：深度優(yōu)先遍歷圖BFTraverse：廣度優(yōu)先遍歷圖endADT簡單起見，只討論圖的遍歷圖的遍歷圖的遍歷：從圖中某一頂點出發(fā)訪問所有頂點，并且每個結(jié)點僅被訪問一次抽象操作，可以是對頂點的各種處理，這里簡化為輸出頂點的數(shù)據(jù)在圖中，如何選取遍歷的起始頂點？ACBDEFa1ana2ai-1ai解決方案：將圖中的頂點按任意順序排列起來，從編號最小的頂點開始v0v1v2v4v3圖的遍歷圖的遍歷：從圖中某一頂點出發(fā)訪問所有頂點，并且每個結(jié)點僅被訪問一次從某頂點出發(fā)能訪問其他所有頂點嗎？解決方案：多次調(diào)用圖遍歷算法下面僅討論從某頂點出發(fā)遍歷圖的算法v6v7v5如何避免遍歷不會因回路而陷入死循環(huán)？解決方案：附設(shè)訪問標(biāo)志數(shù)組visited[n]v0v1v2v4v3圖的遍歷圖的遍歷：從圖中某一頂點出發(fā)訪問所有頂點，并且每個結(jié)點僅被訪問一次a1ana2ai-1aiACBDEF采用什么次序依次訪問圖中所有頂點？解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷先序：A

BD

CEF中序：DB

A

ECF后序：DB

EFC

A線性序：a1a2…

an圖的深度優(yōu)先遍歷（1）訪問頂點v（2）從v

的未被訪問的鄰接點中選取一個頂點w，從w

出發(fā)進行深度優(yōu)先遍歷（3）重復(fù)上述兩步，直至訪問所有和v

有路徑相通的頂點從頂點v

出發(fā)進行深度優(yōu)先遍歷的基本思想是：是一個遞歸的過程算法：DFTraverse輸入：頂點的編號v輸出：無1.訪問頂點v;修改標(biāo)志visited[v]=1;2.w=頂點v的第一個鄰接點；3.while(w存在)3.1if(w未被訪問)從頂點w出發(fā)遞歸執(zhí)行該算法;3.2w=頂點v的下一個鄰接點;v5v0v3v2v1v4

v0

v1

v4運行實例——深入理解操作過程深度優(yōu)先遍歷序列：v0v1v4圖的深度優(yōu)先遍歷v5v0v3v2v1v4

v0

v1

v2深度優(yōu)先遍歷序列：v0v1v4v2

v3v3運行實例——深入理解操作過程圖的深度優(yōu)先遍歷v5v0v3v2v1v4

v0深度優(yōu)先遍歷序列：v0v1v4v2v3

v5v5運行實例——深入理解操作過程圖的深度優(yōu)先遍歷從頂點v

出發(fā)進行廣度優(yōu)先遍歷的基本思想是：⑴訪問頂點v⑵依次訪問v

的各個未被訪問的鄰接點v1,v2,…,vk⑶分別從v1,v2,…,vk出發(fā)依次訪問它們未被訪問的鄰接點，直至訪問所有與頂點v

有路徑相通的頂點“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”圖的廣度優(yōu)先遍歷采用隊列作為輔助存儲結(jié)構(gòu)運行實例——深入理解操作過程廣度優(yōu)先遍歷序列：v0v1v2v0v1v3v2v4v0v1v2圖的廣度優(yōu)先遍歷廣度優(yōu)先遍歷序列：v0v1v2v0v1v3v2v4v1v2v4v3v4v3運行實例——深入理解操作過程圖的廣度優(yōu)先遍歷廣度優(yōu)先遍歷序列：v0v1v2v0v1v3v2v4v4v3v4v3運行實例——深入理解操作過程圖的廣度優(yōu)先遍歷用偽代碼描述廣度優(yōu)先遍歷的操作定義算法：BFTraverse輸入：頂點的編號v輸出：無1.隊列Q初始化;2.訪問頂點v;修改標(biāo)志visited[v]=1;頂點v入隊列Q;3.while(隊列Q非空)3.1v=隊列Q的隊頭元素出隊;3.2w=頂點v的第一個鄰接點;3.3while(w存在)3.3.1如果w未被訪問，則

訪問頂點w;修改標(biāo)志visited[w]=1;頂點w入隊列Q；3.3.2w=頂點v的下一個鄰接點；圖的廣度優(yōu)先遍歷5-3圖的存儲結(jié)構(gòu)及實現(xiàn)v第五章圖圖的存儲結(jié)構(gòu)圖是否可以采用順序存儲結(jié)構(gòu)？在圖中，任何兩個頂點之間都可能存在關(guān)系（邊）無法通過存儲位置表示這種任意的邏輯關(guān)系圖無法采用順序存儲結(jié)構(gòu)如何存儲圖呢？圖是由頂點和邊組成分別考慮如何存儲頂點如何存儲邊圖的鄰接表存儲及實現(xiàn)圖的鄰接矩陣存儲及實現(xiàn)學(xué)什么？5-3-1圖的鄰接矩陣存儲結(jié)構(gòu)及實現(xiàn)v第五章圖存儲思想edge[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它鄰接矩陣也稱數(shù)組表示法，基本思想是：一維數(shù)組：存儲圖中頂點的信息二維數(shù)組（鄰接矩陣）：存儲圖中各頂點之間的鄰接關(guān)系設(shè)G＝(V,E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：存儲示意圖v0v3v2v1v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3無向圖的鄰接矩陣有什么特點？對稱矩陣如何求頂點v

的度？第v行（或第v列）非零元素的個數(shù)如何判斷頂點i和

j之間是否存在邊？if(edge[i][j]==1)0123v0v3v2v1如何求頂點i的所有鄰接點？掃描第

i

行for(j=0;j<n;j++)if(edge[i][j]==1)

頂點j是頂點i的鄰接點v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v30123存儲示意圖有向圖的鄰接矩陣一定不對稱嗎？頂點間存在方向相反的弧如何求頂點v

的出度？第v行非零元素的個數(shù)v0v3v2v1如何求頂點v

的入度？第v列非零元素的個數(shù)v0v1v2v3vertex=01011010

1

0000

000edge=v0

v1

v2

v3v0v1v2v30123存儲示意圖v0v1v2v3vertex=05

∞

2

508

7

∞

80∞2

7

∞0edge=v0

v1

v2

v3v0v1v2v3v0v3v2v12785網(wǎng)圖的鄰接矩陣可定義為：edge[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他0123存儲示意圖存儲結(jié)構(gòu)定義constintMaxSize=10;template<typenameDataType>classMGraph{public:

MGraph(DataTypea[],intn,inte);

~MGraph();

voidDFTraverse(intv);

voidBFTraverse(intv);private:

DataTypevertex[MaxSize];

intedge[MaxSize][MaxSize];

intvertexNum,edgeNum;};圖的抽象數(shù)據(jù)類型定義？ADTGraphDataModel…Operation

CreateGraph：圖的建立DestroyGraph：圖的銷毀DFTraverse：深度優(yōu)先遍歷圖BFTraverse：廣度優(yōu)先遍歷圖endADTv0v3v2v1v0v1v2v3a=輸入v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3結(jié)果44vertexNumedgeNum圖的建立v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3算法：CreateGraph(a[n],n,e)輸入：頂點的數(shù)據(jù)a[n]，頂點個數(shù)n，邊的個數(shù)e輸出：圖的鄰接矩陣1.存儲圖的頂點個數(shù)和邊的個數(shù)；2.將頂點信息存儲在一維數(shù)組vertex中；3.初始化鄰接矩陣edge；4.依次輸入每條邊并存儲在鄰接矩陣edge中：4.1輸入邊依附的兩個頂點的編號i和j；4.2將edge[i][j]和edge[j][i]的值置為1；44vertexNumedgeNum圖的建立template<typenameDataType>MGraph<DataType>::MGraph(DataTypea[],intn,inte){

inti,j,k;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)//存儲頂點

vertex[i]=a[i];

for(i=0;i<vertexNum;i++)//初始化鄰接矩陣

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

edge[i][j]=0;

for(k=0;k<edgeNum;k++)//依次輸入每一條邊

{

cin>>i>>j;//輸入邊依附的兩個頂點的編號

edge[i][j]=1;edge[j][i]=1;//置有邊標(biāo)志

}}圖的建立深度優(yōu)先遍歷v0v1v2v30101101101001100v0

v1

v2

v3v0v1v2v3算法：DFTraverse輸入：頂點的編號v輸出：圖的深度優(yōu)先遍歷序列1.訪問頂點v;修改標(biāo)志visited[v]=1;2.j=頂點v的第一個鄰接點；3.while(j存在)3.1if(j未被訪問)從頂點j出發(fā)遞歸執(zhí)行該算法;3.2j=頂點v的下一個鄰接點;0123template<typenameDataType>voidMGraph<DataType>::DFTraverse(intv){

cout<<vertex[v];visited[v]=1;

for(intj=0;j<vertexNum;j++)

if(edge[v][j]==1&&visited[j]==0)

DFTraverse(j);}算法：BFTraverse輸入：頂點的編號v輸出：圖的廣度優(yōu)先遍歷序列1.隊列Q初始化;2.訪問頂點v;修改標(biāo)志visited[v]=1;頂點v入隊列Q;3.while(隊列Q非空)3.1i=隊列Q的隊頭元素出隊;3.2j=頂點v的第一個鄰接點;3.3while(j存在)3.3.1如果j未被訪問，則

訪問頂點j;修改標(biāo)志visited[j]=1;頂點j入隊列Q；3.3.2j=頂點i的下一個鄰接點；v0v1v3v2v4廣度優(yōu)先遍歷template<typenameDataType>voidMGraph<DataType>::BFTraverse(intv){

intw,j,Q[MaxSize];

//采用順序隊列

intfront=-1,rear=-1;

//初始化隊列

cout<<vertex[v];visited[v]=1;Q[++rear]=v;

//被訪問頂點入隊

while(front!=rear)

//當(dāng)隊列非空時

{

w=Q[++front];

//將隊頭元素出隊并送到v中

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

if(edge[w][j]==1&&visited[j]==0){

cout<<vertex[j];visited[j]=1;Q[++rear]=j;

}

}}

廣度優(yōu)先遍歷5-3-2圖的鄰接表存儲結(jié)構(gòu)v第五章圖存儲思想鄰接矩陣存儲結(jié)構(gòu)的空間復(fù)雜度是多少？O(n2)如果采用鄰接矩陣存儲稀疏圖，會出現(xiàn)什么情況？稀疏矩陣ACBGFEDH12∧345∧7∧68∧∧∧∧∧

01234567

ABCDEFGH

樹的孩子表示法？鄰接表存儲的基本思想是：v0v1v2v3邊表（鄰接表）：頂點v

的所有鄰接點鏈成的單鏈表頂點表：所有邊表的頭指針和存儲頂點信息的一維數(shù)組13∧03∧

0123

v0

v1

v2

v3

3∧102∧adjvexnextvertexfirstEdge存儲思想存儲結(jié)構(gòu)定義v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧structEdgeNode{

intadjvex;EdgeNode*next;};template<typenameDataType>structVertexNode{

DataTypevertex;

EdgeNode*firstEdge;};vertexfirstEdgeadjvexnext基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧邊表中的結(jié)點表示什么？對應(yīng)圖中的一條邊設(shè)圖有n個頂點e條邊，鄰接表的空間復(fù)雜度是多少？O(n+e)vertexadjvexnextfirstEdgev0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何求頂點v的度？頂點v的邊表中結(jié)點的個數(shù)p=adjList[v].firstEdge;count=0;while(p!=nullptr){count++;p=p->next;}vertexadjvexnextfirstEdge基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何求頂點v

的所有鄰接點?頂點i

的邊表中的所有結(jié)點p=adjList[v].firstEdge;while(p!=nullptr){j=p->adjvex;//j是v的鄰接點p=p->next;}vertexadjvexnextfirstEdge基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何判斷頂點i

和頂點j之間是否存在邊?測試頂點i

的邊表中是否存在數(shù)據(jù)域為j

的結(jié)點vertexadjvexnextfirstEdge基本操作13∧

0123

v0

v1

v2

v3

0∧02∧v0v1v2v3∧如何求頂點v的出度？頂點v的出邊表中結(jié)點的個數(shù)如何求頂點v的入度？所有出邊表中數(shù)據(jù)域為v

的結(jié)點個數(shù)vertexadjvexnextfirstEdge基本操作存儲帶權(quán)圖鄰接表如何存儲帶權(quán)圖？權(quán)值存儲在邊表中v0v1v2v32785

0123

v0

v1

v2

v3

1235∧0

237∧38∧0

51

728∧adjvexweightnextvertexfirstEdgeconstintMaxSize=10;template<typenameDataType>classALGraph{public:

ALGraph(DataTypea[],intn,inte);

~ALGraph();

voidDFTraverse(intv);

voidBFTraverse(intv);private:

VertexNode<DataType>

adjList[MaxSize];

intvertexNum,edgeNum;};ADTGraphDataModel…Operation

CreateGraph：圖的建立DestroyGraph：圖的銷毀DFTraverse：深度優(yōu)先遍歷圖BFTraverse：廣度優(yōu)先遍歷圖endADT存儲結(jié)構(gòu)定義圖的抽象數(shù)據(jù)類型定義？圖的建立v0v1v2v3a=輸入v0v1v2v3結(jié)果13∧

0123

v0

v1

v2

v3

0∧02∧∧44vertexNumedgeNum算法：CreateGraph(a[n],n,e)輸入：頂點的數(shù)據(jù)信息a[n]，頂點個數(shù)n，邊的個數(shù)e輸出：圖的鄰接表1.存儲圖的頂點個數(shù)和邊的個數(shù)；2.將頂點信息存儲在頂點表中，將該頂點邊表的頭指針初始化為nullptr；3.依次輸入邊的信息并存儲在邊表中：3.1輸入邊所依附的兩個頂點的編號i和j；3.2生成邊表結(jié)點s，其鄰接點的編號為j； 3.3將結(jié)點s插入到第i個邊表的表頭；13∧

0123

v0

v1

v2

v3

0∧02∧∧圖的建立

v0

v1

v2

v3

∧∧∧∧template<typenameDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){

inti,j,k;

EdgeNode*s=nullptr;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)//初始化頂點表

{

adjList[i].vertex=a[i];

adjList[i].firstEdge=nullptr;}}圖的建立for(k=0;k<edgeNum;k++)//依次輸入每一條邊{cin>>i>>j;//輸入邊所依附的兩個頂點的編號s=newEdgeNode;s->adjvex=j;//生成一個邊表結(jié)點ss->next=adjList[i].firstEdge;//將結(jié)點s插入到第i個邊表的表頭adjList[i].firstEdge=s;}3∧

0

v0

1stemplate<typenameDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){

inti,j,k;

EdgeNode*s=nullptr;

vertexNum=n;edgeNum=e;

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

{

adjList[i].vertex=a[i];

adjList[i].firstEdge=nullptr;}}圖的建立在鄰接表存儲中，須釋放所有在程序運行過程中申請的的邊表結(jié)點template<typenameDataType>ALGraph<DataType>::~ALGraph(){EdgeNode*p=nullptr,*q=nullptr;for(inti=0;i<vertexNum;i++){p=q=adjList[i].firstEdge;while(p!=nullptr){p=p->next;deleteq;q=p;}}}13∧

0123

v0

v1

v2

v3

0∧02∧∧圖的銷毀深度優(yōu)先遍歷算法：DFTraverse輸入：頂點的編號v輸出：無1.訪問頂點v;修改標(biāo)志visited[v]=1;2.j=頂點v的第一個鄰接點；3.while(j存在)3.1if(j未被訪問)從頂點j出發(fā)遞歸執(zhí)行該算法;3.2j=頂點v的下一個鄰接點;13∧

0123

v0

v1

v2

v3

0∧02∧∧template<typenameDataType>voidALGraph<DataType>::DFTraverse(intv){

intj;

EdgeNode*p=nullptr;

cout<<adjList[v].vertex;visited[v]=1;

p=adjList[v].firstEdge;

while(p!=nullptr)

{

j=p->adjvex;

if(visited[j]==0)DFTraverse(j);

p=p->next;

}}13∧

0123

v0

v1

v2

v3

0∧02∧∧深度優(yōu)先遍歷算法：BFTraverse輸入：頂點的編號v輸出：無1.隊列Q初始化;2.訪問頂點v;修改標(biāo)志visited[v]=1;頂點v入隊列Q;3.while(隊列Q非空)3.1i=隊列Q的隊頭元素出隊;3.2j=頂點v的第一個鄰接點;3.3while(j存在)3.3.1如果j未被訪問，則

訪問頂點j;修改標(biāo)志visited[j]=1;頂點j入隊列Q；3.3.2j=頂點i的下一個鄰接點；廣度優(yōu)先遍歷template<typenameDataType>voidALGraph<DataType>::BFTraverse(intv){

intw,j,Q[MaxSize];intfront=-1,rear=-1;

EdgeNode*p=nullptr;

cout<<adjList[v].vertex;visited[v]=1;Q[++rear]=v;

while(front!=rear)

{

w=Q[++front];

p=adjList[w].firstEdge;

while(p!=nullptr)

{

j=p->adjvex;

if(visited[j]==0){

cout<<adjList[j].vertex;visited[j]=1;Q[++rear]=j;

}

p=p->next;

}}13∧

0123

v0

v1

v2

v3

0∧02∧∧廣度優(yōu)先遍歷5-4最小生成樹v第五章圖最小生成樹的定義v0v1v2v4v3生成樹：連通圖的生成樹是包含全部頂點的一個極小連通子圖含有n-1條邊多——構(gòu)成回路少——不連通v0v1v2v4v3v0v1v2v4v3v3v2v1v4v0v0v1v2v4v3可以指定根結(jié)點生成樹可能不唯一生成樹的代價：在無向連通網(wǎng)中，生成樹上各邊的權(quán)值之和最小生成樹：在無向連通網(wǎng)中，代價最小的生成樹v0v1v2v4v32785636v0v1v2v4v3275生成樹的代價：20v0v1v2v4v32563生成樹的代價：16最小生成樹的定義在n個城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，每兩個城市之間架設(shè)通信線路的造價是不一樣的，如何設(shè)計才能使得總造價最小？Prim算法Kruskal算法學(xué)什么？5-4-1Prim算法v第五章圖基本思想算法：Prim輸入：無向連通網(wǎng)G=(V，E)輸出：最小生成樹T=(U，TE)1.初始化：U={v}；TE={}；2.重復(fù)下述操作直到U=V：2.1在E中尋找最短邊(i，j)，且滿足i∈U，j∈V-U；2.2U=U+{j}；2.3TE=TE+{(i，j)}；關(guān)鍵：如何找到連接U和V-U的最短邊？uvv'頂點集U頂點集V-Uminv0v1v2v4v3v5341219262525463817關(guān)鍵：是如何找到連接U和V-U的最短邊？

U：涂色

V-U：尚未涂色方法：一個頂點涂色、另一個頂點尚未涂色的最短邊v0v1v2v4v3v51219262517基本思想v0運行實例初始化：U={v0}V-U={v1,v2,v3,v4,v5}cost={(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}v0v519第一次迭代：U={v0

,v5}V-U={v1,v2,v3,v4}cost={(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26}v0v1v2v4v3v5341219262525463817v0v519v225第二次迭代：U={v0

,v5,v2}V-U={v1,v3,v4}cost={(v0,v1)34,(v2,v3)17,(v5,v4)26}v0v2v51925v317第三次迭代：U={v0

,v5,

v2,v3}V-U={v1,v4}cost={(v0,v1)34,(v5,v4)26}第一次迭代：cost={(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26}運行實例v0v1v2v4v3v5341219262525463817v426v0v2v3v5192517第四次迭代：U={v0

,v5,

v2,v3,v4}V-U={v1}cost={(v4,v1)12}v112v0v2v4v3v519262517第三次迭代：cost={(v0,v1)34,(v5,v4)26運行實例v0v1v2v4v3v5341219262525463817存儲結(jié)構(gòu)需要不斷讀取任意兩個頂點之間邊的權(quán)值圖采用什么存儲結(jié)構(gòu)？圖采用鄰接矩陣存儲如何存儲候選最短邊集（連接U和V-U的候選最短邊）？數(shù)組adjvex[n]：表示候選最短邊的鄰接點數(shù)組lowcost[n]：表示候選最短邊的權(quán)值adjvex[i]=jlowcost[i]=w例如：{(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}含義是：候選最短邊（i,j）的權(quán)值為w，其中i∈V-U，j∈U初始時，lowcost[v]=0，表示將頂點v加入集合U中；

adjvex[i]=v，lowcost[i]=edge[v][i]（0≤i

≤n-1）例如：{(v0,v0)0,(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}000000adjvex[n]=012345

03446∞

∞19lowcost[n]=存儲結(jié)構(gòu)每一次迭代，設(shè)數(shù)組lowcost[n]中的最小權(quán)值是lowcost[j]，則

令lowcost[j]=0，表示將頂點j加入集合U中；例如：{(v0,v0)0,(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}更新：{(v0,v0)0,(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26,(v0,v5)0}lowcost[i]=min{lowcost[i],edge[i][j]}adjvex[i]=j（如果edge[i][j]<lowcost[i]）（0≤i≤n-1）由于頂點j從集合V-U進入集合U，候選最短邊集發(fā)生變化，需要更新：012345

000000adjvex[n]=

03446∞

∞19lowcost[n]=

005

550adjvex[n]=

034252526

0lowcost[n]=012345存儲結(jié)構(gòu)v0v1v2v4v3v5341219262525463817v0000340460∞0∞019

Vv0

v1

v2

v3

v4

v5U輸出

adjvexlowcost下標(biāo)012345voidPrim(intv)/*假設(shè)從頂點v出發(fā)*/{inti,j,k,adjvex[MaxSize],lowcost[MaxSize];

lowcost[v]=0;/*將頂點v加入集合U*/for(i=0;i<vertexNum;i++)/*初始化輔助數(shù)組shortEdge*/{lowcost[i]=edge[v][i];adjvex[i]=v;}算法實現(xiàn)v0000340460∞0∞019(v0,v5)19

Vv0

v1

v2

v3

v4

v5U輸出

adjvexlowcostadjvexlowcost下標(biāo)012345v0,v503452552552600v0v1v2v4v3v5341219262525463817for(k=1;k<vertexNum;i++)/*迭代n-1次*/{j=MinEdge(lowcost,vertexNum)/*尋找最短邊的鄰接點j*/cout<<j<<adjvex[j]<<lowcost[j];lowcost[j]=0;

}for(i=0;i<vertexNum;i++)/*調(diào)整數(shù)組shortEdge[n]*/if(edge[i][j]<lowcost[i]){lowcost[i]=edge[i][j];adjvex[i]=j;}算法實現(xiàn)v0v1v2v4v3v5341219262525463817v0,v5,v2,v3,v4,v1(v4,v1)12v0000340460∞0∞019(v0,v5)19

Vv0

v1

v2

v3

v4

v5U輸出

adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcost下標(biāo)012345v0,v503452552552600(v5,v2)25v0,v5,v203450217526(v2,v3)17v0,v5,v2,v303420526(v5,v4)26v0,v5,v2,v3,v44125040v0v1v2v4v3v51219262517驗證算法voidPrim(intv){inti,j,k,adjvex[MaxSize],lowcost[MaxSize];}O(n)O(n)O(n)時間復(fù)雜度？O(n2)for(i=0;i<vertexNum;i++)if(edge[i][j]<lowcost[i]){lowcost[i]=edge[i][j];adjvex[i]=j;}for(i=0;i<vertexNum;i++){lowcost[i]=edge[v][i];adjvex[i]=v;}lowcost[v]=0;for(k=1;k<vertexNum;i++){j=MinEdge(lowcost,vertexNum)cout<<j<<adjvex[j]<<lowcost[j];lowcost[j]=0;

}算法實現(xiàn)5-4-2Kruskal算法v第五章圖基本思想找到連接U和V-U的最短邊Prim算法的關(guān)鍵是什么？最短邊頂點分別位于U和V-U中Prim算法：先構(gòu)造滿足條件的候選最短邊集，再查找最短邊Kruskal算法：先查找最短邊，再判斷是否滿足條件算法：Kruskal算法輸入：無向連通網(wǎng)G=(V,E)輸出：最小生成樹T=(U,TE)1.初始化：U=V；TE={}；

2.重復(fù)下述操作直到所有頂點位于一個連通分量：2.1在E中選取最短邊(u,v);2.2如果頂點

u、v

位于兩個連通分量，則2.2.1TE=TE+{(u,v)}；2.2.2將這兩個連通分量合成一個連通分量；2.3在

E

中標(biāo)記邊(u,v)，使得(u,v)不參加后續(xù)最短邊的選?。换舅枷腙P(guān)鍵：如何判斷、合并頂點位于的連通分量？v0v1v2v4v3v5341219262525463817初始化：連通分量＝{v0},{v1},{v2},{v3},{v4},{v5}第一次迭代：連通分量＝{v0},{v1,v4},{v2},{v3},{v5}第二次迭代：連通分量＝{v0},{v1,v4},{v2,v3},{v5}第三次迭代：連通分量＝{v0,v5},{v1,v4},{v2,v3}第四次迭代：連通分量＝{v0,v2,v3,v5},{v1,v4}v0v1v2v4v3v51217252619第五次迭代：連通分量＝{v0,v2,v3,v5,v1,v4}運行實例圖采用什么存儲結(jié)構(gòu)呢？邊集數(shù)組表示法存儲結(jié)構(gòu)算法：Kruskal算法輸入：無向連通網(wǎng)G=(V,E)輸出：最小生成樹T=(U,TE)1.初始化：U=V；TE={}；

2.重復(fù)下述操作直到所有頂點位于一個連通分量：2.1在

E中選取最短邊(u,v);2.2如果頂點

u、v

位于兩個連通分量，則2.2.1TE=TE+{(u,v