星期日, 3月 18, 2007

資料結構與演算法02 by 隨機客

非正題
工院盃快結束了,我所能做的事也暫告一段落,所以我決定在下次上課前趕快把上課隨筆寫出來,不然lag到就麻煩了,也很久沒有寫blog了。



2007/03/05 資料結構與演算法(下)02 呂學一 投影片

這堂課最主要講的是Graph 圖論(The adjancency among a set of nodes),重點落在Depth First Search DFS而今天主要著重在三個問題上,但是在進入這三個問題前,什麼是Graph?
G = (V,E) to denote that G is a graph, where V consists of the nodes of G and E consists of the nodes of G and E consists of the edges of G. (yen3註:簡而言之,一張圖G由節點V,和連接邊E所組成),通常使用(n,m) 元素個數來代表(V,E)的集合

而要怎麼表示一個Graph呢,最常見的有兩種方法
  • adjacency matrix
    一個很直覺的方法,使用一個space為O(n^2)來儲存(yen3註:很直覺存法就是使用二維陣列),若(1,2)有所連結,則在table的(1,2)(2,1)標示為1,代表有其連結,其優點是速度快,在Insertion, Deletion, Query 都是O(1) ,缺點是,若是連接邊集中於某些點JK:若是matrix 很稀疏,意指邊很少的狀況下,則會浪費很多空間。

  • Adjacency list
    很直覺的方法,為絕大部分Graph Algorithm所使用的Data Structure,方法是,每一個節點建立一個sorted list(JK註,不一定為sorted,為sorted也沒什麼好處),若和此邊有所連接,則插入(見s.8)(yen3註:在C++中,可用link list或者是STL中的vector儲存節點),優點是節省空間,缺點是速度較慢,Insertion, Deletion 為O(1) (yen3註:O(n) 也是有可能的,端看如何設計) ,Query 為O(deg) (deg 為資料深度), Space 為O(m) (m 為edge數)

  • Adjacency list with balanced search tree
    方法與第二種相同,只是儲存資料時改用BST來儲存,如此在Query則會降成O(log deg)。

那麼三個問題又是什麼呢,分別如下
  • Connected components
    什麼是Connected components呢,定義如下
    Each connected component of graph G=(V,E) is maximan subset U of V such that any tow nodes in U are connected in G.(yen3註:簡而言之,在一圖型G中,尋找subgraph G 包含最多節點n)

  • 解法,則使用(JK註:因為disjoint sets無法在linear time解決,所以才使用DFS)了disjoint sets的概念(s.18),而pseudo code在s.23,至於使用DFS是否為linear time? 見我們需見到subroutine visit中的for loop,此處證明為O(m+n)(yen3註:太晚寫筆記,我忘了怎麼證了Orz)。中間插話,上帝有一本美麗的數學證明本(s.25)XD

  • Topological sort(拓撲排序)
    首先,Topological sort是使用在directed graph上,這時候又會牽扯到DAG(directed acyclic graph - a directed graph that does not contain any cycle.(yen3註:簡而言之,不會有任任何成為cycle的node,就是不能從A node出發再回到A node)),其example在s.30,其pesudo code在綠色字處,加入計算每個節點被拜訪到的先後順序(yen3註:上課時沒有證明,不過用實例跑過一次,確實相同),而,在把答案output時,將t從大到小輸出,原因也蠻直觀的,因為排序最後的節點,是會最先被參觀到的,而排序最前的節點,由於並無人指向,所以是最後被參觀到的,所以一個圖G,並不一定只有一組解,可能會有好幾組解(yen3註:原因,我好難解釋Orz)。證明從s.35開始

  • Strongly Connected components
    定義如下
    Each strongly connetced component of graph G= (V,E) is a max imal subset U of V such that any two nodes in U are reachable(through directed paths) from each ohter in G.(yen3註:在directed graph中,尋找max cycle的subgraph)

    演算法的方法也很簡單,步驟如下
    1. Topological sortDFS讓每個node有一順序
    2. 將圖上的directed edge全部反向
    3. 再跑一次Topological sortDFS(根據第一次跑出來的Topological sort list來執行),每一個list代表一個答案

    那麼為什麼這樣子的演算法可以成立,隨機客使用了非常直觀的證明方法而避免掉課本一拖拉庫的證明(s.49, 50)(yen3註:時間太久,我竟然忘了XD)。




請盡量指教,謝謝:)

(Josh Ko:正確性的證明需提一下,至少命題要寫)
(yen3:下次把一篇拆成好幾天寫就有機會,感謝指正)
---
下次要早點寫,而且分好幾天寫....好累

張貼留言