數(shù)據(jù)結(jié)構(gòu)-第七章圖(圖的定義存儲(chǔ)實(shí)現(xiàn)和圖的遍歷)描述.ppt

《數(shù)據(jù)結(jié)構(gòu)-第七章圖(圖的定義存儲(chǔ)實(shí)現(xiàn)和圖的遍歷)描述.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、1、圖的定義和術(shù)語(yǔ)2、圖的存儲(chǔ)結(jié)構(gòu)3、圖的遍歷4、圖的連通性問(wèn)題5、有向無(wú)環(huán)圖及其應(yīng)用6、最短路徑第七章圖7.1.1圖的定義7.1.2圖的基本術(shù)語(yǔ)7.2.1鄰接矩陣表示7.2.2鄰接表表示7.1.1圖的定義圖（Graph）是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，其形式化定義如下：Graph=(V,R)V={x

2、x∈DataObject}R={VR}//數(shù)據(jù)關(guān)系VR={

3、P(x,y)∧(x,y∈V)}DataObject：是一個(gè)集合，該集合中的所有元素具有相同的特性。V：中的數(shù)據(jù)元素通常稱為頂點(diǎn)（Vertex）（圖中的頂點(diǎn)）

4、。VR：是兩個(gè)頂點(diǎn)之間的關(guān)系的集合。P(x,y)：表示x和y之間有特定的關(guān)聯(lián)屬性P。7.1.1圖的定義若∈VR，則表示從頂點(diǎn)x到頂點(diǎn)y的弧(Arc)，稱x為弧尾(Tail)或起始點(diǎn)，稱y為弧頭(Head)，或終端點(diǎn)。此時(shí)圖中的弧是有方向的，此時(shí)的圖稱為有向圖(Digraph)。若∈VR，必有∈VR，即VR是對(duì)稱關(guān)系，這時(shí)以無(wú)序?qū)?x,y)來(lái)代替兩個(gè)有序?qū)?，表示x和y之間的一條邊(Edge)，此時(shí)的圖稱為無(wú)向圖(Undigraph)。7.1.1圖的定義圖的基本操作和其它數(shù)據(jù)結(jié)構(gòu)一樣，也

5、有創(chuàng)建、插入、刪除、查找等。圖的抽象類型定義和基本操作如P156所示。7.1.2圖的基本術(shù)語(yǔ)圖鄰接點(diǎn)路徑和回路度權(quán)與網(wǎng)生成樹(shù)路徑路徑長(zhǎng)度回路或環(huán)簡(jiǎn)單路徑簡(jiǎn)單回路無(wú)向圖有向圖完全圖子圖連通圖7.1.2圖的基本術(shù)語(yǔ)無(wú)向圖：若∈VR，必有∈VR，即VR是對(duì)稱關(guān)系，這時(shí)以無(wú)序?qū)?x,y)來(lái)代替兩個(gè)有序?qū)?，表示x和y之間的一條邊（Edge），此時(shí)的圖稱為無(wú)向圖。ABCDE無(wú)向圖G27.1.2圖的基本術(shù)語(yǔ)若∈VR，則表示從頂點(diǎn)x到頂點(diǎn)y的弧(Arc)，稱x為弧尾(Tail)或起始點(diǎn)，稱y為弧頭(

6、Head)，或終端點(diǎn)（箭頭指向的點(diǎn)）。圖中的邊是有方向的，此時(shí)的圖稱為有向圖(Digraph)。ABCD有向圖G17.1.2圖的基本術(shù)語(yǔ)ABCDABCDE有向圖G1無(wú)向圖G2結(jié)點(diǎn)(頂點(diǎn))有向邊（?。⒒∥?初始結(jié)點(diǎn))、弧頭(終止結(jié)點(diǎn))ABAB有向圖：G1=(V1，E1)V1={A,B,C,D}E1={,,,}結(jié)點(diǎn)(頂點(diǎn))邊(無(wú)向邊)AB無(wú)向圖：G2=(V2，E2)V2={A,B,C,D,E}E2={(A,B),(A,C),(B,D),(B,E）,(C,E),(D,E)}AB7.1.2

7、圖的基本術(shù)語(yǔ)完全圖有向完全圖：有n(n-1)條邊（圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有弧相連）的有向圖為有向完全圖。12347.1.2圖的基本術(shù)語(yǔ)完全圖無(wú)向完全圖：有n(n-1)/2條邊（圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有邊相連）的無(wú)向圖為無(wú)向完全圖（或稱為完全圖）。1234注意：對(duì)于有很少條邊的圖（e

8、BCDEABDEAABCDABCDE無(wú)向圖G2的子圖有向圖G17.1.2圖的基本術(shù)語(yǔ)連通圖：在無(wú)向圖G=(V,{E})中，若從vi到vj有路徑相通，則稱頂點(diǎn)vi與vj是連通的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn)vi、vj∈V，vi,vj都是連通的，則稱該無(wú)向圖G為連通圖。7.1.2圖的基本術(shù)語(yǔ)連通分量：無(wú)向圖中的極大連通子圖稱為該無(wú)向圖的連通分量。ABCDEFGIJLHMKABCDEHMFGIJLK無(wú)向圖G無(wú)向圖G的三個(gè)連通分量7.1.2圖的基本術(shù)語(yǔ)強(qiáng)連通圖：在有向圖G=(V,{A})中，若對(duì)于每對(duì)頂點(diǎn)vi、vj∈V且vi≠vj，

9、從vi到vj和vj到vi都有路徑，則稱該有向圖為強(qiáng)連通圖。7.1.2圖的基本術(shù)語(yǔ)強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。有向圖G有向圖G的兩個(gè)強(qiáng)連通分量ABCDABCD7.1.2圖的基本術(shù)語(yǔ)鄰接點(diǎn)對(duì)于無(wú)向圖G=(V,{E})，如果邊(v,v’)∈E，則稱頂點(diǎn)v,v’互為鄰接點(diǎn)，即v,v’相鄰接。邊（v,v’）依附于頂點(diǎn)v和v’，或者說(shuō)邊（v,v’）與頂點(diǎn)v和v’相關(guān)聯(lián)。對(duì)于有向圖G=(V,{A})而言，若弧∈A，則稱頂點(diǎn)v鄰接到頂點(diǎn)v’，頂點(diǎn)v’鄰接自頂點(diǎn)v，或者說(shuō)弧與頂點(diǎn)v,v’

10、相關(guān)聯(lián)。7.1.2圖的基本術(shù)語(yǔ)路徑和回路路徑路徑長(zhǎng)度回路或環(huán)簡(jiǎn)單路徑簡(jiǎn)單回路7.1.2圖的基本術(shù)語(yǔ)路徑無(wú)向圖路徑：無(wú)向圖G=(V,{E})中從頂點(diǎn)v到v’的路徑是一個(gè)頂點(diǎn)序列（v=vi,0,vi,1,vi,2,...,vi,m=v’)，其中(vi,j-1,vi,j)∈E,1≤j≤m。有向圖路徑：如果圖G