785.is-graph-bipartite.md

785. Is Graph Bipartite?

Traversal

What's bipartite? For every edge (u, v) in graph, the two nodes will belong to two different vertex set. All the source nodes are in one set, and all the destination nodes are in another set.

a -> b
c -> d

// Bipartite
set1 = {a, c}
set2 = {b, d}

For this problem, we can use graph coloring to solve:

• We can run DFS/BFS to colors the vertex to two color.
• If the vertex is colored (visited), but it's not the color we're going to color, then it validates the condition.
• The graph might not connected, so we have to source every vertex.

DFS

private val notVisited = 0
fun isBipartite(graph: Array<IntArray>): Boolean {
    val n = graph.size
    val colors = IntArray(n) { notVisited }
    for (i in 0 until n) {
        if (colors[i] == notVisited) {
            if (!dfs(graph, i, 1, colors)) return false
        }
    }
    return true
}

private fun dfs(graph: Array<IntArray>, i: Int, toColor: Int, colors: IntArray): Boolean {
    if (colors[i] != notVisited) {
        return colors[i] == toColor
    }
    colors[i] = toColor
    graph[i]?.forEach { adj ->
        // toColor * -1 is the opposite color
        if (!dfs(graph, adj, toColor * -1, colors)) return false
    }
    return true
}

BFS

fun isBipartite(graph: Array<IntArray>): Boolean {
    // 0: not visited, -1 or 1 is the color
    val colors = IntArray(graph.size)
    for (source in graph.indices) {
        if (colors[source] == notVisited) {
            if (!bfs(graph, source, colors)) return false
        }
    }
    return true
}

// We color the adjacent nodes with opposite color, and check if there's a conflict.
private fun bfs(graph: Array<IntArray>, source: Int, colors: IntArray): Boolean {
    val queue = ArrayDeque<Int>()
    var toColor = 1
    queue.addLast(source)
    colors[source] = toColor
    while (!queue.isEmpty()) {
        val size = queue.size
        toColor *= -1 // Reverse the color
        repeat(size) {
            val node = queue.removeFirst()
            for (adj in graph[node]) {
                if (colors[adj] != notVisited) {
                    if (colors[adj] != toColor) return false
                    else continue
                }
                queue.addLast(adj)
                colors[adj] = toColor
            }
        }
    }
    return true
}

// Or equivalently, we color the node poped from the queue with opposite color.
private fun bfs(graph: Array<IntArray>, source: Int, colors: IntArray): Boolean {
    val queue = ArrayDeque<Int>()
    var toColor = 1
    queue.addLast(source)
    while (!queue.isEmpty()) {
        val size = queue.size
        repeat(size) {
            val node = queue.removeFirst()
            if (colors[node] != notVisited) {
                if (colors[node] != toColor) return false // Color conflict
                else continue // Same color
            }
            colors[node] = toColor
            graph[node].forEach { adj ->
                queue.addLast(adj)
            }
        }
        toColor *= -1 // Reverse the color
    }
    return true
}

• Time Complexity: O(V + E)
• Space Complexity: O(V) for colors.