5-2圖的邏輯結(jié)構(gòu)v第五章圖圖的定義和基本術(shù)語圖的抽象數(shù)據(jù)類型定義學什么？歐拉1707年出生在瑞士，19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線、多面體的歐拉定理、立體解析幾何的歐拉變換公式、四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)、微分方程的歐拉方程、數(shù)論的歐拉常數(shù)、變分學的歐拉方程、復變函數(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有向邊（?。罕硎緸?lt;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-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簡單路徑：序列中頂點不重復出現(xiàn)的路徑簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復出現(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ù)類型定義圖是一種與具體應用密切相關(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è)訪問標志數(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）重復上述兩步，直至訪問所有和v

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

出發(fā)進行深度優(yōu)先遍歷的基本思想是：是一個遞歸的過程算法：DFTraverse輸入：頂點的編號v輸出：無1.訪問頂點v;修改標志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;修改標志visited[v]=1;頂點v入隊列Q;3.