Microsoft PowerPoint - lecture9.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - lecture9.pptx"

内曹
3 years ago
Views:

1 連載 : 學生上課睡覺姿勢大全 GRAPH Michael Tsai 2010/11/19

2 2 本日行程考卷檢討, 2 4 題 Threaded binary tree 漏掉的一部分三個問題, 一樣答案 Graph

3 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 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 5 Threaded Binary Tree 接著, 要做 inorder traversal 就很簡單了 for(;;) { } temp=insucc(temp); if (temp==tree) break; // 走回 root 了 printf( %3c, temp >data);

6 6 三個問題, 一樣解答問題一 n 個 node 的 binary tree, 總共有幾種? 例如 : n=3 的話有五種

7 7 三個問題, 一樣解答問題二矩陣乘法 : matrix 乘法是 associative 意思就是 : 問 : 總共有幾種乘法? 例如 : n=4 的時候, 有五種

8 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 9 來解問題二其他其實是一模一樣的問題 ( 幾乎 ) 最強的方法 : recursive! 其實總共的數目, 會等於 1 個矩陣可以排的數目 *n 1 個矩陣可以排的數目 2 個矩陣可以排的數目 * n 2 個矩陣可以排的數目 n 1 個矩陣可以排的數目 *1 個矩陣可以排的數目通通加起來, 1, 1(recursive)

10 10 來解問題一, 1, 1(recursive)

11 11 最後的推倒 ( 誤 ) So, b, 1, 1(recursive) 1 /

12 12 Königsberg Seven Bridge Problem 西元 1736 年, Euler 嘗試著要解答這個問題 : 右邊地圖中, 有沒有可能找出一條路徑, 使得每一條橋都走過一次之後又回到出發點? 答案 : 請見課本 p. 267

13 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 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>}

15 15 Self Edge & Multigraph Multigraph 0 Graph with self edges <v,v>

16 16 Maximum number of edges 一個有 n vertices 的 graph, 最多有幾個 edges? 一個有 n vertices 的 digraph, 最多有幾個 edges? 答案 : graph:, digraph: 1

17 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.) 作用 (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 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 裡面的連續的一段

19 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) 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

20 20 強連接 (strongly connected) In digraph: Strongly connected: G is strongly connected iff 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 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 一個 degree=0 的 vertex 可稱為 isolated Edge 數和 degree 的關係 : 2

22 22 要怎麼表示一個 graph 呢? 跟要使用的 operation 有關讓我們先定義一些 : create insertvertex insertedge deletevertex deleteedge isempty Adjacent 之後還有其他的

23 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) 請同學解釋要怎麼建 adjacency matrix 粉簡單. 那麼來看看好不好用 : 如果要看總共有多少條 edge? O(??) 答 : 有沒有可能跟 edge 數 (e) 成正比呢? 之類的通常, 所以 adjacency matrix 裡面很空

24 24 表示法 II 用 linked list 本方法叫做 adjacency lists 建立一個 list array a[n] (n 為 vertex 數目 ) 每個 list 裡面紀錄通往別的 vertex 的 edge 問 : 怎麼算 in degree? [0] [1] [2] [3] [4] [5] 答 : 如果要比較容易的話, 要另外建 inverse adjacency lists 請同學告訴我怎麼畫 ( 參見課本 p275)

25 25 表示法 II 用 linked list adjacency list 的變形 : \0 \0 1 0 \0 1 2 \0 \0 2 \0 edge: <u,v> u v 指到下一個由 u 出發的 edge 指到下一個進入 v 的 edge

26 26 表示法 III adjacency multilist 另外一種 list representation 的變形 Mark Vertex1 Vertex2 Link1 Link2 [0] [1] [2] [3] \ \0 2 3 \0 \

27 27 Weighted Edge Edge 可以有 weight 表示長度, 或者是需要花費一個 edge 有 weight 的 graph 又叫做 network 想想看 : 用剛剛的 representation 要怎麼儲存 weight? 答 : adjacency matrix 可以用 array 的值來存 adjacency list 可以在 list node 裡面多開一個欄位存

28 下課休息 28

29 下課休息 29

30 30 周末愉快! 考卷下周發放 ( 抱歉 T_T) 分數有問題的可以多利用 office hour 分數很低的同學 ( 擔心被當掉 ), 請來找我聊天

<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446>

<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446> : 2 = 3 4? 0 an ordered set of unambiguous, executable steps that produces a result and terminates in a finite time (computational theory) ( ) 5 6 (C-) int min, max; float degree, b; char ch, token; /,,,