Is Graph Bipartite

1. Define the problem

You are given an undirected graph as an adjacency list, where graph_i holds the neighbours of node i. Return true if the graph is bipartite : that is, if the nodes can be split into two groups so that every edge goes from one group to the other, and never inside a group. Try to paint the graph in two colours . Pick an unpainted node, paint it colour A, and paint all of its neighbours colour B, then their neighbours colour A, and so on. If you ever meet a neighbour that already wears the same colour as the node you came from, the split is impossible.

Constraints

1 ≤ graph.length ≤ 100
0 ≤ graph_i.length < graph.length
No node is listed as its own neighbour
The graph may be split into several disconnected pieces

Example

Inputgraph = [[1, 3], [0, 2], [1, 3], [0, 2]]

Outputtrue

Explanation Nodes 0 and 2 can go in one group, nodes 1 and 3 in the other. Every edge joins a node from the first group to one from the second.

2. Know the words first

In plain terms

Bipartite: A graph whose nodes split into two groups with every edge crossing between the groups. Think of a graph of who played who, where nobody plays a teammate.
Two-colouring: Giving each node one of two colours so that no edge joins two nodes of the same colour. A graph is bipartite exactly when this is possible.
Breadth-first search: Exploring a graph in rings: everything one step away, then everything two steps away. A queue keeps the order right.
Component: A piece of a graph where every node can reach every other node. A graph may hold several, so the search has to start afresh from each unpainted node.

3. Visualize the solution

One cell per node, value = the colour painted on it so far

0—

1—

2—

3—

Statusinit

Four nodes in a ring, none of them painted yet.

What happens in this step

graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
colors = unpainted for all four nodes

The edges are 0-1, 1-2, 2-3 and 3-0.
That ring has an even number of nodes, which is a good sign.

Step 1 of 7

Steps to visualize

The row has one cell per node. The label is the node number and the value is its colour, or a dash if it is unpainted.
Pick an unpainted node, paint it A, and put it in the queue.
Take a node off the front of the queue and look at each of its neighbours.
An unpainted neighbour gets the opposite colour and joins the back of the queue.
A neighbour already wearing the same colour means the graph is not bipartite, and the answer is false straight away.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, value = the colour painted on it so far

0—

1—

2—

3—

Statusinit

Four nodes in a ring, none of them painted yet.

What happens in this step

graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
colors = unpainted for all four nodes

The edges are 0-1, 1-2, 2-3 and 3-0.
That ring has an even number of nodes, which is a good sign.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function isBipartite(graph) {
  const colors = new Array(graph.length).fill(0);

  for (let start = 0; start < graph.length; start++) {
    if (colors[start] !== 0) continue;

    colors[start] = 1;
    const queue = [start];

    while (queue.length > 0) {
      const node = queue.shift();

      for (const neighbor of graph[node]) {
        if (colors[neighbor] === colors[node]) {
          return false;
        }

        if (colors[neighbor] === 0) {
          colors[neighbor] = -colors[node];
          queue.push(neighbor);
        }
      }
    }
  }

  return true;
}

Time: O(n + e), where e is the number of edges
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`graph = [[1, 3], [0, 2], [1, 3], [0, 2]]`	`true`	example from the docstring, a ring of four nodes
`graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]`	`false`	a triangle hidden inside the graph makes the split impossible
`graph = [[]]`	`true`	one node with no edges, the smallest input
`graph = [[1], [0]]`	`true`	two nodes and a single edge between them
`graph = [[1, 2], [0, 2], [0, 1]]`	`false`	a plain triangle, the classic non-bipartite graph
`graph = [[1], [0], [3], [2]]`	`true`	two separate pieces, so the outer loop has to restart

Is Graph Bipartite