Breadth-First Search Maze in C++
A breadth-first search is an algorithm for traversing or searching tree or graph data structures. At each node, the algorithm visits the children before visiting the parent.
In other words, it expands outward from its current position at each tree level rather than moving up to the parent and down to its children.
The breadth-first search is used for finding the shortest paths on graphs. It has been used to find solutions in many fields, such as artificial intelligence, computer science, mathematics, and social sciences.
Breadth-First Search Algorithm
Breadth-first search is a search algorithm that traverses the tree breadth-wise, expanding the nodes in a breadth-first manner.
The algorithm starts at an arbitrary node and expands all of its children. Then, it proceeds to do the same for each of its children, and so on.
The process terminates when it reaches a leaf node or finds a goal state.
To find the shortest path from one node to another, we need to know its distance from that node. This can be calculated by adding the edge lengths between any two nodes in the graph.
Steps to Do Breadth-First Search Maze in C++
The steps to do the breadth-first search maze in C++ are as follows:
-
Create a graph object and initialize it with edges and vertices.
-
Create a queue containing the vertices on which we want to perform a breadth-first search.
-
Initialize the queue’s front pointer as
NULL. -
Create an empty list containing the vertices on which we want to perform a breadth-first search.
-
Initialize the list’s front pointer as
NULL. -
Add the start vertex (a vertex with index 0), which is connected to itself, into the queue.
-
Add the start vertex into the list and set its parent pointer as
NULL.
When the queue becomes non-empty, we take an element from it and recursively call the breadth-first search algorithm on it until we reach an unexplored node.
Lastly, when the queue becomes empty, we reach one end of the maze and stop searching for unexplored nodes from that direction.
Example of the Breadth-First Search Maze in C++
This is an example of a breadth-first search maze in C++. The code implements the algorithm to find the shortest path from a given start node to all other nodes in a graph.
#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point {
int a;
int b;
};
struct queueNode {
Point de;
int sam;
};
bool isValid(int hori, int vert) {
return (hori >= 0) && (hori < HORI) && (vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello) {
if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b]) return -1;
bool visited[HORI][VERT];
memset(visited, false, sizeof visited);
visited[ace.a][ace.b] = true;
queue<queueNode> e;
queueNode s = {ace, 0};
e.push(s);
while (!e.empty()) {
queueNode curr = e.front();
Point de = curr.de;
if (de.a == hello.a && de.b == hello.b) return curr.sam;
e.pop();
for (int i = 0; i < 4; i++) {
int hori = de.a + horiNum[i];
int vert = de.b + vertNum[i];
if (isValid(hori, vert) && lk[hori][vert] && !visited[hori][vert]) {
visited[hori][vert] = true;
queueNode Adjcell = {{hori, vert}, curr.sam + 1};
e.push(Adjcell);
}
}
}
return -1;
}
int main() {
int lk[HORI][VERT] = {{3, 9, 2}, {4, 5, 3}, {0, 3, 0}};
Point source = {0, 0};
Point hello = {1, 1};
int sam = BFS(lk, source, hello);
if (sam != 1)
cout << "Shortest Path:" << sam;
else
cout << "Failed!!!";
return 0;
}
Click here to check the working of the code as mentioned above.
Muhammad Adil is a seasoned programmer and writer who has experience in various fields. He has been programming for over 5 years and have always loved the thrill of solving complex problems. He has skilled in PHP, Python, C++, Java, JavaScript, Ruby on Rails, AngularJS, ReactJS, HTML5 and CSS3. He enjoys putting his experience and knowledge into words.
Facebook