---
hackpadID: WEIZrjFe7P6
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 15 週
###### tags: `TOSSUG 讀書會`

03/24/2015

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

## 討論範圍

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

## 預定進度

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

## 認領狀態

* Shortest Path Problems
* [Bruce Tsai](/ep/profile/oLLqeaQgDjg)
* Dijkstra’s Algorithm
* [Bruce Tsai](https://tossug.hackpad.com/ep/profile/oLLqeaQgDjg)
* Prim’s Spanning Tree Algorithm
* [Bruce Tsai](https://tossug.hackpad.com/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 (Figure 2)。

每個點可移動的步數不一樣，愈靠近邊緣愈少，應該先走。

Knight’s Tour 是 DFS 問題，深度為 8 * 8 = 64。

DFS 用上色的方式去標記節點，找出路徑。

P, NP, NP-Complete, NP-Hard，詳見：

* [](http://en.wikipedia.org/wiki/NP-complete)http://en.wikipedia.org/wiki/NP-complete。
* [](https://tw.knowledge.yahoo.com/question/question?qid=1005011804601)https://tw.knowledge.yahoo.com/question/question?qid=1005011804601

Q: What’s the difference between BFS and DFS?

A: （知道應用情境的朋友可以回答一下嗎？）

Python 的 7 道~~陰影~~面試題：

[](http://www.toptal.com/python/interview-questions)http://www.toptal.com/python/interview-questions

## 活動簽到

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

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

[FourDollars](/ep/profile/tgNQRpN8EgG)

[Jo Jo](/ep/profile/v2IkzygwDuI)

[violetson](/ep/profile/oJusv72f72w)