Skip to content

graphs

以Python實作演算法 – Algorithms Implements using Python

  • Python

TOC

圖論 Graph Theory

G(V, E)

  • 由頂點(vertex, node)和連接頂點的邊(Edge)關聯成的圖形
  • 其中關聯分作有方向性(directed)及無方向性(undirected)
  • 須考慮最大流問題(maximum flow)

在程式語言有幾種方式來建構Graphs:

相鄰矩陣 adjacency matrixes

image
圖片來源

陣列 edge list representation

應用

  • 最短路徑演算法 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

深度優先搜尋 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

Read More »以Python實作演算法 – Algorithms Implements using Python