Breadth First Search and Backtracking

This week I had a chance to look at Topcoder.com tutorial and read about BFS/Backtracking. Sometimes it is not clear if we need to use BFS or Recursion/backtracking approach to solve a given problem and the following is the BFS description from Topcoder.com

Breadth First Search (BFS):
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one. Besides this, certain ways of passing from one point to another are offered, all of them having the same cost of 1 (sometimes it may be equal to another number). Often there is given a N x M table (formed of N lines and M columns) where certain cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end point from the start one. Such tables may represent mazes, maps, cities, and other similar things. These may be considered as classical BFS problems. Because BFS complexity is in most cases linear (sometimes quadratic, or N logN), constraints of N (or M) could be high - even up to 1 million.

Having said that let me post two problems that sound somewhat similar but require different approach to solve. First question. We have a robot sitting somewhere in the matrix and we want to find the shortest path to get to a certain position. This is a kind of problem that needs BFS approach as described above. Whenever we see the shortest and the cost to move from one state to another is same, it is safe to assume that we can use BFS. As we know from graph theory, we use BFS to find the shortest path and hence we can apply BFS to solve the problem and the key to remember is that BFS requires us to use queue-like data structure. At each node, we need to enqueue the neighboring nodes for the future processing and we do this this until the queue is empty. When the queue is empty, we know that we have covered all the nodes that could be reached from the source node. Lastly, for this particular problem we want to keep the number of paths taken so far and use that to calculate the next one by simply adding one.

Second question. How do we find the possible number of paths from one node to another for a robot to take? In this problem, we do not concern the shortest path but would like to know how many paths exist from the source node to the destination node. This is somewhat simple problem in that we just need to recursively call ourselves until we get to the destination. For this particular problem, we need backtracking because we want to keep track of states between each call and thus, we will need to use backtracking technique.
Here is the better description of backtracking from Topcoder.com:

Backtracking:
This technique may be used in many types of problems. Just take a look at the limits (N, M and other main parameters). They serve as the main hint of a backtrack problem. If these are very small and you haven't found a solution that's easier to implement - then just don't waste your time on searching it and implement a straight-forward backtracking solution. 

Usually problems of this kind ask you to find (similarly to Brute Force):

1. Every possible configuration (subset) of items. These configurations should respect some given rules.
2. The "best" configuration (subset) that respects some given rules.

What does that mean? It means that we do not want to explore the path that we have already visited. In other words, we keep the states so far and add the next route and try the next route that's available. Why? In the next move, we normally want to know where we have visited to make a decision. However, when we come back from the next move, we want to take out the next move we just added and add another route that we have not tried yet.

Again, it is possible that the question may ask to calculate the shortest path but the cost for each move differs. For Backtracking problem, it normally asks for finding all the possible paths or some sorts so let us keep that in mind to differentiate.

So in conclusion, look for some keywords when we need to solve problems.
If it states the shortest path with the same cost for each move, try BFS. But if it asks us to find all possible paths or each cost differs, try to see if we can use Backtracking.

p.s. Let me add two samples: one for bfs and the other for backtracking for future reference.

• bfs sample: https://github.com/yeilho/algorithms/blob/master/shortest.cc
• backtracking sample: https://github.com/yeilho/algorithms/blob/master/bridge.cc