以Python實作演算法 – Algorithms Implements using Python
TOC
- 圖論 Graph Theory
- 廣度優先搜尋 Breadth-first Search, BFS
- 深度優先搜尋 Depth-first Search, DFS
- 最短路徑演算法 Shortest Path
圖論 Graph Theory
G(V, E)
- 由頂點（vertex, node）和連接頂點的邊（Edge）關聯成的圖形
- 其中關聯分作有方向性(directed)及無方向性(undirected)
- 須考慮最大流問題(maximum flow)
在程式語言有幾種方式來建構Graphs:
相鄰矩陣 adjacency matrixes
陣列 edge list representation
|
1 2 3 4 5 6 7 8 9 10 11 |
class Node: def __init__(self, name): self.name = name self.visited = False self.neighbors = [] # Nodes self.predecessor = None # use in shortest path def __repr__(self): return 'Node(name={})'.format(self.name) |
應用
- 最短路徑演算法 Shortest Path Algorithm: GPS, 高頻交易
- 生成樹協定 Spanning Tree Protocol, STP
- 爬蟲
廣度優先搜尋 Breadth-first Search, BFS
- 時間複雜度：
O(V+E)（分別遍歷所有節點和各節點的所有鄰居） - 空間複雜度：
O(V)（Queue中最多可能存放所有節點） - 用於有效率的迭代(traversal)
- 迭代的方式為鄰近的先訪問(level-ordered)
- 劣勢在於儲存指標記憶體空間，有時用DFS替代
- 使用FIFO的Queue來實作，Queue為空代表完成迭代
應用
- machine learning
- Edmonds-Karp演算法
- Cheney演算法
以Python實作，輸出請參考gist
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class BFS: """ For BFS, use queue; For DFS, use stack or recursion """ def __init__(self, start): self.queue = [] self.start = start def traversal(self): self.start.visited = True self.queue.append(self.start) while self.queue: # O(V) node = self.queue.pop(0) yield node for n in node.neighbors: # O(E) if not n.visited: n.visited = True self.queue.append(n) |
深度優先搜尋 Depth-first Search, DFS
- 時間複雜度：
O(V+E) - 空間複雜度：
O(logV)（訪問至末端節點後LIFO，Stack最多只會同時存在logV個節點，也就是樹的高度） - 為了解Maze Problem而生的演算法
- 效能比BFS稍佳
- 使用LIFO的Stack來實作
應用
- 拓撲排序 Topological Order
- Kosaraju演算法: 推薦系統 Recommand System
- 判斷Grapth是否有cycle(DAG)
- Maze
以Python實作，輸出請參考gist
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class DFS: """ For BFS, use queue; For DFS, use stack / recursion(os stack) """ def __init__(self, start): self.start = start def traversal(self): interface = self.stack() interface(self.start) return self.result def stack(self): self.result = [] def interface(node): self.result.append(node) node.visited = True for n in node.neighbors: if not n.visited: interface(n) return interface |
Read More »以Python實作演算法 – Algorithms Implements using Python