《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課件-6(圖).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課件-6(圖).ppt（10頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、圖的定義和基本術(shù)語(yǔ) 2、圖的存儲(chǔ)結(jié)構(gòu) 3、圖的遍歷,,,,,圖,1、圖的定義和基本術(shù)語(yǔ),定義,無(wú)向圖,有向圖,圖：是由頂點(diǎn)集合和頂點(diǎn)間關(guān)系組成，記作 G=（V，R）。,V為頂點(diǎn)集合，V={ v1，v2，…，vn }。 R是兩個(gè)頂點(diǎn)之間的關(guān)系的集合。,無(wú)向圖：當(dāng)圖中頂點(diǎn)之間關(guān)系為無(wú)序時(shí)，稱(chēng)為無(wú)向圖。,有向圖：當(dāng)圖中頂點(diǎn)之間關(guān)系為有序時(shí)，稱(chēng)為有向圖。,圖中無(wú)序?qū)?Vi,Vj)=(Vj,Vi)，稱(chēng)為邊。無(wú)向圖記作G（V，E）。,V=（v1，v2，v3，v4，v5）,E= { (v1,v2)，(v1,v3)，(v1,v4)，(v2,v3)，(v3,v5) },對(duì)左圖：,,V=（v1，v2，v3，v4）,E= { ，，， },對(duì)右圖：,,圖中有序?qū)ΨQ(chēng)為弧，其中Vi為弧尾，Vj為弧頭。此時(shí) ≠ 。有向圖記作G（V，A）。,1、圖的定義和基本術(shù)語(yǔ),路徑：在圖中，從頂點(diǎn)Vp到頂點(diǎn)Vq的通路，它由頂點(diǎn)序列（Vp，Vi1，Vi2, … ,Vik,Vq）來(lái)表示，其中相鄰頂點(diǎn)兩兩構(gòu)成一條邊或弧。在有向圖中，則稱(chēng)有向路徑。,路徑長(zhǎng)度：路徑上邊或弧的數(shù)目稱(chēng)。網(wǎng)絡(luò)的路徑長(zhǎng)度為路徑上各邊(弧)的權(quán)值之和,簡(jiǎn)單路徑：在頂點(diǎn)序列中除第一個(gè)和最后一個(gè)頂點(diǎn)外，序列中其余頂點(diǎn)各不相同的路徑。,連通圖：在無(wú)向圖中，若從點(diǎn)Vi到Vj存在路徑，則稱(chēng)Vi和Vj是連通的。若頂點(diǎn)集合V中，每對(duì)不同頂點(diǎn)Vi，Vj都連通，則稱(chēng)圖為連通圖。,基本術(shù)語(yǔ),度：在無(wú)向圖中，與某頂點(diǎn)相連的邊的數(shù)目稱(chēng)為該頂點(diǎn)的度。,入度、出度：在有向圖中，以某頂點(diǎn)為尾的（初始點(diǎn)）的弧的數(shù)目稱(chēng)為該頂點(diǎn)的出度；而以該頂點(diǎn)為頭（終端點(diǎn)）的弧的數(shù)目稱(chēng)為該頂點(diǎn)的入度。,網(wǎng)：若無(wú)向圖中每條邊附一個(gè)對(duì)應(yīng)的數(shù)（權(quán)），則稱(chēng)該圖為網(wǎng)。,有向網(wǎng)：弧上帶權(quán)的有向圖稱(chēng)為有向網(wǎng)。,網(wǎng),有向網(wǎng),2、圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣—關(guān)系(聯(lián))矩陣,是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。對(duì)一個(gè)有n個(gè)頂點(diǎn)的圖，它的鄰接矩陣是具有下列性質(zhì)的n階方陣：,A[i,j]=,,對(duì)于網(wǎng)，,A[i,j]=,,借助于鄰接矩陣，能夠判定任意兩個(gè)頂點(diǎn)之間是否有邊（弧）相連，亦能求得各個(gè)頂點(diǎn)的度。 在無(wú)向圖中，頂點(diǎn)的度是鄰接矩陣中該點(diǎn)所在行（列）的元素之和；在有向圖中，頂點(diǎn)的出度是該頂點(diǎn)所在行的元素之和，頂點(diǎn)的入度是頂點(diǎn)所在列的元素之和。,,,2、圖的存儲(chǔ)結(jié)構(gòu),對(duì)于用鄰接矩陣表示的圖，在高級(jí)語(yǔ)言（VB）中可以這樣定義：,Enum adj 0 1 End Enum Type Graph dim vexs(1 to n) as datatype //存放頂點(diǎn)信息 dim adjmatrix(1 to n,1 to n) as adj End type,,定義一個(gè)含兩個(gè)成員：0，1的枚舉類(lèi)型,,定義一個(gè)圖,鄰接表,頂點(diǎn)的鄰接表：,對(duì)一個(gè)有n個(gè)頂點(diǎn)的圖，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，這樣就將建立n個(gè)單鏈表，這n個(gè)單鏈表就稱(chēng)為一個(gè)圖的鄰接表。,若以圖中頂點(diǎn)Vi為頭結(jié)點(diǎn)，把所有鄰接于該點(diǎn)的頂點(diǎn)鏈接形成一個(gè)單鏈表，則這個(gè)單鏈表稱(chēng)為頂點(diǎn)Vi的鄰接表。,鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,,2、圖的存儲(chǔ)結(jié)構(gòu),頂點(diǎn)表,,邊表,邊（?。┑慕Y(jié)點(diǎn)的組成：,鄰接點(diǎn)域，存放邊(弧)的終點(diǎn)的序號(hào)；,,數(shù)據(jù)域，存放邊(弧)的相關(guān)信息，如網(wǎng)中邊上的權(quán)值；,鏈域，指向鄰接于頂點(diǎn)Vi的下一條邊(弧)的結(jié)點(diǎn)；,Type edgeptr=^edgenode edgenode=record //邊表結(jié)點(diǎn) adjvex:1 n; //鄰接點(diǎn)域 next:edgeptr //鏈域 end; vexnode=record //頂點(diǎn)表結(jié)點(diǎn) vextex:verttype; //頂點(diǎn)信息 link:edgeptr //鏈域 end; Adjlist=array[1n] of vexnode; //定義含有n個(gè)頂點(diǎn)的圖,2、圖的存儲(chǔ)結(jié)構(gòu),注意：對(duì)于上述兩種存儲(chǔ)方式，鄰接矩陣是唯一的而鄰接表不唯一！,高級(jí)語(yǔ)言中圖的鄰接表可以如下定義（以pascal語(yǔ)言為例）：,為了便于隨即訪問(wèn)任一頂點(diǎn)的鄰接表，將所有鄰接表的頭結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中，圖就用這個(gè)數(shù)組來(lái)表示。,,3、圖的遍歷,深度優(yōu)先搜索遍歷,算法邏輯：從圖的某一個(gè)頂點(diǎn)V0出發(fā)遍歷，首先訪問(wèn)該點(diǎn)，然后選擇V0的一個(gè)尚未訪問(wèn)過(guò)的鄰接點(diǎn)W，從W出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到被訪問(wèn)的頂點(diǎn)其鄰接點(diǎn)均被訪問(wèn)過(guò)為止。這時(shí)需要回溯到該頂點(diǎn)訪問(wèn)之前的頂點(diǎn)，繼續(xù)訪問(wèn)其尚未訪問(wèn)過(guò)的鄰接點(diǎn)，這樣不斷回溯直到起始點(diǎn)V0，使所有V0的鄰接點(diǎn)都被訪問(wèn)到為止。,,,,,,,,,,,,,,,,,DFS（A，i） 1. visit[i] //訪問(wèn)頂點(diǎn)Vi 2. visited[i] ←true; //置頂點(diǎn)被訪問(wèn)標(biāo)志 3. For j=1 to n 4. If (A[i,j]=1) and (not visited[j]) then 5. DFS(A，j) 6. end(j) 7. return,采用鄰接矩陣為圖的存儲(chǔ)結(jié)構(gòu)時(shí)深度優(yōu)先搜索遍歷算法：,遍歷結(jié)果：,3,2,4,9,1,6,5,8,7,深度優(yōu)先遍歷的特點(diǎn)：盡可能先對(duì)縱深方向進(jìn)行搜索。,3、圖的遍歷,廣度優(yōu)先搜索遍歷,算法邏輯：首先訪問(wèn)頂點(diǎn)V0，接著依次訪問(wèn)V0的所有鄰接點(diǎn)V1、V2、…Vk，然后再依次訪問(wèn)與V1、V2、…Vk鄰接的所有未曾訪問(wèn)過(guò)的頂點(diǎn)，依次類(lèi)推，直至所有被訪問(wèn)到的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)過(guò)為止。,對(duì)于圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)，廣度優(yōu)先遍歷的結(jié)果為：,3 2 6 1 4 5 9 7 8,,,,,,,,,廣度優(yōu)先遍歷的特點(diǎn)：盡可能先對(duì)橫向進(jìn)行搜索。,3、圖的遍歷,廣度優(yōu)先搜索遍歷算法流程：,V3,V2,V6,V1,V4,V5,V9,V7,V8,遍歷次序：,由廣度優(yōu)先搜索遍歷的邏輯可見(jiàn)，先訪問(wèn)的頂點(diǎn)其鄰接頂點(diǎn)也先被訪問(wèn)，因此在算法中需引進(jìn)一個(gè)隊(duì)列保存已訪問(wèn)過(guò)的頂點(diǎn)！,