1、圖的基本術(shù)語及遍歷,圖的基本術(shù)語及遍歷,教學(xué)目的 1 了解圖的基本概念 2 掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)及深度優(yōu)先搜索和寬度優(yōu)先搜索算法 教學(xué)內(nèi)容 一 圖的基本術(shù)語 二 圖的存儲(chǔ)結(jié)構(gòu) 三 深度優(yōu)先搜索 四 寬度優(yōu)先搜索,一、圖的基本術(shù)語 1、圖的分類 2、圖的屬性 3、網(wǎng),圖的基本術(shù)語及遍歷,圖的基本術(shù)語圖的分類 圖: 圖G由兩個(gè)集合V（G）和E（G）組成，記作G=（ V，E） 其中V(G)是頂點(diǎn)的非空有窮集合 E(G)是邊的有窮集合，而邊是頂點(diǎn)的無序?qū)蛴行驅(qū)Α?圖的基本術(shù)語及遍歷,無向圖: 在圖中，若邊是頂點(diǎn)的無序?qū)?，則稱G為無向圖。 有向圖：若邊是頂點(diǎn)的有序?qū)?，則稱G為有向圖。,圖的基本術(shù)語及遍歷,

2、圖的基本術(shù)語圖的分類 完全圖：在n個(gè)頂點(diǎn)的無向圖G中，若每 一頂點(diǎn)與其余n 一 1個(gè)頂點(diǎn)都有 邊，則稱G為完全圖。,圖的基本術(shù)語及遍歷,有向完全圖：在n個(gè)頂點(diǎn)的有向圖中，若每一個(gè)頂點(diǎn)與其余n一1個(gè)頂點(diǎn)都 有弧存在，則稱G為有向完全圖，具有n (n-1)條弧。,圖的基本術(shù)語及遍歷,子圖: 假設(shè)有兩個(gè)圖G和G,且滿足： 且 則稱G為G的子圖。,圖的基本術(shù)語及遍歷,前三個(gè)圖都是最后一個(gè)的子圖。,圖的基本術(shù)語圖的屬性 無向圖的度: 在無向圖中， 若（v1，v2） E（G）， 稱 v1，v2 為鄰接的，或稱邊（v1，v2 ）依附與頂點(diǎn)v1和v2。 依附于某頂點(diǎn)的邊數(shù)叫作該點(diǎn)的度.,圖的基本術(shù)語及遍歷,度

3、是2,有向圖的度: 在有向圖中，以某頂點(diǎn)為尾的弧數(shù)叫該點(diǎn)的出度；以某頂點(diǎn)為頭的弧數(shù)叫該點(diǎn)的入度。 出度和入度的和是該點(diǎn)的度。,圖的基本術(shù)語及遍歷,度為2,出度1,路徑：在無向圖G中從頂點(diǎn)vp到頂點(diǎn)vq的路徑是一個(gè)頂點(diǎn)序列（vp,vi1,vi2,.，vin,vq），其中（vp, vi1）（vi1, vi2）,（vin, vq）是E（G）中的邊。 路徑長度：稱路徑上邊的數(shù)目為路徑長度。,圖的基本術(shù)語及遍歷,2到4的路徑為2-3-4；長度為2,圖的基本術(shù)語圖的屬性 連通圖: 在無向圖G中，若vi到vj有一條路徑存在，則稱vi到vj是連通的。若對(duì)于V（G）中每對(duì)頂點(diǎn)都連通，則稱G為連通圖。 連通分量：

4、在無向圖中，極大連通子圖稱為連通分量。,圖的基本術(shù)語及遍歷,連通圖,圖的基本術(shù)語圖的屬性 強(qiáng)連通圖： 在有向圖G中，若對(duì)于V（G）中每一對(duì)不同的頂點(diǎn)都存在一條從vi到vj和vj 到vi的路徑，則稱G是強(qiáng)連通圖。 強(qiáng)連通分量： 有向圖中的極大強(qiáng)連通子圖是它的強(qiáng)連通分量。,圖的基本術(shù)語及遍歷,若加上這條線就成強(qiáng)連通圖了,圖的基本術(shù)語圖的屬性 網(wǎng)：在圖G中，若圖的邊帶有權(quán)值，比如圖的邊上有表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或是花費(fèi)，則稱G為網(wǎng)。,圖的基本術(shù)語及遍歷,二、圖的存儲(chǔ)結(jié)構(gòu) 1、鄰接矩陣 2、鄰接表,圖的基本術(shù)語及遍歷,圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣 設(shè)G=（V，E）是有n個(gè)頂點(diǎn)的圖，G的鄰接矩陣A（i

5、，j）是一個(gè)二維的nn數(shù)組，并具有下列性質(zhì)：,圖的基本術(shù)語及遍歷,圖的鄰接矩陣,圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣 網(wǎng)的鄰接矩陣可定義為：,圖的基本術(shù)語及遍歷,網(wǎng)的鄰接矩陣,圖的存儲(chǔ)結(jié)構(gòu)鄰接表 鄰接表：這種存儲(chǔ)結(jié)構(gòu)是對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表。第i個(gè)單鏈表中的每一個(gè)結(jié)點(diǎn)是依附于頂點(diǎn)vi的邊(對(duì)有向圖是以頂點(diǎn)vi為尾的弧)。,圖的基本術(shù)語及遍歷,該圖鄰接表,逆鄰接表：對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)以vi為頭的弧的單鏈表,圖的基本術(shù)語及遍歷,逆鄰接表,圖的存儲(chǔ)結(jié)構(gòu)鄰接表 另外，有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為十字鏈表：把鄰接表和逆鄰接表揉到一起，建立一個(gè)十字鏈表。 無向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為鄰接多重鏈表。,圖的

6、基本術(shù)語及遍歷,三、深度優(yōu)先搜索 1、遞歸算法 2、非遞歸算法,圖的基本術(shù)語及遍歷,深度優(yōu)先搜索遞歸算法 遞歸算法思想：首先從圖G=(V,E)中某一頂點(diǎn)v0出發(fā)，訪問任意一個(gè)和v0鄰接的頂點(diǎn)w1，再從w1出發(fā)，再訪問和w1鄰接且未被訪問過的任意頂點(diǎn)w2。然后，從w2出發(fā)進(jìn)行如上訪問。重復(fù)這個(gè)過程，直到某一個(gè)頂點(diǎn)的所有鄰接點(diǎn)都被訪問過時(shí)，回退到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)。再從該頂點(diǎn)出發(fā)，重復(fù)上述過程，直到所有頂點(diǎn)都被訪問過為止。 例:,圖的基本術(shù)語及遍歷,圖的基本術(shù)語及遍歷,深度優(yōu)先,2已經(jīng)訪問返回8,所有都訪問完畢了,深度優(yōu)先搜索非遞歸算法 非遞歸算法思想：由訪問vi的鄰接表轉(zhuǎn)到訪問vj的鄰接

7、表時(shí)，vi進(jìn)棧。從棧中依次彈出結(jié)點(diǎn)v0,訪問v0的單鏈表中未被訪問過的的結(jié)點(diǎn)，在訪問過程中并重復(fù)上述的入棧過程 。過程如下頁圖示:,圖的基本術(shù)語及遍歷,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,5的鄰接表空，回退8出棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,非遞歸,圖的基本術(shù)語及遍歷,棧,7的鄰接表空，逐一退棧,四、寬度優(yōu)先搜索 1、寬度優(yōu)先搜索 2、圖的連通分量,圖的基本術(shù)語及遍歷,寬度優(yōu)先搜索算法 思想：設(shè)一先進(jìn)先出的隊(duì)Q，從v結(jié)點(diǎn)出發(fā)，訪問v結(jié)點(diǎn),再訪問v的所有鄰接點(diǎn)，并將所有鄰接點(diǎn)入隊(duì)。隊(duì)頭元素出隊(duì)，設(shè)為a，接著訪問a的所有鄰接點(diǎn)，并將a的所有鄰接點(diǎn)入隊(duì)。隊(duì)頭元素出隊(duì)，重復(fù)上述過程，直到隊(duì)空。圖示過程如下:,圖的基本術(shù)語及遍歷,寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度,圖的基本術(shù)語及遍歷,隊(duì),寬度優(yōu)