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

03/31/2015

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

## 討論範圍

* Graphs and Graph Algorithms (3/3)
* Topological Sorting - Programming Exercises

## 心得筆記

三週 graphs 內容都在同一份簡報，本週內容從第 38 頁開始：

*

**Topological Sorting**

根據先後條件找出合理的排列順序。

呼叫 DFS，依照節點 finish time 反向排序後回傳。

**Strongly Connected Components**

用來簡化問題的複雜度，詳見簡報第 46 頁。

另有 Weakly Connected Component，教材未提及。

**Shortest Path Problem**

OSPF: [](http://www.netadmin.com.tw/article_content.aspx?sn=1304170001)http://www.netadmin.com.tw/article_content.aspx?sn=1304170001

Cisco Spanning Tree: [](http://www.hkitblog.com/?p=19137)http://www.hkitblog.com/?p=19137

**Broadcast Problem**

Minimum Spanning Tree

Prim’s Spanning Tree: 最小生成樹的特例，尋找最短路徑

Kruskal’s Algorithm: 根據邊的權重由小到大排序

所有證明可參考 [Introduction to Algorithms](http://mitpress.mit.edu/books/introduction-algorithms) 一書。

DS 讀書會到此結束。

成員推薦課程：

[Software Security](https://www.coursera.org/course/softwaresec)

[Discrete Optimization](https://www.coursera.org/course/optimization)

## 活動簽到

[AL](https://tossug.hackpad.com/ep/profile/o1ekz5Cvtoh)

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

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

[ChangZhuo Chen](/ep/profile/zENQHAa5JtB)

[FourDollars](/ep/profile/tgNQRpN8EgG)

[RJ Hsiao](/ep/profile/BzrOLagTOUQ)

StarNight

[violetson](/ep/profile/oJusv72f72w)

[Wen00072](/ep/profile/H12yKD7rYmT)