Is a Graph Bipartite? Coding Question

Introduction:

A question you may be asked when it comes to graph-theory related problems is if we can create two subgroups with each group-member having a relationship only with elements in the opposite group.

For example, we may be asked to create two teams such that each team-member likes their teammates and any rivals they have are on he other team.

When we are given such problems, it can be thought of as a bipartite graph problem.

Definition and Examples:

A graph is bipartite if it can be split into two sets such that the following rule applies:

• For each pair of vertices, (u, v), u and v must not exist in the same set if they are adjacent (there exists an edge connecting u and v).

If we were to draw out the two sets (let’s call them set RED and set BLUE), it would look like the following:

Note how any element in set RED only connects to an element in set BLUE. There is no edge from a to b for example.

To figure out if a graph is bipartite, we need to write an algorithm that separates the vertices into two sets. Luckily, this problem can be solved by reducing it to another problem.

Graph Coloring

Graph coloring is the problem of trying to find a way to color the vertices of a graph using k colors such that no two adjacent vertices are the same color.

If we want to create two sets out of the graph’s vertices such that no two adjacent vertices are in the same set, we can rethink this problem in the following way:

• Can we color our graph with just two colors.

Let’s look at the following two examples:

Example 1:

Let’s see how we can split this graph into sets RED and BLUE.

Ta-da. Note how 0 is not adjacent to 3, and (2, 1, 4) are not adjacent to one another.

Example 2:

Now, let’s look at a graph that is not bipartite.

Let’s try to color this graph.

Uh-oh. Look at the problem with vertex 3. If we give 3 red, it is adjacent to 0. If we give 3 blue, it is adjacent to (1, 2, 4). Therefore, this graph is not 2-colorable and thus, not bipartite.

Now that we have reduced and changed the way we are thinking of this problem, we can easily think up an algorithm. A way to test if a graph is k-colorable (can be colored with k different colors) is to run a Breadth-First Search (BFS).

In our BFS, we will be coloring the graph red or blue. Give our current node a color, and check if the adjacent nodes are the same color. If they have the same color, the graph is not bipartite. Otherwise, give them the alternate color (if they are not colored already) and add them to the queue. If we can color all nodes, our graph is bipartite.

The Code

Psuedocode:

First, let’s begin by initializing our variables and data-structures we will use.

graph = [adjacency list of vertices]
n = number of vertices
colors = [a list of n vertices denoting the color of each]
red, blue = the colors we will be using
queue = queue data structure

Now, onto the Breadth-First Search.

for (vertex) in range(n):
  if (colors[vertex] is red or blue):
    continue
  queue.enqueue(vertex)
  colors[vertex] = red
  while (queue is not empty):
    current = queue.dequeue()
    
    for (neighbor) in graph[current]:
      if (neighbor is same color as current):
         return false
      else if (neighbor is not colored):
         if (current is red):
           colors[neighbor] = blue 
         else:
           colors[neighbor] = red
         queue.enqueue(neighbor)
return true

And that’s the whole algorithm. We go through each node because the graph may not be strongly connected and thus, we need to check if each component is 2-colorable. If we have not visited the current node (not colored), we color it and begin a BFS from that node. If at any point two adjacent nodes are the same color, the graph cannot be bipartite. Otherwise, we color with the alternative color and continue the algorithm. If we reach the end, we know the graph is bipartite.

Real Code:

In Java, the above psuedocode would look like the following:

Time and Space Complexities:

Time Complexity:

O(V + E), where V is the number of vertices and E is the number of edges.

We go through each possible node once as we color and add it to the queue. However, we do not re-add the nodes to the queue once they have been processed so we can say we check V vertices. For every node added to the queue, we check each possible edge between it and a neighboring vertex. This results in us checking E edges.

Space Complexity:

O(V), where V is the number of vertices

For our algorithm, we use space for our colors array and queue. Our colors arrays if of size V, and our queue has at most V-1 vertices enqueued at the same time (Current node is adjacent to every other vertex, so the rest of the vertices are enqueued at this point).

Conclusion:

With this article, you hopefully gained a useful addition to your algorithms tool-belt and can now use this in solving certain programming questions.