Graph Theory37 sections · 1633 units
Open in Course

LeetCode 785 Is Graph Bipartite? - Walkthrough

Trace example

let's trace graph = [[1,3],[0,2],[1,3],[0,2]]. Start: color = [-1,-1,-1,-1]. Node 00 is uncolored. BFS from 00: color 00 as 00. Queue: [0]. Pop 00. Neighbors: 11, 33. Both uncolored. Color 11 as 11, color 33 as 11. Queue: [1, 3]. Pop 11. Neighbors: 00, 22. 00 has color 00 (opposite of 11, good). 22 uncolored.

Color 22 as 00. Queue: [3, 2]. Pop 33. Neighbors: 00, 22. Both already colored correctly. Pop 22. Neighbors: 11, 33. Both already colored correctly. No conflicts. Return true.