東南大學(xué)計算機學(xué)院方效林(參考版)
2025-07-21 00:36本頁面
【正文】 ?再從頂點 v3出發(fā)， … ，如此進行下去，直到所有鄰接頂點都被訪問過為止 ?退回一步到剛被訪問的頂點，看是否有未被訪問的鄰接頂點。 9 圖的存儲表示 ? 鄰接矩陣 ? 一個有 n 個頂點的圖 G = ( V, E )， 圖的鄰接矩陣是一個二維數(shù)組 [n][n] 10 1 2 0 有向圖的鄰接矩陣可能不對稱 2 1 3 0 ??? ??否則若,0),(1]][Ed g e [ Ejiji?????????000101010E d g e???????????0101101001011010E d g e無向圖的鄰接矩陣是對稱的 圖的存儲表示 ? 鄰接矩陣 ? 網(wǎng)絡(luò) (帶權(quán)圖 )的鄰接矩陣 11 ?????????????jiji,jiji,jijiWji若且或若且或若,)(,)(),(]][[0EEE d g e???????????????068053290410E d g e3 2 1 0 8 6 3 9 5 2 1 4 圖的存儲表示 ? 鄰接表 ? 無向圖的鄰接表 12 D B C A 1 2 ? 0 ? 0 3 ? C B D A 1 ? 2 1 3 0 data link dest link dest link dest保存的是鄰接頂點的下標 頂點數(shù)組 鏈接結(jié)點 圖的存儲表示 ? 鄰接表 ? 有向圖的鄰接表和逆鄰接表 13 1 ? 0 2 ? C ? B A 2 1 0 data link dest link B C A 1 ? 0 ? 2 ? C B A 2 1 0 data link dest link dest link 鄰接表 (出邊表 ) 逆鄰接表 (入邊表 ) 圖的存儲表示 ? 網(wǎng)絡(luò) (帶權(quán)圖 )的鄰接表 14 鄰接表 (出邊表 ) C D B A 8 6 3 9 5 2 1 4 C B D A 2 1 3 0 data link cost link 3 0 6 ? 3 2 2 1 1 4 ? 2 dest cost link dest 9 ? 3 5 1 8 ? 2 圖的遍歷 ? 從給定頂點出發(fā)，沿某些邊遍歷圖中所有頂點一次且僅一次 ? 使用輔助數(shù)組 visited[ ]標識頂點是否被訪問過 ? visited[ ]初始為 0 ? 訪問過后標識為 1 15 圖的遍歷 ? 遍歷方式 ? 深度優(yōu)先遍歷 DFS (Depth First Search) ? 廣度優(yōu)先遍歷 BFS (Breadth First Search) 16 圖的遍歷 ? 遍歷方式 ? 深度優(yōu)先遍歷 DFS (Depth First Search) ?從頂點 v1出發(fā)，訪問任一未被訪問的鄰接頂點 v2。 6 圖的基本概念 ? 路徑長度 ? 非帶權(quán)圖的路徑長度是指此路徑上 邊的條數(shù) ? 帶權(quán)圖的路徑長度是指路徑上各 邊的權(quán)之和 ? 簡單路徑 ? 路徑上各頂點 v1,v2,...,vm 均不互相重復(fù) ? 回路 ? 路徑上第一個頂點 v1 與最后一個頂點 vm 重合 7 圖的基本概念 ? 連通圖與連通分量 ? 無向圖中 , 從頂點 v1到頂點 v2有路徑 , 則稱頂點 v1與v2是連通的。則稱頂點序列 (vi vp1 vp2 ... vpm vj)為從頂點 vi 到頂點 vj 的路徑。東南大學(xué)計算機學(xué)院 方效林 本課件借鑒了清華大學(xué)殷人昆老師 和哈爾濱工業(yè)大學(xué)張巖 老師的課件 第七章 圖 本章主要內(nèi)容 ? 圖的基本概念 ? 圖的存儲表示 ? 圖的遍歷與連通性 ? 最小生成樹 ? 最短路徑 2 圖的基本概念 ? 定義 ? 圖是由頂點及頂點之間的關(guān)系集合組成的數(shù)據(jù)結(jié)構(gòu)Graph = ( V, E ) ? V是頂點的有窮非空集， V={x | x∈ 某個對象 } ? E是頂點之間關(guān)系，稱為 邊 (edge)的有窮非窮集，E={(x,y) | x,y∈ V} 3 圖的基本概念 ? 有向圖與無向圖 ? 有向圖中，頂點對 (x,y)是 有序 的 ? 無向圖中，頂點對 (x,y)是 無序 的 ? 完全圖 ? n個頂點的無向圖有 n(n1)/2條邊 ,該圖為完全圖 ? n個頂點的有向圖有 n(n1)條邊 ,該圖為完全有向圖 4 2 1 3 0 2 1 4 0 完全無向圖 8 6 7 3 6 5 無向圖 (自由樹 ) 1 2 0 有向圖 完全有向圖 圖的基本概念 ? 鄰接頂點 ? (u, v)是 E中的一條邊，則稱 u與 v互為鄰接頂點 ? 子圖 ? 設(shè)有兩個圖 G＝ (V, E) 和 G’＝ (V’, E’)。若 V’? V 且 E’?E, 則稱 G’是 G 的子圖 ? 權(quán)：邊附帶的權(quán)重，稱這樣的圖稱為帶權(quán)圖 5 2 1 3 0 1 3 0 2 1 3 2 1 3 0 子圖 圖的基本概念 ? 頂點 v的度 ? 與 v為端點的邊條數(shù)，記作 D(v) ? 入度：有向圖中 ,以 v為終點的邊的條數(shù) ,記作 ID(v) ? 出度：有向圖中 ,以 v為始點的邊的條數(shù) ,記作 OD(v) ? 有向圖中 v的度為入度與出度的和 ? 路徑 ? 圖 G＝ (V, E) 中 , 從頂點 vi 出發(fā) , 沿一些邊經(jīng)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1