Bipartite Graph: Algorithms, Implementation, and Properties

Bipartite graphs are a key type of graph in computer science and mathematics. They are important because they effectively show connections between two separate groups of things. For example, they can represent how employees are assigned to projects, how resources are given to tasks, or how job seekers are matched with available jobs. In all these cases, connections only go from one group to the other, never within the same group. This basic structure makes complicated problems much simpler to understand and solve using computer programs. This article will explain what bipartite graphs are, their main features, and why they’re so widely used in various fields.

What is a Bipartite Graph?

A bipartite graph, also referred to as a bigraph, is a type of graph used in data structures in computer science. The vertices in these graphs can be divided into two sets such that the vertices of different sets are connected, but no internal connections exist.

In more technical terms, a Bipartite Graph is a graph whose vertices (the ‘dots’ or ‘nodes’) can be divided into two independent sets. Let us suppose that the vertices are divided into two groups, set V₁ and set V₂, such that every edge (the ‘lines’ or ‘connections’) connects a vertex from Set V₁ to a vertex in Set V₂.

You cannot determine whether it is bipartite or not just by looking at it. You will have to visualize it using the disjoint set diagram to confirm that it is a bipartite graph.

Properties of a Bipartite Graph

The three major key elements of a bipartite graph are:

• Nodes are split into two separate sets: Nodes are divided into two distinct, disjoint sets, for example, ‘Group A’ and ‘Group B’. Here, each vertex can belong to exactly one set, and no vertex should belong to both. This is important for a graph to be bipartite.
• No edge connects nodes within the same set: This is an important rule. If you pick any two nodes that are both in ‘Group A’, there will be no line (edge) connecting them. The same applies to ‘Group B’. Connections only happen across the groups.
• Every edge goes from one set to the other: As a direct consequence of the second point, all the connections in a bipartite graph will always be between a node from ‘Group A’ and a node from ‘Group B’. You’ll never see a connection that starts and ends within the same group.

Mathematically, a graph is bipartite if and only if it contains no odd-length cycles.

• A cycle in a graph is a path that starts and ends at the same vertex, visiting other vertices along the way. Think of a loop.
• An odd-length cycle is a cycle that consists of an odd number of edges. For instance, a triangle (a cycle of 3 vertices and 3 edges) is an odd-length cycle. A square (4 vertices, 4 edges) is an even-length cycle.

What is a Complete Bipartite Graph?

In a complete bipartite graph, every node in the first set (V1) is connected to every node in the second set (V2). To create such a graph, we will connect all the nodes from the V₁ set to every node in the V₂ set.

How to Identify a Graph that is Bipartite

To determine if a graph is bipartite, you should partition its vertices into two disjoint sets such that no edge connects two vertices within the same set. To check if a graph is bipartite, we typically use graph traversal techniques like:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Both methods involve a coloring scheme, where we attempt to color the graph using two colors in such a way that no two adjacent nodes share the same color.

Coloring Method Explanation

• First, you will color each node in the graph one of two colors, say 0 and 1. Using these two colors, you will partition the graph into two sets to confirm if it follows the properties of a bipartite graph or not.
• You will perform the above procedure with any unvisited node in the graph. You will color this node the first color, e.g., color 0, assign it as the start node, and explore its connected neighbors.
• You will explore all the nodes that are direct neighbors of your starting node. The immediate neighbors will be given opposite colors to your start node, and hence will be colored 1. That way, you can satisfy the definition of bipartite coloring.
• If a node is colored the same as one of its neighbors, a conflict occurs. This indicates the graph is not bipartite and may contain an odd-length cycle.
• You will continue performing this coloring and conflict detection with all unvisited nodes in the graph until all connected components of the graph have been visited. Using this method confirms that you are correctly processing disconnected graphs.

Now that you are aware of the coloring method, let us look at the two algorithms used to identify whether a graph is bipartite or not.

BFS Algorithm to Check if a Graph is Bipartite

Step 1: Create a color array and initialize all nodes with -1 (unvisited).

Step 2: For each unvisited node:

• Assign color 0 and add it to the queue.
• While the queue is not empty:
  • Dequeue the current node.
  • For each of its neighbours:
    • If not colored, color it with the opposite color and enqueue it.
    • If it is already colored and has the same color as the current node, return False.

Step 3: If no conflicts are found, return True (Graph is Bipartite).

DFS Algorithm to Check if a Graph is Bipartite

Step 1: Create a color array and initialize all nodes with -1.

Step 2: Define a recursive DFS function:

• Color the current node.
• For each neighbour:
  • If unvisited, recursively call DFS with the opposite color.
  • If already been visited and has the same color, return False.

Step 3: Call DFS for all components.

Step 4: If no conflict, return True.

Is Graph Bipartite? – Dry Run

We have discussed the algorithms that can be used to find whether a graph is bipartite or not. Now, to better understand how the algorithms work, let us take a problem statement. We will take a simple graph (given in the picture below) and dry run the DFS algorithm to understand its working and find out ‘Is Graph Bipartite?’. While Breadth-First Search (BFS) is often the go-to for two-coloring a graph, DFS is equally capable and offers a different perspective on graph traversal.

The graph we will use for this example is:

In the first step, we will create an array called ‘color’ of size V (where V is the number of vertices), and assign ‘U’ (for Uncolored) to all of them. Note that we will start indexing the array starting from 1

We start with: color[] = {U, U, U, U, U}. Here, U means Uncolored. All nodes in the graph are uncolored at the beginning.

We will implement a recursive method that we will name dfs(node, c_color), and we will use it to confirm whether or not the graph is bipartite.

This function will do the following:

1. It will color the current node with c_color (0 or 1).
2. It will then check every neighboring node (connected nodes), not just the DFS traversal path. If a neighbor is not colored, it will call itself (recursively) to color the neighboring node with the opposite color.
3. If the neighbor is colored and has the same color as the current node, then we have a conflict, and it is not a bipartite graph.

The goal is to color the graph using two colors (red and green) so that no two connected nodes share the same color.

Step-by-Step Dry Run:

1. Start at Node 1: We begin the coloring process by selecting Node 1 and assigning it the Red color. You can choose any Node, but for simplicity, we chose the root node, that is, Node 1.
   color[] = {R, U, U, U, U}
2. Explore from Node 1: Now, we will traverse the nodes and color them. Let us first look at Node 1’s neighbors. Node 2 is one of the neighbors of Node 1 and is currently uncolored. Since Node 1 is Red, we assign Node 2 an alternate color, which, in this case, is Green.
   color[] = {R, G, U, U, U}
3. Explore from Node 2: We now move to Node 2 and examine its neighbors next.
   • Node 2’s neighbors are Node 1 and Node 4.
   • Node 1 is already colored Red. This is the opposite color of Node 2 (Green), so there’s no conflict here.
   • Node 4, on the other hand, is uncolored. Since Node 2 is Green, we assign Node 4 the Red color.
     color[] = {R, G, U, R, U}
4. Explore from Node 4: We move to Node 4.
   • Node 4’s only neighbor is Node 2.
   • Node 2 is already colored Green. This is the opposite color of Node 4 (Red), so there’s no conflict.
   • All neighbors of Node 4 have been checked. We’ve explored this path fully, so we complete the processing for Node 4 and backtrack to Node 2.
5. Backtrack to Node 2: All neighbors of Node 2 have now been processed (either colored or checked for conflicts). We complete processing for Node 2 and backtrack to Node 1.
6. Continue exploring from Node 1: We’re back at Node 1, and its next uncolored neighbor is Node 3.
   • Node 3 is uncolored. Since Node 1 is Red, we assign Node 3 the Green color.
     color[] = {R, G, G, R, U}
7. Explore from Node 3: We now move to Node 3.
   • Node 3’s neighbors are Node 1 and Node 5.
   • Node 1 is already colored Red. This is the opposite color of Node 3 (Green), so there’s no conflict.
   • Node 5 is uncolored. Since Node 3 is Green, we assign Node 5 the Red color.
     color[] = {R, G, G, R, R}
8. Explore from Node 5: We move to Node 5.
   • Node 5’s only neighbor is Node 3.
   • Node 3 is already colored Green. This is the opposite color of Node 5 (Red), so there’s no conflict.
   • All neighbors of Node 5 have been checked. We complete processing for Node 5 and backtrack to Node 3.
9. Backtrack to Node 3: All neighbors of Node 3 have now been processed. We complete processing for Node 3 and backtrack to Node 1.
10. All neighbors of Node 1 have been processed, and crucially, all reachable nodes in the graph have been colored without encountering any conflicts. This means no two adjacent nodes ever received the same color.

This was a dry run where we used the algorithm to prove that the given graph is bipartite.

Implementing DFS to Check if a Graph is Bipartite

Now that we have understood how BFS and DFS algorithms can be used to check whether the graph is bipartite or not, we will implement them using the DFS algorithm in C++, Java, and Python.

Implementation in C++

Code:

Output:

Explanation: In the C++ code, there exists a Graph class that has an adjacency list to represent the edges within the graph. The recursive DFS function thereby colors each node two different colors (red and white), and continues with its neighbors, checking for conflicts. A conflict occurs when two adjacent nodes have the same color. When the function sees this conflict of two adjacent nodes inheriting the same color, the DFS stops, and the graph is declared as not bipartite.

Implementation in Java

Code:

Output:

Explanation: In the Java code, there is a graph data structure that executes a Depth-First Search (DFS) algorithm to check to see if the graph class is bipartite. This is done through traversing the graph, coloring the node with color 1, followed by the adjacent nodes with color 2, then coloring the adjacent nodes of those adjacent nodes with color 1, checking all neighbor nodes for color conflict.

Implementation in Python

Code:

Output:

Explanation: We use adjacency lists to represent a graph data structure. In this example, we use a Graph class to implement a graph with connections using an adjacency list. We also implement a depth-first search (DFS) function to check if it is “bipartite”. If the graph is bipartite, then nodes can be divided into two disjoint sets such that edges can only connect nodes in different sets and not the same set. The DFS will color the nodes using two colors and will return False as soon as it finds an adjacent node with the same color, indicating the graph is not bipartite.

Master Python – Get Certified & Career-Ready

Enroll Now and launch your journey to becoming a proficient Python developer!

Explore Program

Bipartite Graph vs Non-Bipartite Graph

Real-World Applications of Bipartite Graph

Let’s consider a few use cases and real-world applications of a bipartite graph to understand its importance better:

1. College Course Allocation

In a college course allocation system, the two sets of nodes can represent students and courses. Such graphs help model how colleges can match students to available courses efficiently. They are designed keeping in mind the capacity constraints. For example, the graph can represent which students wish to register for which classes and help assign them to courses without overlaps or conflicts.

2. Job Matching Platforms

In this example, the two sets of nodes represent job seekers and job listings. It shows how applicants apply for different positions and how companies select suitable candidates, effectively modeling the process of matching people to jobs efficiently.

3. Movie Recommendation Systems

In this example, the two sets of nodes represent users and movies. The graph shows which movies each user has watched or rated. By analyzing these connections, recommendation algorithms can suggest new or similar movies to users, efficiently personalizing their viewing experience.

4. E-Commerce Product Recommendations

In the e-commerce industry, two sets, customers and products, can be used to model interactions. Each customer is linked to the products they have purchased or viewed, allowing recommendation algorithms to suggest related or new items, enhancing personalization and boosting sales.

Conclusion

In this article, we looked at the famous bipartite graph and how to implement it in various programming languages such as Java, Python, and C++. We also explained this algorithm through a comprehensive dry run so that the logic is clear to you, even if you are a complete beginner. Finally, we looked at the real-world examples or issues that are solved by this graph and how it is especially used in recommendation systems. Graphs are one of the core topics asked in interviews, and you must learn them thoroughly.

Learn what a Hamiltonian graph is and how it works in this blog.

Bipartite Graph – FAQs