Breadth-First Search (BFS) In A Graph
Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph "level by
level," starting from a source node, by visiting all of its immediate neighbors before
moving on to their neighbors. It uses a queue data structure to keep track of nodes to
visit, systematically exploring the graph in a breadthward motion. BFS is essential for
finding the shortest path in unweighted graphs and other critical applications like
network broadcasting and web crawling.
How BFS Works
1. Start at a source node: Begin the traversal from a chosen starting vertex.
2. Use a queue: A queue data structure is used to manage the order of exploration.
3. Use a visited set/array: To prevent infinite loops in graphs with cycles, a mechanism
(like a visited array or set) is used to keep track of already visited vertices.
4. Enqueue the source node: The source node is added to the queue and marked as
visited.
5. Process the queue:
o While the queue is not empty, dequeue a vertex.
o Add the dequeued vertex to the result or process it as needed.
o For each unvisited neighbor of the current vertex, mark it as visited and enqueue it.
6. Repeat: Continue this process until the queue is empty, meaning all reachable nodes
have been visited.
Key Concepts and Characteristics
Level-by-Level Exploration:
Unlike Depth First Search (DFS), which goes as deep as possible, BFS explores nodes
level by level, finding the closest reachable nodes first.
Network Broadcasting: Used in networks to spread information to all connected
nodes.
Web Crawling: Explores web pages level by level, similar to how search engines
might index websites.
Data Structures:
Primarily uses a queue (FIFO - First-In, First-Out) for managing the order of vertices
and a visited array to track processed nodes.
Given a undirected graph represented by an adjacency list adj, where
each adj[i] represents the list of vertices connected to vertex i. Perform a Breadth
First Search (BFS) traversal starting from vertex 0, visiting vertices from left to right
according to the adjacency list, and return a list containing the BFS traversal of the
graph.
Examples:
Input: adj[][] = [[1,2], [0,2,3], [0,1,4], [1,4], [2,3]]
Output: [0, 1, 2, 3, 4]
Explanation: Starting from 0, the BFS traversal will follow these steps:
Visit 0 → Output: [0]
Visit 1 (first neighbor of 0) → Output: [0, 1]
Visit 2 (next neighbor of 0) → Output: [0, 1, 2]
Visit 3 (next neighbor of 1) → Output: [0, 1, 2, 3]
Visit 4 (neighbor of 2) → Final Output: [0, 1, 2, 3, 4]
Input: adj[][] = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]
Output: [0, 1, 2, 3, 4]
Explanation: Starting from 0, the BFS traversal proceeds as follows:
Visit 0 → Output: [0]
Visit 1 (the first neighbor of 0) → Output: [0, 1]
Visit 2 (the next neighbor of 0) → Output: [0, 1, 2]
Visit 3 (the first neighbor of 2 that hasn't been visited yet) → Output: [0, 1, 2, 3]
Visit 4 (the next neighbor of 2) → Final Output: [0, 1, 2, 3, 4]
What is Breadth First Search?
Breadth First Search (BFS) is a fundamental graph traversal algorithm. It begins
with a node, then first traverses all its adjacent nodes. Once all adjacent are visited,
then their adjacent are traversed.
BFS is different from DFS in a way that closest vertices are visited before others. We
mainly traverse vertices level by level.
Popular graph algorithms like Dijkstra's shortest path , Kahn's Algorithm, and Prim's
algorithm are based on BFS.
BFS itself can be used to detect cycle in a directed and undirected graph, find
shortest path in an unweighted graph and many more problems.
Applications of BFS in Graphs
BFS has various applications in graph theory and computer science, including:
Shortest Path Finding: BFS can be used to find the shortest path between two
nodes in an unweighted graph. By keeping track of the parent of each node during
the traversal, the shortest path can be reconstructed.
Cycle Detection: BFS can be used to detect cycles in a graph. If a node is visited
twice during the traversal, it indicates the presence of a cycle.
Connected Components: BFS can be used to identify connected components in a
graph. Each connected component is a set of nodes that can be reached from each
other.
Topological Sorting: BFS can be used to perform topological sorting on a directed
acyclic graph (DAG). Topological sorting arranges the nodes in a linear order such
that for any edge (u, v), u appears before v in the order.
Level Order Traversal of Binary Trees: BFS can be used to perform a level order
traversal of a binary tree. This traversal visits all nodes at the same level before
moving to the next level.
Network Routing: BFS can be used to find the shortest path between two nodes in a
network, making it useful for routing data packets in network protocols.
PROGRAM BREADTH FIRST TRAVERSAL OF A GIVEN GRAPH
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjList;
public:
Graph(int V);
void addEdge(int u, int v);
void BFS(int start);
};
Graph::Graph(int V) {
this->V = V;
[Link](V);
}
void Graph::addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // If undirected graph
}
void Graph::BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
[Link](start);
while (![Link]()) {
int node = [Link]();
[Link]();
cout << node << " ";
for (int neighbor : adjList[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
}
int main() {
Graph g(6);
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 5);
cout << "Breadth First Traversal starting from node 0: ";
[Link](0);
cout << endl;
return 0;
}
Depth-First Search (DFS) In A Graph
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible
along each branch before backtracking, similar to solving a maze. It starts at a selected
node and explores its neighbors in-depth, using a stack data structure to keep track of
the path and facilitate backtracking when a dead end is reached. The algorithm repeats
this process until all reachable nodes are visited, employing a visited array to prevent
revisiting nodes and getting stuck in cycles.
How DFS Works
1. Start at a node: Begin by selecting any node as the starting point.
2. Mark and store: Mark the starting node as visited and add it to a stack.
3. Explore neighbors: Go to an adjacent, unvisited node and repeat the process.
4. Backtrack: If there are no unvisited neighbors, pop the node from the stack and
backtrack to the previous node to explore its other neighbors.
5. Continue until empty: Continue this until the stack is empty, meaning all reachable
nodes have been visited.
Key Characteristics
LIFO Structure:
DFS uses a Last-In, First-Out (LIFO) structure, typically a stack, to manage the nodes
to visit.
Recursive Nature:
DFS can be implemented recursively, where a function calls itself to explore the next
unvisited neighbor.
Graph Traversal:
It explores one path to its end before moving on to the next, making it suitable for tasks
like finding paths or solving mazes.
Applications of DFS
Cycle Detection: DFS can be used to detect cycles in a graph.
Topological Sorting: It's a core component in algorithms for ordering tasks or
dependencies in a Directed Acyclic Graph (DAG).
Finding Connected Components: DFS can identify all nodes within a connected
component of a graph.
Solving Puzzles: Its exhaustive nature makes it ideal for solving puzzles like mazes,
where you need to explore all possible paths.
In Depth First Search (or DFS) for a graph, we traverse all adjacent vertices one by
one. When we traverse an adjacent vertex, we completely finish the traversal of all
vertices reachable through that adjacent vertex. This is similar to a depth first tree
traversal, where we first completely traverse the left subtree and then move to the right
subtree. The key difference is that, unlike trees, graphs may contain cycles (a node
may be visited more than once). To avoid processing a node multiple times, we use a
boolean visited array.
Example:
Note : There can be multiple DFS traversals of a graph according to the order in which
we pick adjacent vertices. Here we pick vertices as per the insertion order.
Input: adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]
Output: [0 1 2 3 4]
Explanation: The source vertex s is 0. We visit it first, then we visit an adjacent.
Start at 0: Mark as visited. Output: 0
Move to 1: Mark as visited. Output: 1
Move to 2: Mark as visited. Output: 2
Move to 3: Mark as visited. Output: 3 (backtrack to 2)
Move to 4: Mark as visited. Output: 4 (backtrack to 2, then backtrack to 1, then to 0)
Not that there can be more than one DFS Traversals of a Graph. For example, after 1,
we may pick adjacent 2 instead of 0 and get a different DFS. Here we pick in the
insertion order.
Input: [[2,3,1], [0], [0,4], [0], [2]]
Output: [0 2 4 3 1]
Explanation: DFS Steps:
Start at 0: Mark as visited. Output: 0
Move to 2: Mark as visited. Output: 2
Move to 4: Mark as visited. Output: 4 (backtrack to 2, then backtrack to 0)
Move to 3: Mark as visited. Output: 3 (backtrack to 0)
Move to 1: Mark as visited. Output: 1 (backtrack to 0)
PROGRAM DEPTH FIRST TRAVERSAL OF A GIVEN GRAPH
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjList;
public:
Graph(int V);
void addEdge(int u, int v);
void DFS(int start);
void DFSUtil(int v, vector<bool>& visited);
};
Graph::Graph(int V) {
this->V = V;
[Link](V);
void Graph::addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // If undirected graph
void Graph::DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int neighbor: adjList[v]) {
if (!visited[neighbor]) {
DFSUtil (neighbor, visited);
void Graph::DFS(int start) {
vector<bool> visited(V, false);
DFSUtil(start, visited);
int main() {
Graph g(6);
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 5);
cout << "Depth First Traversal: ";
[Link](0);
return 0;
}
Difference Between BFS and DFS
Parameter BFS DFS
Definition It is an It is an abbreviation for Depth First Search.
abbreviation for
Breadth First
Search.
Structure of It uses the It uses the Stack Data Structure for finding the shortest
Data Queue Data path.
Structure for
finding the
shortest path.
Speed It is It is comparatively faster than the BFS method.
comparatively
slower than the
DFS method.
Distance BFS acts better DFS acts better when the target stays farther from the
from Source when the target source.
stays closer to
the source.
Suitability for Since BFS DFS is comparatively much more suitable for the
Decision considers all of decision trees. Within a decision, it allows a user to
Tree its neighbors, it traverse further to augment that decision. If you reach a
is not very conclusion, you reach the win situation, and you stop.
suitable for the
decision trees
used in puzzle
games.
Type of List BFS operates DFS operates using the LIFO list.
using the FIFO
list.
Tracking BFS uses the DFS uses the stack to keep track of the next location
Method queue to keep that it should visit.
track of the next
location that it
should visit.
Type of It ensures a It does not ensure a shallow path solution. DFS first
Solution shallow path heads to the bottom of any subtree. Then, it backtracks.
solution. BFS
directly finds the
shortest path
that leads to a
solution.
Tree Path It traverses a It traverses a path according to the tree depth.
path according
to the tree level.
Backtracking You don’t need You need to follow a backtrack in DFS.
to backtrack in
BFS.
Loop A user can Any user can possibly get trapped in an infinite loop.
Trapping happen to get
trapped in a
finite loop.
In Case of If a user doesn’t If a user does not find any goal, it may lead to the leaf
No Goal find a goal, they node backtracking.
may have to
expand various
nodes before
they find the
solution.
Reaching You can use You might need to traverse through more edges to find
Destination BFS to find a and reach the destination vertex from your source.
Vertex single source of
the shortest path
in the case of an
unweighted
graph. It is
because, in
BFS, one can
easily reach the
vertex with a
minimum
number of
edges from the
source vertex.
Suitable BFS works DFS works better when a user can find the solutions
Vertices better when a away from any given source.
user searches
for the vertices
that stay closer
to any given
source.
Memory The amount of The amount of memory required for DFS is less than
memory that of BFS.
required for BFS
is more than that
of DFS.
Complexity The time The time complexity of BFS is also equivalent to O
of Time complexity of (V+E) when a user deploys the Adjacency List and
BFS is O (V+E) O(V^2) when the user deploys Adjacency Matrix, in
when a user which E refers to the edges and V refers to the vertices.
deploys the
Adjacency List
and O(V^2)
when the user
deploys
Adjacency
Matrix. Here, E
refers to the
edges, and V
refers to the
vertices.