Chapter 6 Graph Chang Chi-Chung 2011.11.17

Graph 圖(graph) 的定義 G = (V, E) 有向圖和無向圖 V為頂點的集合 E為邊的集合，以頂點對表示 Undirected graph (graph) edge (u,v) = (v,u) Directed graph (digraph) edge <u,v> ≠ <v,u>

Examples: Graphs (a) G1 (b) G2 (c) G3 1 2 1 2 1 3 3 4 5 6 2 1 2 1 2 1 3 3 4 5 6 2 V(G1) = {0, 1, 2, 3} V(G2) = {0, 1, 2, 3, 4, 5, 6} V(G3) = {0, 1, 2} E(G3) = {<0, 1>, <1, 0>, <1, 2>} E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} E(G2) = {(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)} Directed Graph Undirected Graph

Graph 有向圖 無向圖 directed graph undirected graph 3 連接 相鄰 incident 頂點 分支度 degree 3 連接 incident 相鄰 adjacent 頂點 vertax 邊 edge 有向圖 directed graph 無向圖 undirected graph

Simple Graph No self edges (self loops，自我迴路) A graph may not have an edge from a vertex, v, back to itself. No multiple edges (多重邊或平行邊) A graph may not have multiple occurrences of same edges. 1 3 1 2 2 (a) Graph with a self edge (b) Multigraph

Complete Graph Complete graph The number of distinct unordered pairs (u, v) with u≠v in a graph with n vertices is n(n-1)/2. Complete graph Undirected graph an n-vertex graph with exactly n(n-1)/2 edges. Directed graph an n-vertex graph with exactly n(n-1) edges K3 K4

Adjacent and Incident Undirected graph Directed graph 1 2 3 4 5 6 If (u, v) is an edge in E(G), vertices u and v are adjacent and the edge (u, v) is the incident on vertices u and v. Directed graph <u, v> indicates u is adjacent to v and v is adjacent from u. <u, v> is incident to u and v. 1 2 1 3 4 5 6 2

子圖 Subgraph A subgraph of G is a graph G’ such that V(G’) V(G) and E(G’) E(G). 1 2 1 2 (1) 1 2 3 (2) (3) 3 1 2 (5) (6) (7) (8) 1 2 3 (4)

Path and Length Path Length Simple Path A path from vertex u to vertex v in graph G is a sequence of vertices u, i1, i2, …, ik, v, such that (u, i1), (i1, i2), …, (ik, v) are edges in E(G). G’ is directed graph, <u, i1>, <i1, i2>, …, <ik, v> are edges in E(G’). Length The length of a path is the number of edges on it. Simple Path A simple path is a path in which all vertices except possibly the first and last are distinct. A path (0, 1), (1, 3), (3, 2) can be written as 0, 1, 3, 2.

Cycle A cycle is a simple path in which the first and last vertices are the same. Similar definitions of path and cycle can be applied to directed graphs.

Examples: Path, Simple Path, Cycle Path 2 (0,1) (1,3) (3,4) (4,5) 1 Path 3 (1,3) (3,4) (4,2) (2,1) 2 3 4 Simple Path Path 2、Path 3 Circle Path 3 5

連通圖 Connected 若圖G，任2點間有一路徑存在，該圖稱為連通圖。 若圖G不連通，則圖G的最大連通子圖，稱為圖G 的連通成分 (connected components) 若圖G為有向圖，若且惟若圖G中任兩點 u到v有一路徑存在，則 v 到 u亦存在有一路徑，則圖G 稱為強連通 (strongly connected) 有向圖G中，最大強連通子圖，稱為圖G 的強連通成分 (strongly connected components)

Example: Connected and Strongly Connected H1 H2 4 1 2 5 6 3 7 G3 1 1 2 2

雙連通 Biconnected 圖G 稱為雙連通，如果圖G中，任兩點間均有兩條不相交的路徑，則稱圖G為雙連通圖 圖G中最大的雙連通子圖，稱為雙連通成分(biconnected component) 加入G中額外的頂點或邊，將不為雙連通圖

G H J E F I D C 分隔頂點 B M K L 分隔邊 A

Forest & Tree 森林和樹 森林是沒有迴路 (cycle) 的圖。 樹是連通的森林。 生成樹 (spanning tree) 是圖G 的形成樹的生成子圖。

Spanning Trees & Complete Graph K4

Graph 的一些性質 定理6.6 令G為一具有 m邊的圖，則 定理 6.7 令G為一具有 m邊的有向圖，則

Graph 的一些性質 定理6.8 令G為一具有 n 個頂點和 m 個邊的簡單圖。 若G為無向圖，則 若G 為有向圖，則

Graph 的一些性質 定理6.11 圖G為一有 n 個頂點與 m 個邊的無向圖，則 若G為連通圖，則 m >= n – 1

圖的運用

重要的觀念 圖的表示方法 (資料結構) 圖的走訪 (traversal) 邊串列 (edges lists) 鄰接串列 (adjacency lists) 鄰接矩陣 (adjacency matrix) 圖的走訪 (traversal) DFS (深先搜尋，depth-first search) BFS (廣先搜尋，breadth-first search)

圖的表示-邊串列 頂點物件 邊物件

邊串列 以紀錄邊為主。 分為頂點物件及邊物件

圖的表示 – 鄰接串列

Adjacency Lists G1 G2 [0] 3 1 2 [1] 2 3 1 2 [2] 1 3 [3] 1 2 3 [0] 1 HeadNodes [0] 3 1 2 [1] 2 3 1 2 [2] 1 3 [3] 1 2 3 G1 HeadNodes [0] 1 [1] 2 1 [2] G2 2

Adjacency Lists H1 1 2 3 G3 H2 4 5 6 7 G3 [0] 2 1 [1] 3 [2] 3 [3] 1 1 HeadNodes [0] 2 1 1 2 [1] 3 [2] 3 3 [3] 1 1 G3 [4] 5 H2 [5] 4 6 4 [6] 5 7 5 6 [7] 6 7 G3

Inverse Adjacency Lists [0] 1 [1] 2 [2] 1 [0] 1 2 [1] G2 1 [2] 求入分支度須用此反轉串列

Adjacency Lists : Sequential Representation H1 H2 4 1 2 5 6 3 7 G3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 9 11 13 15 17 18 20 22 23 2 1 3 5 6 4 7 各頂點紀錄起始位置 各頂點連接的頂點

Adjacency Lists: Orthogonal List 1 tail head column link for head row link for tail 2 head nodes (shown twice) 1 2 1 1 1 1 2 2

Multilists [0] [1] [2] [3] m vertex1 1 2 N0 1 N1 N3 edge (0, 1) 3 N1 2 vertax2 list1 list2 1 2 HeadNodes [0] N0 1 N1 N3 edge (0, 1) 3 [1] N1 2 N2 N3 edge (0, 2) [2] [3] N2 3 N4 edge (0, 3) N3 1 2 N4 N5 edge (1, 2) The lists are N4 1 3 N5 edge (1, 3) Vertex 0: N0 -> N1 -> N2 Vertex 1: N0 -> N3 -> N4 N5 2 3 edge (2, 3) Vertex 2: N1 -> N3 -> N5 Vertex 3: N2 -> N4 -> N5

鄰接矩陣

Adjacency Matrix Adjacency Matrix is a two dimensional n×n array. 1 2 1 3 2 (a) G1 (b) G2

Adjacency Matrix H1 1 2 3 G4 H2 4 5 6 7 (c) G3

Depth-First Search 0,1,3,7,4,5,2,6 [0] 1 2 [1] 3 4 [2] 5 6 [3] 1 7 [4] 1 2 3 4 5 6 HeadNodes [0] 7 1 2 [1] 3 4 [2] 5 6 [3] 1 7 [4] 1 7 [5] 2 7 [6] 2 7 [7] 3 4 5 6

DFS Algorithm Algorithm DFS(G, v) Input: A graph G and a vertx v of G Output: A labeling of the edges in the connected component of v as discovery edges and back edges for all edges e in G.incidentEdges(v) do if edge e is unexplored then w  G.opposite(v, e) if vertax w is unexplored then label e as a discovery edge recursively call DFS(G, w) else label e as a back edge

DFS 可以做什麼？ 圖G 有n個頂點和 m 個邊，且使用連接串列表示的圖，則圖G 的DFS 走訪，可以在 O(n+m)完成，並可以解決以下問題 測試G是否連通 計算G的生成森林 計算G 的連通成分 計算G中兩頂點之間的路徑，或回報路徑不存在。 計算G中的一個迴路，或回報G沒有迴路。

返回邊 發現邊 Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ｈ Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ Ｏ Ｐ

計算雙連通成分 DE EC G H CD J CF KL E F I HJ EC FG D C JG GH IF HI B M K L CM MA AB A MB BC KA CK

計算雙連通成分演算法 參見課本 P315 及 P317

Breadth-First Search 0,1,2,3,4,5,6,7 [0] 1 2 [1] 3 4 [2] 5 6 [3] 1 7 1 2 3 4 5 6 HeadNodes [0] 7 1 2 [1] 3 4 [2] 5 6 [3] 1 7 [4] 1 7 [5] 2 7 [6] 2 7 [7] 3 4 5 6

BFS Algorithm Algorithm BFS(G, v) Input: A graph G and a vertx s of G Output: A labeling of the edges in the connected component of s as discovery edges and cross edges create an empty container L0 insert s into L0 i  0 while Li is not empty do create an empty container Li+1 for each vertax v in Li do for all edge e in G.incidentEdges(v) do if edge e is unexplored then let w be the other endpoint of e if vertax w is unexplored then label e as a discovery edge insert w into Li+1 else label e as a cross edge i  i+1

BFS 可以做什麼？ 基本上，DFS 可以辦得到的事，BFS 也可以辦得到。 在實作上，BFS 使用到 Queue，而 DFS 則 使用到 Stack。

發現邊 Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ｈ 交錯邊 Ｉ Ｊ Ｋ Ｌ Ｍ Ｎ Ｏ Ｐ

垃圾收集法 (garbage collection) 一些新出現的程式語言，對於動態配置記憶體的管理，交由執行時期 (run-time) 的環境。因此程式設計師不需要負責釋放記憶體，從而避免了 memory leak 的風險。 Java C# 透過 DFS 的方式，實作出垃圾收集器 (garbage collector)，將已釋放的記憶體回收。