MediumRating 1625
785. Is Graph Bipartite?
depth-first-searchbreadth-first-searchunion-findgraph
解題說明
Is Graph Bipartite?
題目描述：給定一個無向圖的鄰接表 graph，判斷此圖是否為二分圖（Bipartite Graph）。二分圖的定義是：可以將所有節點分成兩個集合，使得每條邊的兩個端點分別屬於不同集合。
解題思路：使用 BFS 或 DFS 進行二著色（2-Coloring）。若能用兩種顏色為所有節點著色，且相鄰節點顏色不同，則是二分圖：
- 對每個未著色的節點（可能有多個連通分量），開始 BFS。
- 將起點著色為顏色 0，其鄰居著色為顏色 1，鄰居的鄰居著色為顏色 0，依此類推。
- 若發現某個鄰居已被著色且顏色與當前節點相同，則不是二分圖。
C++ 解法
複雜度分析
時間複雜度：O(V + E) — V 為節點數，E 為邊數。每個節點和每條邊各被訪問一次。
空間複雜度：O(V) — 顏色陣列和 BFS 佇列。
虛擬碼
1. Initialize color array with -1 (uncolored) for all nodes
2. For each uncolored node i:
a. BFS from i, color i with 0
b. For each neighbor v of current node u:
- If uncolored: color v = 1 - color[u], enqueue v
- If color[v] == color[u]: return false (odd cycle)
3. Return true其他解法
DFS 著色法：用遞迴 DFS 代替 BFS 進行著色。邏輯相同，時間 O(V+E)，空間 O(V)（遞迴堆疊）。DFS 的程式碼通常更簡短。
Union-Find：對每個節點，將其所有鄰居合併到同一集合。若發現節點和其鄰居在同一集合中，則不是二分圖。時間 O(V * alpha(V) + E)，接近線性。適合動態圖（邊逐步加入）的場景。
延伸思考
- 二分圖判定和「是否存在奇數長度的環」有什麼等價關係？
- 如果圖是有向的，還能用同樣的方法判定嗎？
- 如何找到二分圖的最大匹配？（提示：匈牙利演算法）