Algorithm: BreadthFirst 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:
 web crawling (how Google finds pages)
 social networking (Facebook friend finder)
 network broadcast routing
 garbage collection
 model checking (finite state machine)
 checking mathematical conjectures
 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 AdjacencyMatrix 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.
BreadthFirst 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
BreadthFirst Search Algorithm
Breadth first search (BFS) uses a queue to perform the search. A queue is a FIFO (firstin 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} \\ 2E, & \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 squareJ
, Joe's initial position in the maze, which is a passable squareF
, 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 subfire, 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 breadthfirst 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[4][2] = {{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][0];
next.y = temp.y + dir[i][1];
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][0];
next.y = temp.y + dir[i][1];
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
.
orJ
, make itF
and add it to queue.  For Joey, if he goes out of range, he is safe, else if there is a
.
nearby, make itJ
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.
Copyright
Under Creative Common [AttributionNonCommercialShareAlike 4.0 International (CC BYNCSA 4.0)] License
Based on MIT OpenCourseware 6.006 and 6.046j. Necessary amendments to the original text have been made.
Subscribe to This is SXKDZ
Get the latest posts delivered right to your inbox