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,中文稱有向無環圖