Bipartite Graph Check Using Traversal

What is a Bipartite Graph?

Formally, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets, let's call them $U$ and $V$, such that every edge connects a vertex in $U$ to one in $V$. In simpler terms, no edge connects two vertices within the same set.

A more intuitive way to think about this is through 2-coloring. A graph is bipartite if and only if you can color all its vertices with just two colors (say, red and blue) such that no two adjacent vertices have the same color.

The following video provides an excellent introduction to this concept, showing clear visual examples of graphs that are bipartite and those that are not.

The Key Property: Odd-Length Cycles

So, what prevents a graph from being bipartite? The answer lies in its cycles. Consider a simple cycle of length 3 (a triangle). If you color the first vertex red, its neighbor must be blue. The third vertex is adjacent to both the red and blue vertices, so it cannot be colored either red or blue without violating the rule. This conflict arises because the cycle has an odd length.

This leads to a fundamental theorem in graph theory:
A graph is bipartite if and only if it has no odd-length cycles.

Linear graphs (which have no cycles) and graphs containing only even-length cycles are always bipartite. This property is the theoretical foundation for our algorithm.

The video you just started watching also explains this crucial link between bipartiteness and cycle length.

The Algorithm: 2-Coloring with BFS

Since you have a strong background in graph traversals, you can probably already see how to build an algorithm. We can use BFS (or DFS) to traverse the graph while trying to assign one of two colors to each vertex.

Here is the strategy using BFS:

1. Create a color array, initialized to a special value (e.g., -1) to indicate that no vertex has been colored yet.
2. Iterate through all vertices of the graph. If a vertex hasn't been colored, start a BFS from it. This handles disconnected graphs.
3. When starting a new BFS from a source vertex s, assign it an initial color (e.g., 0). Push it onto the queue.
4. In the BFS loop, when you dequeue a vertex v:
   • For each neighbor u of v:
     • If u is not yet colored (color[u] == -1), assign it the opposite color of v (color[u] = 1 - color[v]) and enqueue it.
     • If u is already colored, check if color[u] == color[v]. If they have the same color, you have found a conflict. This means an odd-length cycle exists, and the graph is not bipartite. You can stop and return false.
5. If the BFS completes for a component without finding any conflicts, that component is bipartite.
6. If you iterate through all components and find no conflicts, the entire graph is bipartite.

Let's read a concise description of this algorithm.

The process of detecting a conflict is shown visually in the image below. When processing the queue, node 2 is dequeued, its neighbor 4 is explored. But node 4 has already been colored from another path (via 1), and its color is the same as node 2's. This is a conflict.

To see a detailed walkthrough of this algorithm, let's return to the video. It provides an excellent step-by-step dry run using a queue and a color array.

C++ Implementation

The implementation is a straightforward extension of the standard BFS code you've already written. The main additions are the color array and the logic to handle the coloring and conflict detection.

A crucial point for competitive programming is to handle disconnected graphs correctly. Your main function should loop through all vertices from 0 to n-1 and start a new traversal only if the vertex hasn't been colored yet.

The cp-algorithms article provides a very clean and typical competitive programming implementation.

The video you watched also covers the logic for handling multiple components towards the end, which is an important pattern to recognize.

A Note on DFS

You can also use Depth-First Search to perform the 2-coloring test. The logic is very similar: you pass the expected color down the recursion. If you encounter an already-colored neighbor, you check for a conflict. For your reference, the take U forward channel also has a video on the DFS-based approach in the resource G-18. Bipartite Graph | DFS | C++ | Java. Both methods are valid, but BFS is often considered slightly more natural as its layer-by-layer expansion maps nicely to the alternating colors.

Conclusion

You have now learned a powerful application of graph traversal that allows you to determine a fundamental structural property of a graph. Bipartite graph problems appear frequently in various forms, and being able to quickly implement a 2-coloring check is an essential skill.

Key Takeaways:

• A graph is bipartite if its vertices can be partitioned into two sets such that no edge connects two vertices in the same set.
• This property is equivalent to being 2-colorable.
• The key theoretical insight is that a graph is bipartite if and only if it contains no odd-length cycles.
• We can check for bipartiteness using BFS or DFS by attempting to 2-color the graph during traversal. A conflict arises if we find an edge between two nodes that have been assigned the same color.
• It is critical to wrap the traversal logic in a loop to correctly handle disconnected graphs.

This lesson concludes our module on core traversal algorithms. You have built a strong foundation, moving from basic definitions to implementing BFS and DFS and applying them to solve problems like shortest paths, cycle detection, grid traversals, and now, bipartite checking.

In the next module, we will take a detour from graph theory to build another critical pillar for your competitive programming toolkit: Dynamic Programming (DP). We will start from the very beginning, understanding its core principles of optimal substructure and overlapping subproblems. Mastering DP is essential, as it is a prerequisite for solving many advanced graph problems, especially those on Directed Acyclic Graphs (DAGs).