Learn how to test if an undirected graph is bipartite by coloring it with two colors. Simple DFS idea, commented Python code, dry run, and Big-O analysis.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n You get an undirected graph<\/strong> as an adjacency list What does the problem ask?<\/h2>\n\n\n\n
graph<\/code>.
Your job is to say true<\/strong> if you can color every node using only two colors<\/strong> such that no two connected nodes share the same color<\/strong>.
If this is impossible, return false<\/strong>.<\/p>\n\n\n\n
\n\n\n\nExamples<\/h2>\n\n\n\n
graph<\/code> (adjacency list)<\/th>Result<\/th> Reason<\/th><\/tr><\/thead> [[1,3], [0,2], [1,3], [0,2]]<\/code><\/td>true<\/strong><\/td> You can color nodes (0,2)<\/code> with color 0 and (1,3)<\/code> with color 1.<\/td><\/tr>[[1,2,3], [0,2], [0,1,3], [0,2]]<\/code><\/td>false<\/strong><\/td> Triangle (0,1,2)<\/code> forces a conflict, needs 3 colors.<\/td><\/tr>[[],[]]<\/code><\/td>true<\/strong><\/td> Two isolated nodes are always bipartite.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\nIntuition & Approach<\/h2>\n\n\n\n
\n
Bipartite means we can split nodes into two groups (colors). Adjacent nodes must land in different groups.<\/li>\n\n\n\n
Then travel through its neighbors with DFS.<\/li>\n\n\n\n\n
The graph may have many separate components, so repeat the DFS for every still-uncolored node.<\/li>\n\n\n\n
\n\n\n\nCode<\/h2>\n\n\n\n