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.