Is Graph Bipartite?

Leetcode Problem 785: Is Graph Bipartite?

Problem Summary

Given an undirected graph with n nodes numbered from 0 to n - 1, represented as an adjacency list, determine whether the graph is bipartite. A graph is bipartite if its nodes can be partitioned into two independent sets A and B such that every edge connects a node in A to a node in B. The graph has no self-edges, no parallel edges, and may be disconnected. The number of nodes is at most 100.

Techniques

• Depth-First Search
• Breadth-First Search
• Union-Find
• Graph

Solution

function graphBipartiteDfs(graph: number[][], node: number, colors: number[]): boolean {
    const neighbors = graph[node]

    for (const neighbor of neighbors) {
        if (colors[neighbor] !== -1 && colors[neighbor] === colors[node]) {
            return false
        } else {
            if (colors[neighbor] === -1) {
                colors[neighbor] = 1 - colors[node] 
                
                if (!graphBipartiteDfs(graph, neighbor, colors)) {
                    return false
                }
            }
        }
    }

    return true
}

function isBipartite(graph: number[][]): boolean {
    const colors = Array(graph.length).fill(-1)

    for (let i = 0; i < graph.length; i++) {
        for (let k = 0; k < graph[i].length; k++) {
            if (colors[i] === -1) {
                colors[i] = 0
                const isBipartite = graphBipartiteDfs(graph, i, colors)

                if (!isBipartite) {
                    return false
                }
            }
        }
    }

    return true
};

console.log(isBipartite([[1,3],[0,2],[1,3],[0,2]])) // true
console.log(isBipartite([[1,2,3],[0,2],[0,1,3],[0,2]])) // false