Graph 是什麼？

Graph是一種抽象的資料結構，用來表示物體與物體之間的關係。是一種由節點(Node/ Vertex)和邊(Edge)組成的資料結構，用來描述物件之間的關係。

Graph是由兩個核心元素組成：G= (V,E)
V - 節點（Vertex）：代表的是資料元素，也叫頂點或節點（Node）。 
E - 邊（Edge）：代表節點之間的連結關係，通常都是由一對節點(u,v)來表示。 

Graph 的類型

那根據邊的特性，Graph可以分成四種主要的類型:

1. 無向圖(Undirected Graph)

   • 邊是雙向的，沒有方向性
   • A和B之間有一條邊是 A<——>B（A連到B，B也連到A）
   • Ex:A是B的家人，B也是A的家人

2. 有向圖 (Directed Graph / Digraph)

   • 邊是單向的，有固定的方向
   • A和B之間有一條邊A——>B(A連到B，但B不一定連到A)
   • Ex:A在IG追蹤了B，但不代表B必須追蹤A

3. 加權圖 (Weighted Graph)

   • 每條邊都有一個相關聯的「權重」或「成本」
   • 權重可以是任何數值，代表不同的意義
   • Ex:
     地圖：邊的權重可以代表兩個城市之間的「距離」（公里）或「行車時間」（分鐘）
     電腦網路： 邊的權重可以是兩個節點之間的「延遲」（latency）或「頻寬」

4. 無權圖 (Unweighted Graph)

   • 邊沒有權重，連接或不連接
   • 只關心「有沒有連接」，不關心連接的「成本」

Graph 在程式中如何表示

1. 鄰接矩陣 (Adjacency Matrix)

   • 鄰接矩陣是一個V * V的二維陣列。
   • matrix[i][j] = 1 表示從頂點i到頂點j有一條邊，那matrix[i][j] =0的話就是沒有邊。
   • 優點:檢查兩個頂點之間是否有邊非常快。
   • 缺點:很佔空間，如果Graph頂點很多但邊很少，會浪費大量空間。

2. 鄰接串列 (Adjacency List / 鄰接表)

   • 一個陣列或Map，其中每個索引i都會對應到一個串列（List）。
   • adjList[i]儲存了一個串列，裡面包含了所有與頂點i相鄰的頂點。
   • 優點：空間效率高，適合稀疏圖。
   • 缺點：檢查i和j之間是否有邊，需要O(k)時間(k是頂點i的鄰居數）

Graph 的基本操作 / 演算法

1. DFS (Depth-First Search)

• 深度優先搜索，使用遞迴 (Recursion) 或堆疊 (Stack)
• 先沿著一條路走到頭，再回頭探索其他路徑
• 適用：找路徑、檢查循環、拓撲排序

2. BFS (Breadth-First Search)

• 廣度優先搜索，使用佇列 (Queue)
• 一層一層探索節點，像水波紋一樣一層一層向外擴散
• 適用：最短路徑、層級遍歷、最小步數問題

3. Cycle Detection (循環檢測)

• 檢查有向圖或無向圖是否有循環
• DFS + 訪問狀態或 Union-Find

4. Topological Sort (拓撲排序)

• 用於有向無循環圖 (DAG)
• 安排節點順序，例：課程表、任務排程

5. 最短路徑算法

• BFS → 無權圖最短路徑
• Dijkstra → 有權圖最短路徑
• Bellman-Ford → 有負權邊的最短路徑

總結就是Graph是一種強大靈活的工具，是演算法和資料結構的基石!