




版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、第7章 圖第7章 圖 7.1 圖的定義和術語 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的最小生成樹7.1 圖的定義與術語一、圖的定義1、圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E) 其中:V(G)是頂點的非空有限集 E(G)是邊的有限集合,邊是頂點的無序?qū)蛴行驅(qū)?。圖的分類 有向圖 無向圖37.1 圖的定義與術語2、有向圖有向圖G是由兩個集合V(G)和E(G)組成的。 其中:V(G)是頂點的非空有限集。 E(G)是有向邊(也稱弧)的有限集合,弧是頂點的有序?qū)Γ洖?,v,w是頂點,v為弧尾,w為弧頭。47.1 圖的定義與術語例如: G1 = V1 = A
2、, B, C, D, E E1 = , , , , , , EACBD57.1 圖的定義與術語3、無向圖無向圖G是由兩個集合V(G)和E(G)組成的。 其中:V(G)是頂點的非空有限集。 E(G)是邊的有限集合,邊是頂點的無序?qū)Γ洖?(v,w) 或 (w,v),并且(v,w)=(w,v)。67.1 圖的定義與術語例如: G2 = V2 = v0 ,v1,v2,v3,v4 E2 = (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) V0V4V3V1V277.1 圖的定義與術語例如: G2 = V2 = v0,v1,v2,v3 E2 = ,
3、 , , V0 V1 V2 V3 例245136G1V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , 87.1 圖的定義與術語圖的應用舉例例1、交通圖(公路、鐵路) 頂點:地點邊:連接地點的路例2、電路圖 頂點:元件邊:連接元件之間的線路例3、通訊線路圖 頂點:地點邊:地點間的連線例4、各種流程圖如產(chǎn)品的生產(chǎn)流程圖。 頂點:工序邊:各道工序之間的順序關系97.1 圖的定義與術語二、圖的基本術語1、鄰接點及關聯(lián)邊 鄰接點:邊的兩個頂點 關聯(lián)邊:若邊e= (v, u), 則稱頂點v、u 關聯(lián)邊e2、頂點的度、入度、出度 頂點V的度 = 與V相關聯(lián)的邊
4、的數(shù)目 在有向圖中: 頂點V的出度 = 以V為起點有向邊數(shù) 頂點V的入度 = 以V為終點有向邊數(shù) 頂點V的度 = V的出度+V的入度 設圖G 的頂點數(shù)為 n,邊數(shù)為 e 圖的所有頂點的度數(shù)和 = 2*e (每條邊對圖的所有頂點的度數(shù)和“貢獻”2度) V0 V4 V3 V1 V2eV0V1V2V3107.1 圖的定義與術語3、路徑、回路 無向圖 G =(V,E)中的頂點序列v1, v2, , vk,若 (vi, vi+1)E ( i=1, 2, , k-1),v=v1, u=vk,則稱該序列是從頂點v到頂點u的路徑;若v=u,則稱該序列為回路。無向圖G1 V0 V4 V3 V1 V2路徑:V0,
5、 V1, V2, V3回路:V0, V1, V2, V3, V0 117.1 圖的定義與術語3、路徑、回路 有向圖 D =(V,E)中的頂點序列 v1, v2, , vk,若 E (i=1, 2, , k-1),v=v1,u=vk,則稱該序列是從頂點v到頂點u的路徑;若v=u,則稱該序列為回路。有向圖G2V0V1V2V3路徑:V0, V2, V3回路:V0, V2, V3, V0 127.1 圖的定義與術語4、連通圖(強連通圖) 在無(有)向圖 G= 中,若對任何兩個頂點 v、u 都存在從 v 到 u 的路徑,則稱G是連通圖(強連通圖) 非連通圖 連通圖 強連通圖 非強連通圖 V0 V1 V2
6、 V3 V0 V2 V3 V1 V5 V4 V0 V4 V3 V1 V2 V0 V1 V2 V3137.1 圖的定義與術語5、子圖 設有兩個圖 G=(V,E),G1=(V1,E1),若V1 V,E1 E,而且E1關聯(lián)的頂點都在 V1 中,則稱 G1 是 G 的子圖;(b)、(c) 都是 (a) 的子圖(d) V4 V1 V2(c) V0 V4 V3 V1 V2(a) V0 V4 V3 V1 V2(b) V0 V4 V3 V1 V2147.1 圖的定義與術語6、連通分量(強連通分量):無(有)向圖的極大(強)連通子圖。極大(強)連通子圖:該子圖是(強)連通子圖,若再將G的任何不在該子圖中的頂點加
7、入,子圖就不再(強)連通。非連通圖 V0 V2 V3 V1 V5 V4連通分量157.1 圖的定義與術語強連通分量 V0 V1 V2 V3非連通圖 V0 V2 V3 V1167.1 圖的定義與術語7、生成樹 包含無向圖 G 所有頂點的極小連通子圖稱為G生成樹。 極小連通子圖意思是:該子圖是G的連通子圖,在該子圖中刪除任何一條邊,子圖不再連通。G1的生成樹 V0 V4 V3 V1 V2章連通圖G1 V0 V4 V3 V1 V2 連通 所有頂點 無回路17 V0 V1 V2 V37.2 圖的存儲結(jié)構(gòu)一、數(shù)組表示法(鄰接矩陣表示)鄰接矩陣:G的鄰接矩陣是滿足如下條件的n階矩陣:Aij=1 若(vi,
8、vj)E 或 E0 否則0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0在數(shù)組表示法中,用鄰接矩陣表示頂點間的關系 V0 V4 V3 V1 V20 1 1 00 0 0 00 0 0 11 0 0 0187.2 圖的存儲結(jié)構(gòu)二、鄰接表:圖的鏈式存儲結(jié)構(gòu)1、無向圖的鄰接表 頂點:通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中; 關聯(lián)同一頂點的邊:用線性鏈表存儲。 V0 V4 V3 V1 V2 0 1 2 3 4m-1V0V1V2V3V413212013420419typedef struct tnode /表頭結(jié)點 int vexdata; ArcNode *
9、 firstarc; VNode, AdjList MAX_VERTEX_NUM ;7.2 圖的存儲結(jié)構(gòu)typedef struct ArcNode/鏈表結(jié)點 int adjvex; struct ArcNode *next; ArcNode;adjvex nextvexdata firstarctypedef struct/圖 AdjList vertices; int vexnum, arcnum; / 頂點數(shù)和弧數(shù)int kind; / 圖的種類ALGraph;207.2 圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點 1)在G鄰接表中,同一條邊對應兩個結(jié)點; 2)頂點v的度:等于v對應線性鏈表的長度
10、; 3)判定兩頂點v ,u是否鄰接:要看v對應線性鏈表中有無對應的結(jié)點。 4)在G中增減邊:要在兩個單鏈表插入、刪除結(jié)點; 5)設存儲頂點的一維數(shù)組大小為 m(m圖的頂點數(shù)n),圖的邊數(shù)為 e,G占用存儲空間為:m+2*e。G占用存儲空間與G的頂點數(shù)、邊數(shù)均有關;適用于邊稀疏的圖。217.2 圖的存儲結(jié)構(gòu)2、有向圖的鄰接表頂點:用一維數(shù)組存儲(按編號順序)以同一頂點為起點的弧:用線性鏈表存儲0123v0v2v3v1vexdatafirstarc 2 1 3 0adjvexnext類似于無向圖的鄰接表,所不同的是:以同一頂點為起點的?。河镁€性鏈表存儲。V0V1V2V3227.2 圖的存儲結(jié)構(gòu)3、
11、有向圖的逆鄰接表頂點:用一維數(shù)組存儲(按編號順序)以同一頂點為終點的弧:用線性鏈表存儲。0123v0v2v3v1vexdatafirstarc 3 0 0 2類似于有向圖的鄰接表,所不同的是:以同一頂點為終點?。河镁€性鏈表存儲V0V1V2V3章237.3 圖的遍歷連通圖的深度遍歷(DFS)從圖中某頂點v出發(fā): 1)訪問頂點v; 2)對v的每個未被訪問的鄰接點wj,從wj出發(fā),繼續(xù)對圖進行深度優(yōu)先遍歷。深度遍歷: V1,V2,V4,V5,V8,V3,V6,V7 例 V1 V8 V7 V6 V5 V4 V3 V2V1V2V4V3V8V7V6 V5深度遍歷: V1,V3,V6,V7,V2,V5,V8
12、,V4247.3 圖的遍歷圖的深度遍歷(DFS)Vw1SG1SG2SG3w2w3w2 W1、W2和W3 均為 V 的鄰接點,SG1、SG2 和 SG3 分別為含頂點W1、W2和W3 的子圖。訪問頂點 V :for (W1、W2、W3 ) 若該鄰接點W未被訪問, 則從它出發(fā)進行深度優(yōu)先搜索遍歷。257.3 圖的遍歷圖的深度遍歷(DFS)Vw1SG1SG2SG3w2w3w2從圖解可見:1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;解決的辦法是:為每個頂點設立一個 “訪問標志 visitedw”。2. 如何判別V的鄰接點是否被訪問?267.3 圖的遍歷Boolean visitedMAX;
13、 / 訪問標志數(shù)組Status (*VisitFunc)(int v); / 訪問函數(shù)void DFS ( Graph G, int v) / 從頂點v出發(fā),深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for ( w=FirstAdjVex(G, v);w=0; w=NextAdjVex(G,v,w) ) if ( !visitedw ) DFS(G, w); / 對v的尚未訪問的鄰接頂點w / 遞歸調(diào)用DFS / DFS277.3 圖的遍歷非連通圖的深度優(yōu)先搜索遍歷 首先將圖中每個頂點的訪問標志設為 FALSE,之后搜索圖中每個頂點,如果未被訪問
14、,則以該頂點為起始點,進行深度優(yōu)先搜索遍歷,否則繼續(xù)檢查下一頂點。287.3 圖的遍歷void DFSTraverse ( Graph G, Status (*Visit) (int v) / 對圖 G 作深度優(yōu)先遍歷。 VisitFunc = Visit; for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 訪問標志數(shù)組初始化 for ( v=0; vG.vexnum; +v ) if (!visitedv) DFS(G, v); / 對尚未訪問的頂點調(diào)用DFS297.3 圖的遍歷例如:abchdekfgF F F F F F F F FTTTTTT
15、TTTachdkfe bgachkfedbg訪問標志:訪問次序: a b c d e f g h k 0 1 2 3 4 5 6 7 8307.3 圖的遍歷圖的深度遍歷(DFS)V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍歷:V1V3 V7 V6 V2 V4 V8 V5317.3 圖的遍歷圖的廣度遍歷(BFS) 從圖中的某個頂點V0出發(fā),并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點,之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點,直至圖中所有和V0有路徑相通的頂點都被
16、訪問到。 若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點,重復上述過程,直至圖中所有頂點都被訪問到為止。327.3 圖的遍歷圖的廣度遍歷(BFS)從圖中某頂點v出發(fā):1) 訪問頂點v2) 訪問v的所有未被訪問的鄰接點w1,w2,wk3) 依次從這些鄰接點出發(fā),訪問它們的所有未被訪問的鄰接點,直到圖中所有訪問過的頂點的鄰接點都被訪問到。V1V8V7V6V5V4V3V2V1 V2 V4 V3 V8 V7 V6 V5V1,V2,V3,V4,V8,V5,V6,V7V1,V3,V2,V6,V7,V4,V5,V8337.3 圖的遍歷void BFSTraverse ( Graph G,
17、 Status (*Visit) (int v) ) for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 初始化訪問標志 InitQueue(Q); / 置空的輔助隊列Q for ( v=0; v=0; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點w入隊列 / if / while357.3 圖的遍歷圖的廣度遍歷(BFS)(請對照教材第170頁)例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列:10 1 2 3 4 54fr遍歷序列:1 40 1 2 3 4 54 3fr遍歷序列:1 4 3367.3 圖的遍歷圖的廣度遍歷(BFS)例142350 1 2 3 4 54 3 2fr遍歷序列:1 4 3 20 1 2 3 4 5 3 2fr遍歷序
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 蘇州市重點中學2024-2025學年高三第一次聯(lián)考歷史試題理試題含解析
- 唐山工業(yè)職業(yè)技術學院《環(huán)境生態(tài)學》2023-2024學年第二學期期末試卷
- 贛南師范大學科技學院《陳設藝術品設計》2023-2024學年第一學期期末試卷
- 寧夏銀川市金鳳區(qū)六盤山高級中學2025屆高三第二次(4月)月考數(shù)學試題試卷含解析
- 遼寧石化職業(yè)技術學院《工廠化育苗原理與技術》2023-2024學年第二學期期末試卷
- 棗莊職業(yè)學院《人力資源專業(yè)英語》2023-2024學年第二學期期末試卷
- 宿遷職業(yè)技術學院《病理學(含病理生理學)》2023-2024學年第二學期期末試卷
- 河南省安陽市滑縣2025屆下學期高三四月考歷史試題試卷含解析
- 西安交通工程學院《乒乓球Ⅳ》2023-2024學年第二學期期末試卷
- 山西電力職業(yè)技術學院《系統(tǒng)架構(gòu)》2023-2024學年第二學期期末試卷
- 光伏補貼申請流程
- 小數(shù)與單位換算(說課稿)-2023-2024學年四年級下冊數(shù)學人教版
- 《張愛玲傾城之戀》課件
- 實驗診斷學練習題庫(附參考答案)
- 無錫網(wǎng)格員考試題庫
- 第9課 改變世界的工業(yè)革命
- 《供應商選擇與評估》課件
- 新版申請銀行減免利息的申請書
- QC課題提高金剛砂地面施工一次合格率
- 保潔服務質(zhì)量保障及措施
- 《電子銀行安全評估過程實施指南》征求意見稿
評論
0/150
提交評論