Why is Graph Theory so amazing? - part 3 - BFS, bipartite graphs

In the previous article, we looked into one type of graph traversal - depth first search, which works by starting from a root node, and visit every one of its neighbours recursively.

Today, we will explore another type of graph traversal - breadth first search (or BFS, for short).

Breadth-First Search - Analysis & Why It Matters

As opposed to its sibling, BFS is not a recursive algorithm - it will visit nodes in a First In, First Out manner, by using a queue data structure.

The Queue Data Structure

A queue data structure is a sequential collection of entities (we can visualise it as an array, for simplicity, although it can be implemented in more ways) that has 2 fundamental operations:

1. append an entity to the end of the queue
2. pop an entity from the start of the queue

If the queue is represented properly in memory, both of these operations have an O(1) time complexity. Naturally, the space complexity of a queue is O(n). As the name suggests, it is very similar to a real-life queue.

Back to the algorithm, it works by first appending the root node to the queue and marking it as visited. Then, as long as there are nodes in the queue, we start popping elements from the front. After popping a node, we put all of its unvisited neighbours in queue, we mark them as visited, and then continue with the popping.

By and large, the algorithm works by following these steps:

1. let i be the root node of the traversal; append i to the queue and mark it as visited.
2. while the queue is not empty:
   • pop the first element in the queue, let it be j.
   • mark j as visited.
   • loop through the neighbours of j, push each of them to the queue if they are not yet visited, and mark them as visited.

Analysing the time complexity of BFS yields the same results as with the DFS. Let G be a graph with N nodes and E edges.

• if G is represented by using an adjacency matrix, the time complexity of the algorithm is O(N*N)
• if G is represented by using adjancency lists, the complexity of the algorihm is O(N+E).

So, again, we see an applicability for each of the graph representation methods.

Now, let's see a Python implementation of the BFS algorithm. We will be using the deque collection from the standard Python library for constant operations on the queue and the adjacency_list.py for the class definition and we will run the algorithm on last week's graph.

The output of the snippet above is "1 2 3 4".

Bipartite Graphs

A bipartite graph, also called a bigraph, is a graph whose nodes can be divided into 2 disjoint sets, let them be U and V, so that every edge in the graph connects a node from U to a node from V.

For example, the graph above is bipartite, with U = (1, 2, 6) and V = (3, 4, 5, 7). Do note that a bipartite graph is not necessarily connected (there is not necessarily a path between any two nodes).

Now, let's see how we can use BFS to determine whether a given graph is bipartite or not. For this, we will try to traverse the graph and construct U and V as we go. For simplicity, we can color the nodes of U with red and the nodes of V with green.

The colouring, and implicitly the set choices, are not unique, as we can either choose to put node 6 in U or in V.

Let's see how we can determine if the first connected component is a bipartite graph. We can start a BFS from 1, and colour it in red. Then, colour all of its neighbours in blue. When looking at an arbitrary node, we can colour its neighbours in the opposite color (i. e. red neighbours if the node is blue, and vice-versa). Applying such a method would construct a part of U and V, made up of only connected component of the graph.

To extend this idea to multiple connected components, we have to run multiple BF searches - we have to loop through all the nodes of the graph and, if we find an uncolored one, we have to start a traversal from there.

Let us see a Python snippet of how we can do this.

The snippet above outputs U as (1, 2, 6) and V as (3, 4, 5, 7), and concludes that the graph in the example is indeed bipartite.

Bipartite graphs can model a wide range of problems. One very practical exampling is class scheduling. If we were to take two sets, U, made up of students, and V made up of the classes they can take, we can use this bipartite graph modelling to determine which classes should not happen at the same time.

Conclusion

This week, we looked a little into what breadth-first search can do. However, its applications do not stop at bipartite graph checks - it can also be used to determine the shortest path from a node to all the others (which can be useful when trying to send packets through a network), or modified further to give the algorithm completely new behaviours.
We will continue the series next week - until then, do delight yourself with some other articles in The Magic of Computing series! Maybe you are into Fibonacci numbers, or you wanna brush up your knowledge about prime numbers?