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.
 Applications of BFS
1. Pathfinding Algorithms
Breadth-First Search (BFS) is commonly used for finding the shortest path in unweighted graphs. By exploring nodes level by
level, BFS guarantees that the first time it reaches the destination, it has found the shortest possible route. Example: BFS is
useful in maze-solving, robotic movement, and route planning. For instance, in simple route navigation systems like those used
by Google Maps (when weights aren’t involved), BFS-like techniques help determine the optimal path.
2. Web Crawling
BFS is fundamental in web crawling, where pages are systematically visited based on their link depth. Starting from a root URL,
it explores all hyperlinks on a page before moving deeper into linked pages. This strategy ensures organized, level-wise data
collection and is particularly useful for building search engine indexes or extracting structured data from websites.
3. Social Network Analysis
In platforms like LinkedIn or Facebook, BFS is employed to analyze relationships, such as identifying degrees of separation,
finding mutual friends, or tracing connection paths between users. It’s also used to locate key influencers or clusters within a
network, offering insights into complex social structures by traversing user connections in a breadth-wise manner.
4. AI in Games
BFS is often used in game artificial intelligence for exploring possible states or determining optimal moves. Example: In games
like Pac-Man, BFS helps compute the shortest path for ghosts to chase Pac-Man or for Pac-Man to escape. Similarly, in puzzle-
solving games or board games like Sudoku and chess, BFS ensures a thorough and fair exploration of all possible actions.
 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.

[Link] 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.

[Link]-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.

[Link] 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.
 Advantages of DFS
❖ Memory-efficient - DFS uses less memory than BFS. Only the path from the root node to the
current node is needed.
❖ Time Efficient - For graphs with many nodes or edges, DFS may be faster than BFS. Its time
complexity is O(b^m), where b is the branching factor and m is the maximum graph depth.
❖ Depth-first search - DFS explores the deepest path first. This approach makes it useful in
certain scenarios, such as finding the maximum depth of a tree or graph.

Disadvantages of DFS
❖ Completeness - DFS is not guaranteed to find the solution if it exists. If the graph has
cycles, it may loop forever.
❖ Non-optimal solution - DFS may not find the shortest path between two nodes in an
unweighted graph. It may find a longer path before finding the shortest path.
❖ Local minimum - DFS may get stuck in a local minimum in a weighted graph.
 Applications of DFS
[Link] generation:
The Maze generation is comprised of designing a layout of passages and walls within a maze. This maze
generation makes use of a randomized approach of the Depth-first search algorithm because it leverages
the recursive method and stack. For instance, assume that the space is a large grid of cells where each cell
holds the four walls. The DFS performs by selecting any random neighbor at first that has not been visited. It
removes the wall between the two cells that are not connected and then it adds the new cell to the stack.
This process continues until there is no more solution can be generated, resulting in a complete maze.
[Link]-solving:
Puzzle-solving including Japanese nomograms can employ Depth-first search as a method for
systematically exploring possible solutions. In Japanese nomograms, DFS is utilized to explore different
combinations of filled and empty cells in the grid.
[Link] in robotics:
DFS can be employed for pathfinding in robotics, especially in scenarios where simplicity, memory efficiency,
and adaptability are important considerations.
 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.
 References
All the information is collected and curated from the following sources:

➢ [Link]

➢ [Link]

➢ [Link]

➢ [Link]

➢ [Link]