---
hackpadID: Ban0ccXFt8y
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 14 週

03/03/2015

[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)

## 討論範圍

* Graphs and Graph Algorithms (1/3)
* Objectives - Breadth First Search Analysis

## 預定進度

* Graphs and Graph Algorithms (2/3)
* The Knight’s Tour Problem - Depth First Search Analysis

## 認領狀態

* Building the Knight’s Tour Graph
* [Bruce Tsai](/ep/profile/oLLqeaQgDjg)
* General Depth First Search
* [Bruce Tsai](/ep/profile/oLLqeaQgDjg)

## 心得筆記

*

[](http://www.slideshare.net/YiLungTsai/problem-solving-with-algorithms-and-data-structure-graphs)http://www.slideshare.net/YiLungTsai/problem-solving-with-algorithms-and-data-structure-graphs

**Graph**

Trees 就是 Graphs 的一種特例。

Vertex (node) 是節點

Edge (arc) 是連線，可能有或沒有方向性

vertex 都是平等的，所以沒有深度 (Tree 有 root node、leaf node，有深度)

vertex 和 edge 可以有一些屬性，例如顏色、權重...

**Undirected Graph**

G = (V, E)

V = {v1, v2, ...}

E = {(v1, v2), (v1, v5), (v2, v3), …}

(v1, v2) == (v2, v1)

**Directed Graph**

D = (V, A)

V = {v1, v2, ...}

E = {(v1, v2), (v1, v5), (v2, v3), …}

(v1, v2) != (v2, v1)

**Path**

Path 是一個起始 vertex 經過哪些 edge、vertex 到目的地 vertex 的路徑。

例如：v1 -> v3 -> v4

**Cycle**

Cycle 是起始 vertex 和目的地 vertex 是同一個點，所走過的 path 形成一個 cycle。

例如：v1 -> v5 -> v2 -> v1

**Adjacent**

某 vertex 和鄰近 vertex 透過 edge 相連。

**Adjacency Matrix**

可用來表示 graph，但佔用 n**2 空間，多數空間都沒用到。

**Adjacency List**

較 Adjacency Matrix 節省更多空間，透過一個 list 儲存所有 vertex，每筆 vertex 對應到一筆資訊。

**The Word Ladder Problem**

FOOL -> POOL -> POLL -> POLE -> PALE -> SALE -> SAGE

一次取代一個字母，最終換成想要的單字。這是一個 graph 問題。

每個字母都建 index，對應到符合的單字集合，接著透過 BFS 尋找解答。

**BFS (Breadth First Search)**

graph → tree → 從找到的leaf node往root node找，所得到的路徑即為graph中的path  

時間複雜度：O(V*L + 2*E) = O(V + E)

**補充資料**

平方根有個 magic number: 0x5f3759df。

平方根計算可用牛頓法，詳細證明請參閱第 2 週筆記。

Skip Lists 是一種隨機資料結構，實作簡單又快速，空間用很少，適合平行運算，可做為 BST 的另一個選擇。

隨機演算法有一些重要的應用，通常都是去證明它誤差範圍或出錯機率有多低，可以用低成本換取更高效益。

Trees 在現實生活中跟 file systems 密切相關，很多內建的演算法也都會用到。

四元想到 [](https://demo.sandstorm.io/)https://demo.sandstorm.io/ 也可以無痛快速建構 IPython Notebook。

au 翻譯的簡報 [](https://docs.google.com/presentation/d/1-ZVGV6qlQ2cug7Rl_qkSduiFkNLdCbSCuqIcLhd3sA4/edit)https://docs.google.com/presentation/d/1-ZVGV6qlQ2cug7Rl_qkSduiFkNLdCbSCuqIcLhd3sA4/edit

## 活動簽到

[Bruce Tsai](/ep/profile/oLLqeaQgDjg)

[Carl Su](/ep/profile/n5euV0AaWLn) 

[F](/ep/profile/tgNQRpN8EgG)[ourDollars](/ep/profile/tgNQRpN8EgG)

Freeman

[Manuel Stallman](https://tossug.hackpad.com/ep/profile/GgkcGJEol5r)

[RJ Hsiao](https://tossug.hackpad.com/ep/profile/BzrOLagTOUQ)

StarNight

[violetson](/ep/profile/oJusv72f72w)

[Yuan CHAO](/ep/profile/tWFK4EfMvdy)