連載 : 學生上課睡覺姿勢大全 http://www.wretch.cc/blog/chi771027/26489957 GRAPH Michael Tsai 2010/11/19
2 本日行程 考卷檢討, 2 4 題 Threaded binary tree 漏掉的一部分 三個問題, 一樣答案 Graph
3 Threaded binary tree 長這樣 root f A f f B f t C t t D t f E f f F t t G t t H t
4 Threaded binary tree 長這樣 ( 訂正 ) root f t f A f f B f t C t t D t f E f f F t t G t t H t
5 Threaded Binary Tree 接著, 要做 inorder traversal 就很簡單了 for(;;) { } temp=insucc(temp); if (temp==tree) break; // 走回 root 了 printf( %3c, temp >data);
6 三個問題, 一樣解答 問題一 n 個 node 的 binary tree, 總共有幾種? 例如 : n=3 的話有五種
7 三個問題, 一樣解答 問題二 矩陣乘法 : matrix 乘法是 associative 意思就是 : 問 : 總共有幾種乘法? 例如 : n=4 的時候, 有五種
8 三個問題, 一樣解答 問題三 使用一個 stack, 把 1 到 n 的整數照順序 push 進去, 但是中間可以夾雜任意次數的 pop, 請問 output 有幾種? 假設 n=3 則有五種 (push 1, pop, push 2, pop, push 3, pop) 123 (push 1, push 2, pop, pop, push 3, pop) 213 (push 1, pop, push 2, push 3, pop, pop) 132 (push 1, push 2, pop, push 3, pop, pop) 231 (push 1, push 2, push 3, pop, pop, pop) 321
9 來解問題二 其他其實是一模一樣的問題 ( 幾乎 ) 最強的方法 : recursive! 其實總共的數目, 會等於 1 個矩陣可以排的數目 *n 1 個矩陣可以排的數目 2 個矩陣可以排的數目 * n 2 個矩陣可以排的數目 n 1 個矩陣可以排的數目 *1 個矩陣可以排的數目 通通加起來, 1, 1(recursive)
10 來解問題一, 1, 1(recursive)
11 最後的推倒 ( 誤 ) 1 0 1 So, b, 1, 1(recursive) 1 / 1 2 1 1 2 4 1 2
12 Königsberg Seven Bridge Problem 西元 1736 年, Euler 嘗試著要解答這個問題 : 右邊地圖中, 有沒有可能找出一條路徑, 使得每一條橋都走過一次之後又回到出發點? 答案 : 請見課本 p. 267
13 A graph G: a graph, consists of two sets, V and E. V: a finite, nonempty set of vertices. E: a set of pairs of vertices. 0 G=(V,E) V={0,1,2,3} E={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} 1 3 2
14 Directed & undirected graph Graph 中, edge 有方向的叫做 directed graph, 沒方向的叫做 undirected graph Directed graph 通常又叫 digraph Undirected graph 通常就只叫做 graph (1,2) 和 (2,1) 在 undirected graph 是一樣的 edge <1,2> 和 <2,1> 在 digraph 是不一樣的 edge V={0,1,2,3} E=? E={<0,1>,<0,2>,<1,2>,<2,1>,<3,1>,<3,2>} 1 0 3 2
15 Self Edge & Multigraph Multigraph 0 Graph with self edges <v,v> 0 1 2 1 2 3 3
16 Maximum number of edges 一個有 n vertices 的 graph, 最多有幾個 edges? 一個有 n vertices 的 digraph, 最多有幾個 edges? 答案 : graph:, digraph: 1
17 怎麼這麼多名詞 XD 相鄰 (adjacent): 如果有 edge (u,v), 那麼 u, v 兩 vertices 就是 adjacent. 如果有 edge <u,v> 那麼我們說 v is adjacent to u. ( 課本用相反的定義, 說有 <u,v> 的話是說 u is adjacent to v.) 1 0 2 作用 (incident): 如果有 edge (u,v) 那麼 u, v 兩 vertices 就是 incident ( 作用 )on ( 在 ) u 和 v 上面 <u,v> is incident from u and is incident to v. Subgraph: 如果 G=(V,E), G =(V,E ) 是 G 的 subgraph, 則 V V 且 E E 3
18 路徑 (path) Path: 一條從 u 到 v 的 path, 是一連串的 vertices,,,,,,, 而且,,,,,,,, 都是 edge. (digraph 的定義自行類推 ) 0 以上的 path 也可以寫成,,,,,. Path 的 length: 裡面有幾條 edge Simple path: 除了 u, v( 起點和終點 ) 以外, 其他的 vertices 都沒有重複過. Cycle: 一個 u 和 v 一樣的 simple path Subpath:?? 答案 : 定義 path 的 vertex sequence 裡面的連續的一段. 1 3 2
19 0 有連接的 (connected) In undirected graph: Vertices u and v are said to be connected iff there is a path from u to v. (graph & digraph) 1 3 2 5 4 Connected graph: iff every pair of distinct vertices u and v in V(G) is connected Connected component ( 也有人直接叫 component): A maximal connected subgraph Maximal: no other subgraph in G is both connected and contains the component. 問 : Tree 是一個怎麼樣的 graph? 答 : connected and acyclic ( 沒有 cycle) graph 問 : Forest 是一個怎麼樣的 graph? 答 : acyclic graph 1 2 3 5 4
20 強連接 (strongly connected) In digraph: 1 2 3 Strongly connected: G is strongly connected iff 4 5 6 for every pair of distinct vertices u and v in V(G) there is a directed path from u to v and also from v to u. Strongly connected component: A maximal subgraph which is strongly connected.
21 Degree of vertex Vertex 的 degree: 有幾個 edge 連在 vertex 上 Digraph 中 又可分為 in degree and out degree in degree: 進入 vertex 的 edge 數 out degree: 出去 vertex 的 edge 數 degree=in degree+out degree 1 2 3 4 5 6 一個 degree=0 的 vertex 可稱為 isolated Edge 數和 degree 的關係 : 2
22 要怎麼表示一個 graph 呢? 跟要使用的 operation 有關 讓我們先定義一些 : create insertvertex insertedge deletevertex deleteedge isempty Adjacent 之後還有其他的
23 表示法 I 用 Array 本方法叫做 adjacency matrix index 當作 vertex 號碼 edge 用 matrix 的值來表示 : 如果有 (i,j) 這條 edge, 則 a[i][j]=1, a[j][i]=1. (graph) 如果有 <i,j> 這條 edge, 則 a[i][j]=1. (digraph) 1 2 3 4 5 6 請同學解釋要怎麼建 adjacency matrix 粉簡單. 那麼來看看好不好用 : 如果要看總共有多少條 edge? O(??) 答 : 有沒有可能跟 edge 數 (e) 成正比呢? 之類的 通常, 所以 adjacency matrix 裡面很空
24 表示法 II 用 linked list 本方法叫做 adjacency lists 建立一個 list array a[n] (n 為 vertex 數目 ) 每個 list 裡面紀錄通往別的 vertex 的 edge 問 : 怎麼算 in degree? [0] [1] [2] [3] [4] [5] 1 3 4 0 4 3 2 0 1 2 3 4 5 答 : 如果要比較容易的話, 要另外建 inverse adjacency lists 請同學告訴我怎麼畫 ( 參見課本 p275)
25 表示法 II 用 linked list adjacency list 的變形 : 0 1 2 2 0 1 0 1 0 1 \0 \0 1 0 \0 1 2 \0 \0 2 \0 edge: <u,v> u v 指到下一個 由 u 出發的 edge 指到下一個進入 v 的 edge
26 表示法 III adjacency multilist 另外一種 list representation 的變形 Mark Vertex1 Vertex2 Link1 Link2 [0] [1] [2] [3] 0 1 0 2 0 3 \0 1 2 1 3 \0 2 3 \0 \0 0 1 2 3
27 Weighted Edge Edge 可以有 weight 表示長度, 或者是需要花費 一個 edge 有 weight 的 graph 又叫做 network 3 0 1 2 4 3 2 5 2 3 4 5 1 想想看 : 用剛剛的 representation 要怎麼儲存 weight? 答 : adjacency matrix 可以用 array 的值來存 adjacency list 可以在 list node 裡面多開一個欄位存
下課休息 28
下課休息 29
30 周末愉快! 考卷下周發放 ( 抱歉 T_T) 分數有問題的可以多利用 office hour 分數很低的同學 ( 擔心被當掉 ), 請來找我聊天