Learning applications and solving Problems with BFS.

Learn bfs from here!
Now we know Breadth-first Search. Let’s start solving problems using it.
To have a clear understanding about bfs one should solve Bi-coloring problem.

Bi-Coloring
Online Judge (Uva) 10004 – Bicoloring Please read this problem.
You’re given a graph with n nodes and L edges. You’ve to color all the nodes using only two colors. You’ve to color those nodes in such a way that no two adjacent nodes has the same color! We’ve to tell that if we can color the given graph in this way. In other words, we have to tell this graph is bi-colorable or not.
Please before moving below try to solve it yourself.

Solution:
If you understood bfs clearly you can easily solve this problem. Let’s color this graph using white and black color.
Assume we are checking for all the adjacent nodes b of node a.
We can find those nodes b in two states:

1: We haven't visited this node yet.
2: We've visited this node before.

What can we do for the first situation?
If the color of node a is white, then we will color node b with black. If the color of node a is black, then we will color node b with white. We can’t change color of node b in the second situation. Because we already colored node b with a color. So, we’ve to check if node a and node b is colored with same color! If they have the same color then bi-coloring is not possible. Because no two adjacent nodes can have same color.
How can we change our bfs code to solve this problem? Please try to do this yourself before moving below.

We can solve this problem without using a visited array! We have to color the nodes using two colors. For marking unvisited nodes we can use a third color. In this code character ‘n’ is the third color. First we’ve checked if node b is colored with ‘n’. In other word if node b is unvisited. If node b is unvisited, we are coloring node b as we need.
In the next condition we are checking if we’ve already visited this node. If it’s visited then we are checking if they are in same color. If they have the same color then we are returning false.
Our code will look like following:

while( !qu.empty() )
{
    a = qu.front();
    qu.pop();
    int sz = graph [ a ].size();
    for ( int i = 0 ; i < sz; i++ )
    {
        b = graph [ a ] [ i ];
        if ( color [ b ] == 'n' )
        {
            qu.push( b );
            
            ///Marking the child with opposite color
            if( color [ a ] == 'b' )color [ b ] = 'w';
            else color [ b ] = 'b';
        }
        else if ( color [ b ] == color [ a ] )
        {
            ///Adjacent nodes have same color. So bi-coloring not possible.
            return false;
        }
    }
}

Complete code with C++.

Now we’ve solved bi-coloring will we stop thinking about this?
Answer: Absolutely not! If you think more you will find some interesting ideas!

1: If the graph contains cycle(s) with odd length then bi-coloring is not possible for this graph.

2: We are creating two sets of nodes by coloring the nodes. One set contains the nodes colored in white. Another set contains nodes colored in black. No two nodes of the same set won’t connected by any edge. Because then two adjacent nodes will have the same color.

3: If we look at the nodes of a same component we will see that the level of the nodes can be divided into two groups. Even and Odd levels. If a node of even level colored in white then all the nodes of even levels are also colored white. Then odd level nodes are colored in black.
And if an even level node is colored in black. Then all the even level nodes are colored in black also. Then all the odd level nodes will be colored in white.

4: Using the previous observation we can solve this problem without coloring! Please try this yourself first.
For two different nodes if the distance from the source node is even and those nodes are adjacent then bi-coloring is not possible! Same goes for the odd level nodes.

How can we write the code for this?
Our bfs code will be as following:

while( !qu.empty() )
{
    a = qu.front();
    qu.pop();
    int sz = graph [ a ].size();
    for ( int i = 0 ; i < sz; i++ )
    {
        b = graph [ a ] [ i ];
        if ( !level [ b ] )
        {
            qu.push( b );
            level [ b ] = level [ a ] + 1;
        }
        else if ( level [ b ] == level [ a ] )return 1;
    }
}

Full code with C++.

Think more! You may find more interesting things!!
Now I am finishing wrting for bi-coloring.

Now we will start to solve the next problem.

A Node Too Far.
Online Judge (Uva) 336 - A Node Too Far. Please read this problem.

Don’t be afraid by reading the problem description!
Actually it is a simple problem which can be easily solved using bfs.
You are given an undirected graph containing NC edges. There can be maximum of 30 edges.
You’ve to answer some queries. For each query, you are given a node number a and an integer b. You’ve to tell that how many nodes are unreachable if you can use maximum of b edges. In other words, how many nodes have distance more than b from source node a. Before moving below please try to solve it yourself.

Solution:
There can be maximum of 30 edges. But we don’t know how many queries are there. Let’s Q be the number of queries. If we run bfs once for each query then our maximum complexity can be: O( Q*30 ).
For each query we will run a bfs to find out how many nodes we are there within the distance of b from source node a.
And our answer will be:
(Total number of nodes in the graph - Total number of visited nodes)

Very simple solution!
But we have not solved this problem completely.
There can be maximum of 30 nodes. But there have not any range for the numbering of the nodes. Suppose there is a node with the number 123456789. We can’t have any array that large to mark nodes visited or save the levels.
How can we solve this?

We can compress the values!
If you don't know how to compress please learn it from here.
Hope that you won’t have any problem to solve this problem now.

Full code with C++

We Ship Cheap.
Online Judge (Uva) 762 - We Ship Cheap. Please read this problem.

A shipping company named We Ship Cheap delivers products. They always uses the cheapest path to deliver products. You are given a source and a target city. You’ve to print the shortest path from source to target city. If there are no path you’ve to print this otherwise.
Before moving below please try to solve this yourself.

Solution:
You know how to print a path and how to compress. So, it’s look like an easy problem for you. You’re given the nodes as strings. So, now you can compress those strings into integers or you can create graph of string type. But here we’ll solve this by compressing strings. We’ll run a breadth-first search from source node. Then we will check if we’ve visited the target node. If we have not visited the target node we will output No route. Otherwise we’ll print the path. We’ve already learned to print the path. So it won’t be a problem for us.
But we’ve to be careful about few things. What is the maximum number of nodes there can be? Each node will consists of two uppercase English letter. So, there can be 26*26 nodes. One of the reason of getting wrong answer verdict in this problem is, they haven’t specified if the source node and the target node will be present in the input graph. Now we’ve to check if the source and target nodes are presented in the input graph. When we’ll solve a problem we’ve to be careful about all possible cases.
If you have not solved this problem already you can solve this now!

Full code with C++.

Breadth First Search in 2-D Grids. (Knight Moves.)
Online Judge (Uva) 439 - Knight Moves. Please read this problem.

We’ve to solve this problem for a Knight in a chess board.
You’re given a knights current position and target position. You’ve to find the number of moves required to reach the target cell. You’ve to minimize the number of moves.
A chess board consist of 8*8 grid. There are 8 rows and 8 columns. Previously we ran bfs of simple graphs. But how can we run bfs in 2D-Grid? First try yourself to solve this.

Solution:
You’re given the co-ordinate of the knight with row and column. We will assume this cell is the source node. But how can we store a position of a grid in the queue?
It’s very simple! We’ll use pair or structure.

queue < pair < int , int > > qu;

The first element will be row and the second element will be column. A knight can move in 8 directions. We’ll check the number of valid move from his current position using a Direction array. If you can’t use Direction array than you can learn it from here.
And we’ll use another 2-D array for saving levels of the nodes.
We don’t need to create a graph. While checking for valid moves, we’ll jump to the valid cells of the grid within bfs.
Now solve this problem if you have not solved it yet!

Complete code with C++.

Some problems for practice:
567 - Risk - Online Judge(Uva).
10653 - Bombs! NO they are Mines!! - Online Judge(Uva).
Rumor - Codeforces.
Peculiar apple-tree - Codeforces
Spiky Mazes - Spoj
11396 - Claw Decomposition - (Uva) Online Judge.
11080 - Place the Guards (Uva) Online Judge.
924 - Spreading the News (Uva) Online Judge.
429 - Word Transformation (Uva) Online Judge.
10009 All Roads Lead Where? (Uva) Online Judge.

Start Reading 3rd Part!
Start Reading 4th Part!