Elementary Graph Algorithms - Breadth First Search

Graph problems pervade computer science, and algorithms to working with them are fundamental to the field. Hundreds of interesting computational problems are couched in terms of graphs. In this part, we touch the Breadth First Search.

Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Given a graph $G = (V, E)$ and a distinguished source vertex $s$, breadth-first search systematically explores the edges of $G$ to discover every vertex that is reachable from $s$. It computes the distance (smallest number of edges) from $s$ to each reachable vertex. [1]

Now let’s consider a real world application of the BFS algorithm. 

Treasure Island - Problem Definition

You have a map that marks the location of a treasure island. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in. There are other explorers trying to find the treasure. So you must figure out a shortest route to the treasure island. Assume the map area is a two dimensional grid, represented by a matrix of characters. You must start from the top-left corner of the map and can move one block up, down, left or right at a time. The treasure island is marked as $X$ in a block of the matrix. $X$ will not be at the top-left corner. Any block with dangerous rocks or reefs will be marked as $D$. You must not enter dangerous blocks. You cannot leave the map area. Other areas $O$ are safe to sail in. The top-left corner is always safe.

Output the minimum number of steps to get to the treasure.
e.g.
Input

$$\begin{bmatrix}
O & O & O & O \\
D & O & D & O \\
O & O & O & O \\
X & D & D & O \\
\end{bmatrix}$$


Output :Route is $(0, 0), (0, 1), (1, 1), (2, 1), (2, 0), (3, 0)$ The minimum route takes $5$ steps. 

Input: 

$$\begin{bmatrix}
O & O & O & O \\
D & O & D & O \\
O & O & O & O \\
O & D & D & O \\
O & D & X & O \\
\end{bmatrix}$$


Output : $(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (3, 3), (4, 3), (4, 2)$ or $(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 2)$ The minimum route takes $8$ steps. 

Treasure Island - Approach

We use a variant of the BFS algorithm to find the minimum distance to reach the treasure. We maintain a FIFO queue data structure to keep discovered vertices whose adjacency list is yet to be scanned. We use an array named $m$ to get hold of the $x$ and $y$ coordinate changes for each move: up, down, left and right. We have two procedures, $FIND-TREASURE$ first calculates shortest path distances in an $m \cdot n$ matrix named $d$ and the procedure $PRINT-PATH$ uses this matrix in turn to print the blocks in an optimal solution. Also note that the procedure $PRINT-PATH$ starts its job from the block where the treasure is buried, hence the treasure coordinates are passed in as an argument to the routine. The algorithms that follow describe our approach of finding the shortest path more precisely.  

**Input:** Map area represented by an $m \cdot n$ matrix     
**Output:** Minimum number of steps to reach the treasure along with the corresponding route.  
$FIND-TREASURE(G)$  
$\phantom{{}++{}}$ $rl \gets G.length$  
$\phantom{{}++{}}$ $cl \gets G[0].length$  
$\phantom{{}++{}}$ let $d$ be a $rl \cdot cl$ matrix, each entry initialized to $\infty$  
$\phantom{{}++{}}$ let $q$ be an empty FIFO queue  
$\phantom{{}++{}}$ let $m$ be an array containing the finite set of moves  
$\phantom{{}++{}}$ let $r$ be the treasures row position initialized to $-1$    
$\phantom{{}++{}}$ let $c$ be the treasures column position initialized to $-1$  
$\phantom{{}++{}}$ $q.enqueue(\{0, 0\})$  
$\phantom{{}++{}}$ $d[0][0] = 0$  
$\phantom{{}++{}}$ `while` $q$ is not empty  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $u \gets q.dequeue()$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `for` `each` $p \in m$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $i \gets u[0] + p[0]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $j \gets u[1] + p[1]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $i \ge 0$ and $i \lt rl$ and $j \ge 0$ and $j \lt cl$ and $d[i][j] == \infty$ and $G[i][j] \ne D$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $G[i][j] == X$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$  $\phantom{{}++{}}$ $r \gets i$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$  $\phantom{{}++{}}$ $c = j$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $d[i][j] \gets d[u[0]][u[1]] + 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $q.enqueue(\{i, j\})$  
$\phantom{{}++{}}$ `if` $r == -1$ and $c == -1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ throw error  
$\phantom{{}++{}}$ `print` "The minimum route takes " d[r][c] " steps."  
$\phantom{{}++{}}$ $PRINT-PATH(d, r, c, m)$  


**Input:** An $m \cdot n$ matrix containing shortest path distances calculated at step 1, $x$ and $y$ coordinates of the treasure and the finite set of moves $m$.    
**Output:** Shortest route to reach the treasure.  
$PRINT-PATH(d, i, j, m)$  
$\phantom{{}++{}}$ `if` $i == 0$ and $j == 0$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `print` "(" i ", " j ")"  
$\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $r \gets -1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $c \gets -1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $s \gets \infty$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `for` `each` $p \in m$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $k \gets i + p[0]$   
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $l \gets j + p[1]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $k \ge 0$ and $k \lt d.length$ and $l \ge 0$ and $l \lt d[0].length$ and $d[k][l] \lt s$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $r \gets k$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $c \gets l$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $s \gets d[k][l]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $r == -1$ and $c == -1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `print` "path doesn't exist"  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $PRINT-PATH(d, r, c, m)$    
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `print` "(" i ", " j ")"  


Here’s the sample implementation of the  solution to the treasure island problem along with a driver program. 

Analysis

Let $m \cdot n$ be the dimension of the map area. Each block is enqueued at most once and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, and so the total time devoted to queue operations is $O(2 \cdot m \cdot n)$. Calculation of the $d$ value takes O(1) time per entry. Thus, the calculation over all the entries in the table $d$ incurs a total cost of $O(m \cdot n)$. The overhead for initialization is $O(m \cdot n)$. Thus, the total running time of our procedure is $O(4 \cdot m \cdot n) = O(m \cdot n)$.

The $PRINT-PATH$ procedure runs in time linear in the number of blocks in the path printed. 

References

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the ...
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t...
Read more

Combining the emissions of multiple Observables together using RxJava Zip operator in a Spring Boot Micro service

Image
Introduction Well, today we are going to discuss an advanced RxJava operator called Zip. Let’s first take a look at the zip operator at a glance and then move on to a real world example that leverages the capabilities of the operator. In fact, zip is a very powerful and useful operator provided in the RxJava library. Prerequisites : Good knowledge of Java8, Functional Programming, RxJava, Spring Boot, Microservices. User Level : Advanced Since this is an advanced article, I am not going to walk you through the basics of RxJava or Spring Boot microservices. If you need to get some basic understanding of RxJava, I thoroughly recommend you to go through one of my previous blog posts [1] [2] or any other good introductory article about RxJava. If you need to learn more about Spring Boot microservices please go through some of the spring tutorials which are really comprehensive and impressive. RxJava Zip Operator Combines the emissions of multiple Observables together via a speci...
Read more