Introduction

Graph traversal is the process of visiting each vertex in a graph. It is like navigating through a network of nodes,

where each node represents a point of interest and edges represent the connections between them.

Different traversal algorithms have their own strategies for visiting vertices. Some algorithms, like Breadth-First

Search (BFS), explore all neighboring vertices before moving to the next level. Others, like Depth-First Search (DFS),

go as far as possible along each branch before backtracking. These methods help in solving different types of

problems, from finding the shortest path to detecting cycles in the graph.
 What is Breadth-First Search?
The Breadth-First Search is a traversing algorithm used to satisfy a given property by searching the tree or graph data
structure. It belongs to uninformed or blind search AI algorithms as it operates solely based on the connectivity of
nodes and doesn't prioritize any particular path over another based on heuristic knowledge or domain-specific
information. It doesn't incorporate any additional information beyond the structure of the search space. It is optimal for
unweighted graphs and is particularly suitable when all actions have the same cost. Due to its systematic search
strategy, BFS can efficiently explore even infinite state spaces.

Key Characteristics of BFS

The Key characteristics of BFS are as follows:
1. First-in-First-Out (FIFO): The FIFO queue is preferred in BFS because it is faster than a priority queue and maintains
the correct node order. In BFS, new nodes deeper in the tree are added to the back of the queue, while older, shallower
nodes are expanded first.
2. Early goal test: In traditional BFS, the algorithm tracks the states reached during the search. Instead of storing all
states, it keeps only those needed for an early goal test, checking if a newly generated node satisfies the goal as soon as
it's created.
3. Cost-optimal: BFS always aims to find a minimum-cost solution by prioritizing the shortest path. When it generates
nodes at depth d, it has already explored all nodes at depth d−1. So, if a solution exists, BFS will find it as soon as it
reaches the correct depth, making it a cost-optimal algorithm
 Working of BFS
BFS explores the graph level by level, starting from the source node. It visits all the
nodes at one level before moving to the next. BFS uses a queue to keep track of
nodes that need to be explored.
From the source node, BFS moves to all its direct neighbors (Layer 1), then moves
to the next layer (Layer 2), continuing until all nodes are visited.

Traversal Order:·
• Starting from node 0.
• Layer 0: Visit node 0 (source node) .
• Layer 1: Visit nodes 1, 2, 3 (neighbors of node0).
• Layer 2: Visit nodes 4, 5, 6, 7 (neighbors of nodes 1, 2, 3).
• Output: 0, 1, 2, 3, 4, 5, 6, 7.
 Advantages of BFS
The advantages of BFS are as follows:
❖ Optimal Solution - BFS is guaranteed to find the shortest path between two nodes in an unweighted
graph.
❖ Completeness - BFS is complete, meaning it will find the solution if it exists.
❖ Uniform cost search - BFS can be modified to search for the shortest path in a weighted graph by
replacing the queue data structure with a priority queue.
❖ Level-wise traversal - BFS visits all the nodes at a given level before moving to the next level. This
approach makes it useful in certain scenarios such as finding the shortest path or exploring a game
state.

Disadvantages of BFS
The disadvantages of DFS are as follows:
❖ Space complexity - BFS can be memory-intensive, especially for large graphs or trees. It needs to
store all the visited nodes in a queue data structure, which can take up a lot of memory.
❖ Time complexity - BFS can be slow for graphs with a large number of nodes or edges.
 What is Depth- First Search?
Depth-first search is a traversing algorithm used in tree and graph-like data structures. It generally starts by
exploring the deepest node in the frontier. Starting at the root node, the algorithm proceeds to search to the
deepest level of the search tree until nodes with no successors are reached. Suppose the node with unexpanded
successors is encountered then the search backtracks to the next deepest node to explore alternative paths.

Key Characteristics of DFS

In simple terms, the DFS algorithms in AI holds the power of extending the current path as deeply as possible
before considering the other options.

1.Not Cost-Optimal: DFS is not cost-optimal because it does not guarantee finding the shortest path to the goal. It
may find a solution quickly, but that path might not be the shortest or the cheapest one.

2.Stack-Based Search: DFS uses a stack to remember which nodes to explore next. When DFS visits a new node,
it adds it to the stack. It keeps going deeper by exploring neighbours. If it reaches a dead end (a node with no
more children), it backtracks by removing nodes from the stack and exploring other possible paths.

3.Backtracking Search: A variant of DFS is called backtracking search, which uses less memory. Instead of
creating all possible paths at once, it generates one child node at a time. It can also modify the current state
directly without making a new copy. This saves memory by only keeping one state and the path taken so far.
 Working of DFS
Approach: DFS explores as deep as possible along a branch before backtracking. It uses a
stack (or recursion) to keep track of nodes and back tracks when it reaches a dead end.

Starting from the source node, DFS goes deeper into the graph, visiting one branch of the
graph first before backtracking to explore others.

Traversal Order:·
• Starting from node 0.
• Visit node 0 -> Visit node 1 -> Visit node 4(deepest) ->
Backtrack to node 1 -> Visit node 5-> Backtrack to node 0
-> Visit node 2 -> Visit node 6 -> Backtrack to node 2 ->
Visit node 3 ->Visit node 7.
• Output: 0, 1, 4, 5, 2, 6, 3, 7.
 Conclusion
Graph traversal algorithms are fundamental in graph theory and computer science. They provide systematic ways to

explore graphs, ensuring that each vertex is visited in a specific order. This systematic approach helps in various

tasks like searching, pathfinding, and analyzing the connectivity of the graph.

BFS and DFS are two popular algorithms for traversing and searching graphs and trees. BFS is best suited for

situations in which the shortest path in an unweighted graph must be found, whereas DFS is best suited for situations

in which the maximum depth of a tree or graph must be found. To make an informed decision on which algorithm to

use for a given problem, it is critical to understand the differences between these two algorithms.