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

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