September 14, 2016

# Algorithm: Breadth-First Search

## Recall: Graphs

Graph $$G = (V,E)$$

• $$V$$ = set of vertices (arbitrary labels)

• $$E$$ = set of edges, i.e., vertex pairs $$(v,w)$$

ordered pair $$\Rightarrow$$ directed edge of graph

unordered pair $$\Rightarrow$$ undirected ## Graph Search

Exploring a graph, e.g.:

• find a path from start vertex $$s$$ to a desired vertex
• visit all vertices or edges of graph, or only those reachable from $$s$$

### Applications

There are many:

1. web crawling (how Google finds pages)
2. social networking (Facebook friend finder)
3. network broadcast routing
4. garbage collection
5. model checking (finite state machine)
6. checking mathematical conjectures
7. solving puzzles and games

### Pocket Cube

Consider a $$2 \times 2 \times 2$$ Rubik’s cube

Configuration Graph:

• vertex for each possible state
• edge for each basic move (e.g. 90 degree turn) from one state to another
• undirected: moves are reversible

Diameter (“God’s Number”):

• $$11$$ for $$2 \times 2 \times 2$$
• $$22$$ for $$3 \times 3 \times 3$$
• $$\Theta \left(\dfrac{n^2}{\lg{n}}\right)$$ for $$n \times n \times n$$ [Demaine, Demaine, Eisenstat Lubiw Winslow 2011] ## Graph Representations (Data Structures)

### Adjacency Lists

Array $$Adj$$ of $$|V|$$ linked lists.

• For each vertex $$u \in V$$, $$Adj[u]$$ stores $$u$$’s neighbors, i.e., $$\left\{ v \in V | (u,v) \in E \right\}$$ $$(u,v)$$ are just outgoing edges if directed
• in Python: $$Adj$$ = dictionary of list/set values; vertex = any hashable object (e.g., int, tuple)
• Advantage: multiple graphs on same vertices ### Adjacency Matrix

Assume that vertices are numbered $$1, 2, \dots, |V|$$ in some arbitrary manner. The Adjacency-Matrix representation of a graph $$G$$ consists of a $$|V| \times |V|$$ matrix $$A = (a_{ij})$$ such that

$$a_{ij} = \begin{cases}\begin{array}{ll} 1, & \text{if} (i,j) \in E \\ 0, & \text{otherwise} \end{array}\end{cases}$$ The adjacency matrix of a graph requires $$\Theta(V^2)$$ memory, independent of the number of edges in the graph.

Observe the symmetry along the diagonal of the adjacency matrix above. Since in an undirected graph, $$(u, v)$$ and $$(v, u)$$ represent the same edge, the adjacency matrix $$A$$ of an undirected graph is its own transpose: $$A = A^\mathrm{T}$$. In some applications, it pays to store only the entries on and above the diagonal of the adjacency matrix, thereby cutting the memory needed to store the graph almost in half.

### Representation Tradeoffs

Space:

• Adjacency lists uses one node per edge, and two machine words per node. So space is $$\Theta(Ew)$$ bits ($$w$$ = word size).
• Adjacency matrix uses $$V^2$$ entries, but each entry can be just one bit. So space can be $$\Theta(V^2)$$ bits.

Time:

• Add an edge: both data structures are $$O(1)$$.
• Find if there is an edge from $$u$$ to $$v$$: matrix is $$O(1)$$, and adjacency list must be scanned.
• Visit all neighbors of $$v$$ (very common): matrix is $$\Theta(V)$$, and adjacency list is $$O(\mathrm{neighbors})$$. This means BFS will take $$O(V^2)$$ time if we use adjacency matrix representation.
• Remove an edge: similar to find and add.

The adjacency list representation provides a compact way to represent sparse graphs – those for which $$|E|$$ is much less than $$|V^2|$$ – it is usually the method of choice. We may prefer an adjacency matrix representation, however, when the graph is dense – $$|E|$$ is close to $$|V^2|$$ – or when we need to be able to tell quickly if there is an edge connecting two given vertices.

## Breadth-First Search

Explore graph level by level from $$s$$

• level $$0$$ = $${s}$$

• level $$i$$ = vertices reachable by path of $$i$$ edges but not fewer • build level $$i > 0$$ from level $$i - 1$$ by trying all outgoing edges, but ignoring vertices from previous levels

### Breadth-First Search Algorithm

Breadth first search (BFS) uses a queue to perform the search. A queue is a FIFO (first-in first- out) data structure. When we visit a node and add all the neighbors into the queue, then pop the next thing off of the queue, we will get the neighbors of the first node as the first elements in the queue. This comes about naturally from the FIFO property of the queue and ends up being an extremely useful property. Even though the implementation shown in the following code does not use a queue explicitly, it still maintains the FIFO order of visiting the nodes.

BFS(V, Adj, s):
level = {s: 0}
parent = {s: None}
i = 1
frontier = [s]                  # previous level, i - 1
while frontier:
next = []                   # next level, i
for u in frontier:
for v in Adj[u]:
if v not in level:  # not yet seen
level[v] = i    # = level[u] + 1
parent[v] = u
next.append(v)
frontier = next
i += 1 ### Analysis

Vertex $$V$$ enters next (and then frontier)

• only once (because $$\text{level}[v]$$ then set)
• base case: $$v = s$$

$$\Rightarrow Adj[v]$$ looped through only once

Time: $$\displaystyle\sum _{v \in V} |Adj[v]|= \begin{cases} \begin{array}{ll} |E|, &\text{for directed graphs} \\ 2|E|, & \text{for undirected graphs} \end{array} \end{cases}$$
$$\Rightarrow O(E)$$ time

$$O(V + E)$$ (linear time) to also list vertices unreachable from $$v$$ (those still not assigned level)

## Exercise: UVA 11624

### Introduction

Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze.

Given Joe's location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it. Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square that is on fire. Joe may exit the maze from any square that borders the edge of the maze. Neither Joe nor the fire may enter a square that is occupied by a wall.

### Input

The first line of input contains a single integer, the number of test cases to follow.

The first line of each test case contains the two integers $$R$$ and $$C$$, separated by spaces, with $$1 \le R, C \le 1000$$. The following $$R$$ lines of the test case each contain one row of the maze. Each of these lines contains exactly $$C$$ characters, and each of these characters is one of:

• #, a wall
• ., a passable square
• J, Joe's initial position in the maze, which is a passable square
• F, a square that is on fire

There will be exactly one J in each test case.

### Output

For each test case, output a single line containing 'IMPOSSIBLE' if Joe cannot exit the maze before the fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.

### Sample Input

2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F


### Sample Output

3
IMPOSSIBLE


### Analysis and Solution

Apparently, BFS for only one time can't satisfy our requirement. If we BFS aimed at John's move, with John moving to another square, the fire may spread vertically and horizontally. One square of fire will spawn a sub-fire, so many squares will be occupied by fire (the number square of fire is uncountable) shortly after John's initial move. It's arduous to breadth-first search where each element in one frontier (John's possible moves) has to cope with various variable limitations (spreading fire).

After analyzing, we can safely get the correct solution:

• Firstly, BFS fire's spreading path and preprocess the time every possible square getting fired.
• Then, BFS John's escaping plan using preprocessed fire time. For every possible square, only when the time John reaching it is less than the time it getting fire, it's passable and the corresponding step can be pushed to the search queue.

Here's my code:

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct pos {
int x;
int y;
int step;
};

int N, n, m;
constexpr int max_n = 1005;
constexpr int inf = 0x3f3f3f3f;

char map[max_n][max_n];
bool visited[max_n][max_n];
int firetime[max_n][max_n];
constexpr short dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
queue<pos> q;
pos john, fire;

bool check(pos p) {
if (p.x >= 0 && p.y >= 0 && p.x < n && p.y < m) {
return true;
}
return false;
}

void clean(queue<pos> &q) {
while (!q.empty()) {
q.pop();
}
return ;
}

int main(void) {
scanf("%d", &N);

while (N--) {
bool solved = false;
scanf("%d %d", &n, &m);
clean(q);
memset(visited, false, sizeof(visited));
memset(firetime, inf, sizeof(firetime));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf(" %c", &map[i][j]);
if (map[i][j] == 'J') {
john.x = i;
john.y = j;
john.step = 0;
}
else if (map[i][j] == 'F') {
fire.x = i;
fire.y = j;
fire.step = 0;
visited[i][j] = true;
firetime[i][j] = 0;
q.push(fire);
}
}
}
while (!q.empty()) {
pos temp = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
pos next;
next.x = temp.x + dir[i];
next.y = temp.y + dir[i];
next.step = temp.step + 1;
if (check(next) && !visited[next.x][next.y]
&& map[next.x][next.y] == '.') {
visited[next.x][next.y] = true;
firetime[next.x][next.y] = next.step;
q.push(next);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
printf("%d ", firetime[i][j]);
}
printf("\n");
}
memset(visited, false, sizeof(visited));
clean(q);
q.push(john);
visited[john.x][john.y] = true;
while (!q.empty()) {
pos temp = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
pos next;
next.x = temp.x + dir[i];
next.y = temp.y + dir[i];
next.step = temp.step + 1;
if (!check(next)) {
printf("%d\n", next.step);
solved = true;
goto output;
}
if (!visited[next.x][next.y]
&& map[next.x][next.y] == '.'
&& firetime[next.x][next.y] > next.step) {
visited[next.x][next.y] = true;
q.push(next);
}
}
}
output:
if (!solved) {
printf("IMPOSSIBLE\n");
}
}

return 0;
}


Update:

There's a way transmuting double BFS into single, provided by Batman. Actually, the core of this solution remains the same:

We can use a single queue containing tuples: $$(x,y,f)$$ where $$f=1$$ if element is fire, else $$0$$.

Before starting BFS, we can add all the fire elements in the queue first, followed by Joey.

• For fire elements, just see nearby cells, if they are . or J, make it F and add it to queue.
• For Joey, if he goes out of range, he is safe, else if there is a . nearby, make it J and add it to queue. If Joey can't move, chill, don't do anything.
• If Joey can't get out of the maze, then eventually, F will dominate the entire maze, and queue will become empty leading to end of BFS.

Based on MIT OpenCourseware 6.006 and 6.046j. Necessary amendments to the original text have been made.