資料結構與演算法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：下次把一篇拆成好幾天寫就有機會，感謝指正)
---
下次要早點寫，而且分好幾天寫....好累