Breadth First Search (BFS)
Let us first discuss the BFS implementation using adjacency matrix representation. In this method we consider a matrix of vertices which contains the relationship information in the matrix i.e., if a vertex u is connected to vertex v, there will be an edge/relationship at matrix[u][v] and it might be bidirectional or unidirectional weighted or unweighted directed depending up the need of the problem.
Code Implementation:
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *adjMatrixOfGraph(){
int i,u,v;
Graph *G = new Graph;
// cout<<"Enter no. of Vertices ";
cin>>G->V;
//cout<<"Enter no. of Edges ";
cin>>G->E;
G->Adj = new int*[G->V];
for(int j = 0;j<G->V;j++)
G->Adj[j] = new int[G->V];
for(int u = 0 ;u<G->V;u++)
for(int v = 0;v<G->V;v++)
G->Adj[u][v] = 0;
for(int i = 0;i<G->E;i++)
{
//Undirected Graph
//cout<<"Enter edge pair: _%d_%d_ ";
//for directed graph adj(u,v) gives only the edge u->v
cin>>u>>v;
G->Adj[u][v] = 1;
G->Adj[u][v] = 1;
}
return G;
}
Space Complexity – where V is the number of vertices.
Now, using this in Breadth First Search (BFS) we implement the following code:
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *createAdjMatrix(int V,int E) {
struct Graph* G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;i<G->V;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;j<G->V;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;i<G->E;i++)
{
int u,v;
cin>>u>>v;
G->Adj[u][v] = 1;
G->Adj[v][u] = 1;
}
return G;
}
void BFS(struct Graph* G,int u,bool* visited){
queue<int> q;
q.push(u);
visited[u] = true;
while(!q.empty()){
int currentVertex = q.front();
q.pop();
cout<<currentVertex<<" ";
for(int i = 0;i<G->V;i++)
{
if(i==currentVertex)
continue;
if(!visited[i] && G->Adj[currentVertex][i])
{
q.push(i);
visited[i] = true;
}
}
}
}
void BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;i<G->V;i++)
visited[i] = false;
for(int i = 0;i<G->V;i++)
if(!visited[i])
BFS(G,i,visited);
}
Now when we have done with the basic requirements let us see the approach of solving the problem. The idea is to traverse the graph nodes in BFS fashion and as the graph is unweighted/uniformly weighted we can use the Breadth First Search Algorithm easily to find the shortest path to the destination node from source node/cell.
We store the distance in the queue for particular nodes and keep on updating the node’s neighbour’s distance if the current distance is smaller than the previous distance and hence at the end of the whole BFS traversal we will have the shortest distance stored in the destination node.
Let us see the code implementation:
#include<bits/stdc++.h>
using namespace std;
struct node
{
int v;
int dist;
};
int minimumSolve(int graph[], int N)
{
bool *visited = new bool[N];
for (int i = 0; i < N; i++)
visited[i] = false; // not visited
//creating a queue
queue<node> q;
visited[0] = true;
node n = {0, 0};
q.push(n);
node cell;
while (!q.empty())
{
cell = q.front();
int v = cell.v;
if (v == N-1)
break;
q.pop();
for (int j=v+1; j<=(v+6) && j<N; ++j)
{
if (!visited[j])
{
node a;
a.dist = (cell.dist + 1);
visited[j] = true;
if (graph[j] != -1)
a.v = graph[j];
else
a.v = j;
q.push(a);
}
}
}
return cell.dist;
}
// Driver program to test methods of graph class
int main()
{
// Let us construct the board given in above diagram
int N = 50;
int graph[N];
for (int i = 0; i<N; i++)
graph[i] = -1;
// Marking the Ladders
graph[4] = 21;
graph[6] = 7;
graph[12] = 25;
graph[25] = 28;
// MArking the Snakes
graph[30] = 0;
graph[12] = 8;
graph[6] = 3;
graph[21] = 6;
cout << minimumSolve(graph, N);
return 0;
}
Space Complexity - O(V*V) where V is the number of vertices/nodes.
Another implementation of the Snake & Ladder game as a function is also given below –
vector<int> calculate(int row,int next_step)
{
//for flipping the dirctions in the board
int x=(next_step-1)/row;
int y=(next_step-1)%row;
if(x%2==1)y=row-1-y;
x=row-1-x;
return {x,y};
}
//vector board function
int snakesAndLadders(vector<vector<int>>& board) {
int r=board.size();
queue<int> q;
q.push(1);
int step=0;
while(!q.empty())
{
int n=q.size();
for(int i=0;i<n;i++)
{
int t=q.front();
q.pop();
if(t==r*r)return step;
for(int i=1;i<=6;i++)
{
int next_step=t+i;
if(next_step>r*r)break;
auto v=calculate(r,next_step);
int row=v[0],col=v[1];
if(board[row][col]!=-1)
{
next_step=board[row][col];
}
if(board[row][col]!=r*r+1)
{
q.push(next_step);
board[row][col]=r*r+1;
}
}
}
step++;
}
return -1;
}
Space Complexity - O(V*V) where V is the number of vertices/nodes.
Time and Space Complexity remains the same. This algorithm is very easy and fun to use as it can also be used to make a simple Snake and Ladder game for small projects. The whole code structure remains the same only the marking of the cells has to be visualised.
Check out this problem - Optimal Strategy For A Game
Frequently Asked Questions
Is C++ superior to Python?
Due to its statically typed syntax and quicker code compilation, C++ is faster than Python. Python is slower than C++ because it employs the interpreter and enables dynamic typing, which slows down compilation.
In a coding interview, is C++ allowed?
In coding interview rounds, C++ is acceptable. C++ is one of the primary programming languages used by top IT organizations for coding interviews, including Microsoft, LinkedIn, PayPal, and Amazon.
Which five C++ data types are there?
Integer, float, double, char, and boolean.
Conclusion
Hope this article helps as an aspiring developer and a programmer and it can also be used to create a small project for adding into your portfolio. To learn more, visit our library section and to explore our programming courses, you can check our out course page.
85+ registered 