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.

Table of Contents:

• What is a Bipartite Graph?
• Properties of a Bipartite Graph
• What is a Complete Bipartite Graph?
• How to Identify a Bipartite Graph
  • Coloring Method Explanation
  • BFS Algorithm to Check if a Graph is Bipartite
  • DFS Algorithm to Check if a Graph is Bipartite
• Is Graph Bipartite? – Dry Run
• Implementing DFS to Check if a Graph is Bipartite
• Bipartite Graph vs Non-Bipartite Graph
• Real-World Applications of Bipartite Graph
• Conclusion

What is a Bipartite Graph?

A bipartite graph, sometimes referred to as a bigraph, is a type of graph used in data structures in computer science, whose vertices can be divided into two sets such that vertices of different sets are connected in some way and there are no internal connections. Let us suppose that the vertices are divided into two groups, V₁ and V_2, and there will be no adjacent vertices in V1 or V2.

In more technical terms, a Bipartite Graph is a graph whose vertices (the ‘dots’ or ‘nodes’) can be divided into two completely separate and independent sets. Let’s call them 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₂.

As you can see, by looking at a graph, you cannot determine whether it is bipartite or not. 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 : This means that you can take all the vertices in the graph and put them into two distinct groups, say ‘Group A’ and ‘Group B’. Every vertex must belong to exactly one of these groups. There is no overlap between the groups for a bipartite graph.
• 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.

Beyond the structural definition, there is a powerful mathematical property that helps us identify bipartite graphs:

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 a bipartite graph, we will connect all the nodes from the V₁ set to every node in the V₂ set.

How to Identify a Bipartite Graph

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 and prepare to see if it is 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 you discover a neighbor who has the same color as their neighbor, this will be called a direct conflict. This conflict indicates that the graph cannot be bipartite, or there exists an odd-length cycle in this graph.
• You will continue performing this coloring and conflict detection with all unvisited nodes in the graph in a recursive manner, until all connected components of the graph have been processed. 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 a bipartite graph.

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 where we 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 all neighboring nodes (connected nodes). If it is not colored, it will call itself (recursively) to color the neighboring node with the opposite color.
3. If the neighbor is colored and is the same color as the first node, then we have a conflict, and it is not a bipartite graph.

We are basically looking to color the graph in two colors (red and green), such that connected nodes do not have the same coloring.

Step-by-Step Dry Run:

• 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}
• 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}
• 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}
• 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.

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

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. A color conflict would arise through the coloring of the node assigned in contradiction to what should be assigned with the DFS algorithm examining bipartite graphs.

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”. A bipartite graph is a graph where all nodes can be divided into two disjoint sets such that edges only connect nodes in different sets. 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

Recommendation systems, matching, and relationships between two distinct types of things are all applications that employ bipartite graphs. Let’s consider a few examples of use cases.

1. College Course Allocation

In this example, the sets of nodes were classified as ‘Students’ and ‘Courses.’ Graphs like this include bipartite graphs to illustrate how colleges can match students to courses for capacity and efficiency purposes. In this example of students and classes, a bipartite graph can show which students wish to register in which classes and can match and assign students to available classes in an appropriate manner with no overlaps or conflict.

2. Job Matching Platforms

The sets here are ‘Job Seekers’ and ‘Job Listings or Jobs’. A bipartite graph will depict a scenario where job seekers apply to jobs and companies select applicants. In other words, students will match applicants to jobs in a very efficient manner.

3. Movie Recommendation Systems

In this case, whenever a user is connected to movies they have watched or expressed a like for, this forms a bipartite graph. Then the recommendation engine will take into account how they are connected and can generate a recommendation of similar movies that the user may also like. The bipartite graph sets are ‘Users’ and ‘Movies’.

4. E-Commerce Product Recommendations

In an e-commerce environment, each customer is connected to the products they have purchased or viewed. The algorithm uses a bipartite graph to make recommendations on related or new items. The sets are distinct: ‘Customers’ and ‘Products’.

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. We briefly discussed a complete bipartite graph, which is a type of such graph and might be used in many scenarios. Finally, we looked at the real-world examples or issues that are solved by a bipartite graph and how it is especially used in recommendation systems. Graphs are one of the core topics asked in interviews, and it is important that you learn them thoroughly.

Bipartite Graph – FAQs