Graphs, their traversal and use cases – III

Hi!

In the previous posts we learned about the traversal algorithms used on graphs: DFS and BFS. I am sure you have understood the algorithm and are eager to solve some questions using those algorithms.

In this post we will discover how to use the algorithms to solve problems. We will solve today is Bicoloring.

Go ahead and take a look at the question! Try to solve it first and then continue. It is immensely important that you must try yourself first before taking a look at my approach and solution. I will walk you through the process of understanding what the question demands and how to solve it.

The assumptions given are as follows:

• no node will have an edge to itself.
• the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
• the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

If we try to think how to solve it, these statements must come to your mind:

1. Every node is connected so we can traverse to every node easily
2. Every, parent and child node pair will definitely have different colors if the graph is BICOLORABLE.
3. A node can have more than one parent and thus must satisfy the second statement for every parent for the graph to be BICOLORABLE
4. It will not be a BICOLORABLE graph if the sibling of a node is also it’s parent, that is if two nodes are connected and they have a common immediate parent

Keeping these statements in mind let’s device an algorithm:

1. Store the input in an Adjacency List or an Adjacency Matrix.
2. Traverse the map and mark the levels for each node using BFS or DFS
3. Check if two nodes of same level are connected
4. If you find no such nodes then the graph is BICOLORABLE else it is NOT BICOLORABLE.

Let’s get put our brains to work and write a program for the above algorithm! I have come up with this:

from sys import stdin 
from collections import defaultdict

while True:
    v = int(stdin.readline())
    if v > 0:
        e = int(stdin.readline())
        adj_list = [[] * v for _ in range(v)]
        for _ in range(e):
            e1, e2 = map(int, stdin.readline().split())
            adj_list[e1].append(e2)
            adj_list[e2].append(e1)
        
        queue = [[0,0]]
        clear = True
        reached = [False] * v
        heights = defaultdict(int)
        heights[0] = 0

        while queue:
            node, height = queue.pop(0)
            for n in adj_list[node]:
                if not reached[n]:
                    queue.append([n,height+1])
                    heights[n] = height+1
                    reached[n] = True

                if heights[n] == heights[node]:
                    clear = False
                    break
        if clear:
            print("BICOLORABLE.")
        else:
            print("NOT BICOLORABLE.")
    else:
        break

There can be multiple solutions to same problem so please do try solving the problem yourself and feel free to share your solutions!

I have only given you an example of how to use an algorithm to solve a problem and there are many more such questions which you can find online. Just like every muscle, your brain will also develop after you keep on brainstorming regularly. To become better at coding consistency is a major contributor so Happy Coding!