785. Is Graph Bipartite?

Medium

Description

給定一個無向圖的鄰接表 graph，判斷該圖是否為二部圖（Bipartite）。即能否將所有節點分成兩組，使得每條邊的兩端分屬不同組。

Example:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] Output: false

Intuition#

嘗試用兩種顏色著色，若能成功則是二部圖，否則不是。

二部圖等價於圖可以被二著色
用 BFS/DFS 對節點交替著色
若發現相鄰節點顏色相同，則不是二部圖

Approaches#

1: BFS 著色#

概念: BFS 遍歷，交替分配顏色，發現衝突即回傳 false
時間複雜度: O(V + E)
空間複雜度: O(V)

class Solution {
    fun isBipartite(graph: Array<IntArray>): Boolean {
        val n = graph.size
        val color = IntArray(n) // 0: 未著色, 1: 組A, -1: 組B

        for (start in 0 until n) {
            if (color[start] != 0) continue
            val queue = ArrayDeque<Int>()
            queue.add(start)
            color[start] = 1
            while (queue.isNotEmpty()) {
                val node = queue.removeFirst()
                for (next in graph[node]) {
                    if (color[next] == 0) {
                        color[next] = -color[node]
                        queue.add(next)
                    } else if (color[next] == color[node]) {
                        return false
                    }
                }
            }
        }
        return true
    }
}

⭐2: DFS 著色#

概念: DFS 遞迴著色，程式碼更簡潔
時間複雜度: O(V + E)
空間複雜度: O(V)

class Solution {
    fun isBipartite(graph: Array<IntArray>): Boolean {
        val color = IntArray(graph.size)

        fun dfs(node: Int, c: Int): Boolean {
            color[node] = c
            for (next in graph[node]) {
                if (color[next] == c) return false
                if (color[next] == 0 && !dfs(next, -c)) return false
            }
            return true
        }

        for (i in graph.indices) {
            if (color[i] == 0 && !dfs(i, 1)) return false
        }
        return true
    }
}

🔑 Takeaways#

Pattern: 圖的二著色 – 判斷二部圖等價於圖可以被二著色
關鍵技巧: 圖可能不連通，需要對每個連通分量都做檢查；用 1 和 -1 表示兩種顏色方便取反