An algorithm is a set of instructions that you follow to solve a problem or achieve a desired result. You can use them to solve math problems, process and analyze large amounts of data, and even automate tasks. Algorithms are used in many fields, including computer science, engineering, finance, and artificial intelligence. Algorithms can improve workflow efficiency and help you make better decisions faster. Algorithms help us make sense of the data we have. This allows you to make more informed decisions and achieve better results.
There are numerous algorithms from basic to advanced which are needful in DSA or programming, listing form searching, sorting, to complex graph-related algorithms.
Let’s discuss a few of such important algorithms in detail –
Breadth First Search (BFS)
What is BFS? Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node.
There are many ways to traverse the graph, but among them, BFS is the most used approach. It is a recursive algorithm to search all the vertices of a tree or graph data structure. BFS puts every vertex of the graph into two categories - visited and non-visited. It selects a single node in a graph and, after that, visits all the nodes adjacent to the selected node.
A standard BFS implementation puts each vertex of the graph into one of two categories:
Visited
Not Visited
The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The algorithm works as follows:
Start by putting any one of the graph's vertices at the back of a queue.
Take the front item of the queue and add it to the visited list.
Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
Keep repeating steps 2 and 3 until the queue is empty.
The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node
The complexity of the BFS algorithm
The time complexity of BFS depends upon the data structure used to represent the graph. The time complexity of the BFS algorithm is O(V+E), since in the worst case, the BFS algorithm explores every node and edge. In a graph, the number of vertices is O(V), whereas the number of edges is O(E).
The space complexity of BFS can be expressed as O(V), where V is the number of vertices.
BFS can be implemented for different scenarios, which we will discuss in the next section –
BFS Implementation for an undirected graph:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// Node class for the graph
class Node {
public:
int value;
vector<Node*> adjacent_nodes;
Node(int value) {
this->value = value;
}
void add_adjacent(Node* node) {
adjacent_nodes.push_back(node);
}
};
// BFS function
void bfs(Node* start_node) {
unordered_set<Node*> visited; // set to keep track of visited nodes
queue<Node*> q; // queue to keep track of nodes to visit
visited.insert(start_node);
q.push(start_node);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->value << " ";
for (Node* adjacent : node->adjacent_nodes) {
if (visited.find(adjacent) == visited.end()) {
visited.insert(adjacent);
q.push(adjacent);
}
}
}
}
int main() {
// Create nodes
Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
Node* node4 = new Node(4);
Node* node5 = new Node(5);
// Create edges
node1->add_adjacent(node2);
node1->add_adjacent(node3);
node2->add_adjacent(node4);
node3->add_adjacent(node4);
node3->add_adjacent(node5);
node4->add_adjacent(node5);
// Perform BFS starting from node1
bfs(node1);
return 0;
}
Explanation
Define a Node class to represent each node in the graph. Each Node has a value attribute to represent its value, and a vector of pointers to Node objects called ‘adjacent_nodes’ to represent its neighboring nodes.
Define the ‘bfs’ function which takes a Node pointer ‘start_node’ as its parameter and performs BFS starting from that node. Use an unordered set called visited to keep track of the nodes we have already visited. Use a queue of Node pointers called ‘q’ to keep track of the nodes that we need to visit.
In the main function, create the nodes and edges for the graph by calling the ‘add_adjacent’ function on each node to add pointers to its neighboring nodes.
Call the ‘bfs’ function with node1 (or any other starting node) as the parameter to perform BFS on the graph.
Also Read: Depth-first Search Algorithm
BFS Implementation for a directed graph:
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;
class Node {
public:
int value;
vector<Node*> adjacent_nodes;
Node(int value) {
this->value = value;
}
void add_adjacent(Node* node) {
adjacent_nodes.push_back(node);
}
};
void bfs(Node* start_node) {
unordered_set<Node*> visited; // set to keep track of visited nodes
queue<Node*> q; // queue to keep track of nodes to visit
visited.insert(start_node);
q.push(start_node);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->value << " ";
for (Node* adjacent : node->adjacent_nodes) {
if (visited.find(adjacent) == visited.end()) {
visited.insert(adjacent);
q.push(adjacent);
}
}
}
}
int main() {
// Create nodes
Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
Node* node4 = new Node(4);
Node* node5 = new Node(5);
// Create edges
node1->add_adjacent(node2);
node1->add_adjacent(node3);
node2->add_adjacent(node4);
node3->add_adjacent(node4);
node3->add_adjacent(node5);
node4->add_adjacent(node5);
node5->add_adjacent(node1); // This is a directed edge
// Perform BFS starting from node1
bfs(node1);
return 0;
}
Explanation
Define a Node class to represent each node in the graph. Each Node has a value attribute to represent its value, and a vector of pointers to Node objects called ‘adjacent_nodes’ to represent its ‘neighboring’ nodes.
Define the ‘bfs’ function which takes a Node pointer ‘start_node’ as its parameter and performs BFS starting from that node. Use an ‘unordered_set’ called visited to keep track of the nodes we have already visited. Use a queue of Node pointers called q to keep track of the nodes that we need to visit.
In the main function, create the nodes and edges for the graph by calling the ‘add_adjacent’ function on each node to add pointers to its ‘neighboring’ nodes.
Call the ‘bfs’ function with node1 (or any other starting node) as the parameter to perform BFS on the graph.
In the creation of edges, only add the edge from the start node to the end node since this is a directed graph. For example, to add an edge from node1 to node2, call node1->add_adjacent(node2).
During BFS, for each node, iterate through its adjacent nodes and add them to the queue if they have not been visited yet. Use the visited set to keep track of visited nodes and avoid processing them multiple times.
After visiting a node, print out its value.
Applications
To build an index by search index
For GPS navigation
Path-finding algorithms
In the Ford-Fulkerson algorithm to find maximum flow in a network
Cycle detection in an undirected graph
In minimum spanning tree