Consider the following problem. You are given the maze figure below and asked to find a way to the exit with a minimum number of decisions to make (a decision is required whenever there is at least one available direction to go). At the right of the maze figure we have pointed out these critical positions and given them numbers. Also the circles coloured in cyan are the start (1) and the finish (10).
On the basis of this diagram we will draw a graph with the following rules :
- the vertices are the critical positions
- there is an edge from X to Y if we can go from X to Y by making exactly one decision
It is easy to see now that the minimum length path is 1, 3, 14, 15, 10 with 4 decisions to make (the number of edges connecting the vertices). This is because we have an overview of the maze, we know every detail about it in advance. But what if we do not ? We would never be aware of the consequences of our current decision until we make it. What would be our strategy then ?
One possibility is to gather an infinite number of people (this is for instructional purposes only) and put them in the start position of the maze.
Then everytime we are to make a decision, leave one single person in the current position and split the group into N smaller ones, where N is the number of the current possible decisions to make. These groups each go a different way and so on, until someone reaches the finish. It is clear that the path found by this group of people is of minimum length, since every group has to make only one decision at a time (the length of each step is the same for everyone) and this group made it first to the finish. Note that passing through a point that already has one person standing there is not permitted.
To reconstruct the minimum length path, let us assume that every person that is left in a certain point knows exactly the position where the group came from. For example the person in point 2 knows that the group came from the 1st position before it left him there. Now if we start with the last position of the winning group (the finish) we may go backwards as we know its previous position, and so on until we reach the start. We have now constructed the exact minimum path (in terms of decisions to make) to arrive at the finish of the maze, but in reversed order. The last operation is to reverse the path in order to find the correct one.
This is a version of Lee’s algorithm for finding the shortest path between two particular vertices in an undirected graph. But let us now concentrate on the method of traversal, which in terms of graph theory is known as Breadth First Search ( BFS in short ). I assume you already know the algorithm, it is all in the way the groups of people move from one point to another – at each step the groups separate into smaller ones, then go to the next positions and also leave a person behind. Remember it is not allowed to pass through a point with one person already standing there. This separation process continues until there are no more available positions to visit.
For a better understanding let us try and traverse the next graph starting from vertex 3 using this method. The steps are already described graphically below but let us make a few comments.
First there is a group of 5 people (which is enough for this situation) positioned in vertex 3. Then one person goes to vertex 1, one to vertex 5, two persons go to vertex 2 and one stays in 3. At the next phase of the process we clearly see that the person in vertex 1 has nowhere to go, since both its next possible positions (2 and 3) are occupied. Because 2 is smaller than 5 (considering the integer numbers order) we will search first for its available positions. The single one is vertex 4, so we leave one person in 2 and send one to 4. This seems like our last move – no person can move from its current position anymore since all are occupied.
The BFS method shows the vertices that are visited through each step of the traversal process.
In the example above we would get the following listing :
3, 1, 2, 5, 4
To implement this method in C++ we will use a queue to store the current position of each group of people and search for their available directions to go. Also we will use an additional boolean array to store information about each vertex (whether it is occupied or not) :
visited [ k ] = true if position k is occupied, otherwise visited [ k ] = false
The Breadth First Search pseudocode looks like this (assuming x is the first node to start the traversal) :
for (all vertices 1<= i <= n) do visited [ i ] = false ADD x to Queue visited [ x ] = true while (Queue is not empty) do extract information from the Queue to variable k display k for (all vertices 1<= i <= n) do if (visited[ i ] == false AND there is an edge between k and i) then ADD i to Queue visited [ i ] = true end if end while
The minimum length path algorithm is very similar to this. The only difference is that we need to store the position from which every person came in the traversal process in order to reconstruct the path. We will achieve this using an array and displaying it in reverse order at the end of the traversal. Below you will find the listing that implements both BFS and the minimum path algorithm by encapsulating them inside the Graph class. We have also implemented a Queue class since both use this type of container.
#include <iostream>
using namespace std;
struct node {
int info;
node *next;
};
class Queue {
public:
Queue();
~Queue();
bool isEmpty();
void add(int);
int get();
private:
node *first, *last;
};
class Graph {
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
// adds the (x, y) pair to the edge set
void addEdge(int x, int y);
// performs a Breadth First Search starting with node x
void BFS(int x);
// searches for the minimum length path
// between the start and target vertices
void minPath(int start, int target);
private :
int n;
int **A;
};
Queue::Queue() {
first = new node;
first->next = NULL;
last = first;
}
Queue::~Queue() {
delete first;
}
bool Queue::isEmpty() {
return (first->next == NULL);
}
void Queue::add(int x) {
node *aux = new node;
aux->info = x;
aux->next = NULL;
last->next = aux;
last = aux;
}
int Queue::get() {
node *aux = first->next;
int value = aux->info;
first->next = aux->next;
if (last == aux) last = first;
delete aux;
return value;
}
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
bool Graph::isConnected(int x, int y) {
return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y) {
A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::BFS(int x) {
Queue Q;
bool *visited = new bool[n+1];
int i;
for (i = 1; i <= n; ++i)
visited[i] = false;
Q.add(x);
visited[x] = true;
cout << "Breadth First Search starting from vertex ";
cout << x << " : " << endl;
while (!Q.isEmpty()) {
int k = Q.get();
cout << k << " ";
for (i = 1; i <= n; ++i)
if (isConnected(k, i) && !visited[i]) {
Q.add(i);
visited[i] = true;
}
}
cout << endl;
delete [] visited;
}
void Graph::minPath(int start, int target) {
Queue Q;
int i, p, q;
bool found;
struct aux { int current, prev; };
aux *X = new aux[n+1];
int *Y = new int[n+1];
bool *visited = new bool[n+1];
for (i = 1; i <= n; ++i)
visited[i] = false;
Q.add(start);
visited[start] = true;
found = false;
p = q = 0;
X[0].current = start;
X[0].prev = 0;
while (!Q.isEmpty() && !found) {
int k = Q.get();
for (i = 1; i <= n && !found; ++i)
if (isConnected(k, i) && !visited[i]) {
Q.add(i);
++q;
X[q].current = i;
X[q].prev = p;
visited[i] = true;
if (i == target) found = true;
}
++p;
}
cout << "The minimum length path from " << start;
cout << " to " << target << " is : " << endl;
p = 0;
while (q) {
Y[p] = X[q].current;
q = X[q].prev;
++p;
}
Y[p] = X[0].current;
for (q = 0; q <= p/2; ++q) {
int temp = Y[q];
Y[q] = Y[p-q];
Y[p-q] = temp;
}
for (q = 0; q <= p; ++q)
cout << Y[q] << " ";
cout << endl;
cout << "Length = " << q-1 << endl;
delete [] visited;
delete [] X;
delete [] Y;
}
Let us now write two separate functions, one that traverses the previously presented graph starting from vertex 3 (the same as in the example) and one that finds the minimum length path in the maze described at the beginning of this article. Their names are Traversal() and Maze() respectively. Running the program will generate identical results with the ones we have already calculated.
void Traversal() {
Graph g(5);
g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4);
g.addEdge(3, 5); g.addEdge(4, 5);
g.BFS(3);
}
void Maze() {
Graph f(15);
f.addEdge(1, 2); f.addEdge(1, 3); f.addEdge(2, 4);
f.addEdge(3, 14); f.addEdge(4, 5); f.addEdge(4, 6);
f.addEdge(5, 7); f.addEdge(6, 13); f.addEdge(7, 8);
f.addEdge(7, 9); f.addEdge(8, 11); f.addEdge(9, 10);
f.addEdge(10, 12); f.addEdge(10, 15); f.addEdge(11, 12);
f.addEdge(13, 14); f.addEdge(14, 15);
f.minPath(1, 10);
}
void main() {
Traversal();
cout << endl;
Maze();
}
You may use the addEdge method similarly to create your own graphs and then traverse them using the BFS function or find a minimum path between two vertices using the minPath function.