[演算法] Graph

Graph 是由點 node 和邊 edge 所 構成的,一個圖可以用G = (V,E) 來表示,

其中 V 是頂點集合,E 是邊集合

分別有:

  • 有向圖 Directed Graph: 每條邊是單方向的,即一條邊 (u, v) 只代表能從 u 到 v
  • 連通圖 Connected Graph:每對點之間都存在一條路徑可以相通
  • 無向圖Undirected Graph:邊是雙向的,一條邊(u, v) 代表u可以到v,v亦可到u。
  • 無環圖 Acyclic Graph:沒有 cycle 的圖
  • 有向無環圖 Directed Acyclic Graph: 可以會有拓扑排序 (Topological sorting)

呈現方式:

相鄰串列 Adjacency list

對於每個點,存下與它相鄰的所有頂點編號

有向圖為例

相鄰矩陣 Adjacency matrix:

元素 matrix[v][u] 代表 v 是否有邊到 u

有向圖為例

Graph 跟 Tree 的差別

沒有 Cycle 無向的 Graph 就是 Tree

沒有 Cycle有向的 Graph 就是 DAG,中文稱有向無環圖

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *