1

ABSTRACT
Graph traversal algorithms are fundamental tools in
computer science, facilitating the exploration and analysis of complex
network structures. This case study delves into the realm of graph
traversal, focusing on Breadth-First Search (BFS) and Depth-First
Search (DFS) algorithms. Through a comprehensive examination of
their principles, implementations, and applications, this study provides
insights into the versatility and significance of graph traversal
techniques.The case study begins with highlighting the importance of
graph traversal and then proceeds to explore BFS and DFS algorithms
in detail, elucidating their respective traversal strategies, time and space
complexities, and implementation techniques. Practical examples and
code snippets in Python accompany theoretical discussions, enabling
readers to grasp the concepts effectively.The study aims to provide a
solid foundation for understanding graph traversal algorithms and their
significance in algorithmic problem-solving and data processing
domains
 2

CONTENTS

1. INTRODUCTION 3

2. GRAPH TRAVERSAL ALGORITHM 4

3. BREADTH FIRST SEARCH ALGORITHM 4

4. APPLICATION OF BFS 6

5. IMPLEMENTATION OF BFS IN PYTHON 7

6. PYTHON CODE FOR IMPLEMENTING BFS 10

7. DEPTH FIRST SEARCH ALGORITHM 11

8. IMPLEMENTATION OF DFS IN PYTHON 14

9. PYTHON CODE FOR IMPLEMENTING DFS 19

10. CONCLUSION 21

11. REFERENCES 22

A J College of Science And Technology

 3

INTRODUCTION
Graph traversal is a fundamental concept in computer
science and mathematics, playing a crucial role in various applications
such as network routing, social network analysis, and data
compression. It involves visiting every vertex and edge of a graph in a
systematic way. Two primary algorithms used for graph traversal are
Breadth-First Search (BFS) and Depth-First Search (DFS).
A graph consists of a set of vertices and a set of edges that
connect the vertices. These edges may be directed or undirected, and
they can have weights. The way in which the vertices are connected
and the properties of the edges give rise to different types of graphs,
such as directed graphs, undirected graphs, weighted graphs, and cyclic
graphs.
Graph traversal algorithms are essential for solving various
problems on graphs, such as finding the shortest path between two
vertices, detecting cycles, and identifying connected components. The
choice of algorithm depends on the specific problem and the
characteristics of the graph.
In the following sections, we will delve into discussing the
importance of graph traversal in various real-world applications. We
will also examine the Breadth-First Search (BFS) and Depth-First
Search (DFS) algorithms in detail, highlighting their uses and
differences.

A J College of Science And Technology

 4

GRAPH TRAVERSAL ALGORITHM

Here, we will delve into the two primary graph traversal
algorithms: depth-first search (DFS) and breadth-first search (BFS).
We will provide a step-by-step explanation of how these algorithms
work, their differences, and the scenarios in which they are most
effectively used. This section will also include visual representations of
the algorithms in action, highlighting how they navigate through
different types of graphs

BREADTH FIRST ALGORITHM

Breadth-First Search (BFS) is an algorithm used for traversing
graphs or trees. Traversing means visiting each node of the graph.
Breadth-First Search is a recursive algorithm to search all the vertices
of a graph or a tree. BFS in python can be implemented by using data
structures like a dictionary and lists. Breadth-First Search in tree and
graph is almost the same. The only difference is that the graph may
contain cycles, so we may traverse to the same node again.
Before learning the python code for Breadth-First and its
output, let us go through the algorithm it follows for the same. We can
take the example of Rubik’s Cube for the instance. Rubik’s Cube is seen
as searching for a path to convert it from a full mess of colors to a single
color. So comparing the Rubik’s Cube to the graph, we can say that the
possible state of the cube is corresponding to the nodes of the graph and
the possible actions of the cube is corresponding to the edges of the
graph.
BFS commonly used for applications such as finding the
shortest path in an unweighted graph, network routing, and cycle
detection in an undirected graph. The time complexity of BFS is O(V
+ E), where V is the number of nodes and E is the number of edges,
and the space complexity is O(V).

Principles of BFS :

A J College of Science And Technology

 5

1. Queue-based Approach: BFS employs a queue data structure to

keep track of the vertices that need to be visited. The algorithm
initializes a queue with the source vertex and iteratively dequeues
vertices from the front of the queue, visiting each vertex's
neighbours in a systematic manner.
2. Exploration of Neighbours: For each vertex being visited, BFS
explores all of its adjacent vertices (neighbours) that have not yet
been visited. This ensures that BFS traverses the graph layer by
layer, visiting vertices at the current level before moving on to
vertices at the next level.
3. Level-by-Level Exploration: BFS explores the graph in a level-
by-level manner, ensuring that vertices closer to the source vertex
are visited before vertices farther away. This property makes BFS
particularly suitable for finding shortest paths in unweighted
graphs, as it guarantees that the shortest path to each vertex is
discovered before longer paths.
4. Marking Visited Vertices: To prevent revisiting vertices and
avoid infinite loops, BFS marks each visited vertex as "visited"
once it has been dequeued from the queue. This ensures that each
vertex is visited at most once during the traversal process.
5. Optimality of Shortest Paths: One of the key properties of BFS
is that it guarantees to find the shortest path from the source
vertex to any other vertex in an unweighted graph. This is
achieved due to the level-by-level exploration strategy, which
ensures that shorter paths are discovered before longer paths.
Overall, BFS is a versatile and efficient algorithm for exploring and
analysing graphs, particularly in scenarios where finding the shortest
path or exploring all vertices in a graph is required. Its simplicity and
optimality make it a fundamental tool in graph theory and computer
science.

A J College of Science And Technology

 6

APPLICATION OF BREADTH FIRST SEARCH

ALGORITHM
1. Shortest Path Finding: One of the most common applications of
BFS is finding the shortest path between two nodes in an
unweighted graph. By traversing the graph level by level, BFS
guarantees that the shortest path from the source node to any other
node is found first.
2. Connected Components: BFS can be used to determine the
connected components of an undirected graph efficiently. By
starting BFS from each unvisited node, it's possible to identify all
the connected components present in the graph.
3. Network Broadcasting: BFS is employed in network
broadcasting algorithms to efficiently disseminate information or
messages across a network. By broadcasting messages to
neighbouring nodes in a breadth-first manner, BFS ensures that
the message reaches all reachable nodes with minimal delay.
4. Web Crawling and Indexing: In web crawling, BFS is used to
systematically explore and index web pages on the internet.
Starting from a seed URL, BFS visits all the linked pages at the
same level before moving on to deeper levels, ensuring a
comprehensive coverage of the web.
5. Shortest Path in Grids and mazes: BFS is widely used to find
the shortest path in grid-based environments, such as mazes or
game maps. Each cell in the grid represents a node, and BFS
explores neighbouring cells level by level until it reaches the
target cell, providing the shortest path.
6. Minimum Spanning Tree: BFS can be applied to find the
minimum spanning tree (MST) of an unweighted graph. By
performing BFS starting from any arbitrary node, the resulting
tree contains the spanning tree.

A J College of Science And Technology

 7

IMPLEMENTATION OF BFS IN PYTHON

Breadth-first search is the process of traversing each node of the
graph, a standard BFS algorithm traverses each vertex of the graph into
two parts: 1) Visited 2) Not Visited. So, the purpose of the algorithm
is to visit all the vertex while avoiding cycles. BFS starts from a node,
then it checks all the nodes at distance one from the beginning node,
then it checks all the nodes at distance two, and so on. So as to recollect
the nodes to be visited, BFS uses a queue.
 The implementation of BFS can be broken down into the
following steps:
STEP 1: ENQUEUE THE STARTING NODE
The first step is to enqueue the starting node into a queue data structure.
This node is marked as visited so that it’s not revisited later.
STEP 2: DEQUEUE A NODE AND MARK IT AS VISITED
In this step, we dequeue a node from the queue and mark it as visited.
We then process this node.
STEP 3: ENQUEUE ALL ADJACENT NODES OF THE
DEQUEUED NODE THAT ARE NOT YET VISITED
We then enqueue all the adjacent nodes of the dequeued node that have
not been visited yet. These nodes are added to the end of the queue.
STEP 4: REPEAT STEPS 2-3 UNTIL THE QUEUE IS EMPTY
Many times, a graph may contain two different disconnected parts and
therefore to make sure that we have visited every vertex, we can also
run the BFS algorithm at every node.
BFS example
Let's see how the Breadth First Search algorithm works with an
example. We use an undirected graph with 5 vertices.

A J College of Science And Technology

 8

We start from vertex 0, the BFS algorithm starts by putting it in the

Visited list and putting all its adjacent vertices in the stack. Visit start
vertex and add its adjacent vertices to queue.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the

back of the queue and visit 3, which is at the front of the queue.

Visit 2 which was added to queue earlier to add its neighbours

4 remains in the queue

Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is
already visited. We visit it.

A J College of Science And Technology

 9

Visit last remaining item in the queue to check if it has unvisited

neighbours
Since the queue is empty, we have completed the Breadth First
Traversal of the graph.

BFS pseudocode

Bredth_First_Serach( G, A ) // G ie the graph and A is the source

node
Let q be the queue
q.enqueue( A ) // Inserting source node A to the queue
Mark A node as visited.
While ( q is not empty )
B = q.dequeue( ) // Removing that vertex from the queue,
which will be visited by its neighbour
Processing all the neighbours of B
For all neighbours of C of B
If C is not visited, q. enqueue( C ) //Stores C in q to visit its
neighbour
Mark C a visited

A J College of Science And Technology

 10

PYTHON CODE FOR IMPLEMENTING

BREADTH FIRST SEARCH
from collections import deque

def bfs(graph, start):

visited = set()
queue = deque([start])
visited.add(start) # Add the start vertex to the visited se
bfs_sequence = []

# Perform BFS traversal

while queue:
# Dequeue a vertex from the queue
vertex = queue.popleft()
bfs_sequence.append(vertex)
# Iterate through the neighbors of the dequeued vertex
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)

return bfs_sequence
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
start_vertex = 0
bfs_result = bfs(graph, start_vertex)
print("BFS Traversal Sequence:", bfs_result)

OUTPUT : BFS Traversal Sequence: [0, 1, 2, 3]

A J College of Science And Technology

 11

DEPTH FIRST SEARCH ALGORITHM

Depth-First Search or DFS algorithm is a recursive

algorithm that uses the backtracking principle. It entails conducting
exhaustive searches of all nodes by moving forward if possible and
backtracking, if necessary. To visit the next node, pop the top node
from the stack and push all of its nearby nodes into a stack. Topological
sorting, scheduling problems, graph cycle detection, and solving
puzzles with just one solution, such as a maze or a sudoku puzzle, all
employ depth-first search algorithms. Other applications include
network analysis, such as determining if a graph is bipartite.
The algorithm starts at the root node (in the case of a graph, you
can use any random node as the root node) and examines each branch
as far as possible before backtracking.

When a dead-end occurs in any iteration, the Depth First Search

(DFS) method traverses a network in a deathward motion and uses
a stack data structure to remember to acquire the next vertex to start a
search.

Principle:

The principle behind Depth-First Search can be summarized as

follows:

A J College of Science And Technology

 12

1. Start at a Node: The algorithm starts at an initial node,

typically called the root node, and marks it as visited.
2. Explore Neighbours: It selects an unvisited neighbour of the
current node and moves to it. If there are multiple neighbours, it
chooses one arbitrarily.
3. Recursion or Stack: If implemented recursively, DFS explores
the selected neighbour by recursively calling itself with the
neighbour as the current node. If implemented iteratively, it
pushes the neighbour onto the stack for later exploration.
4. Backtrack if Necessary: If the current node has no unvisited
neighbours, or if the goal node is not found, DFS backtracks to
the previous node and explores other unvisited neighbours.
5. Repeat: Steps 2-4 are repeated until all nodes in the graph are
visited, or until the goal condition is met.

APPLICATION OF DFS ALGORITHM

Depth-First Search (DFS) has numerous applications across various
domains due to its ability to systematically explore the depth of a
graph or tree structure. Here are some notable applications of DFS:

1. Topological Sorting: DFS can be used to perform topological

sorting on directed acyclic graphs (DAGs). This is particularly
useful in scheduling tasks with dependencies, such as compiling
software or processing job dependencies in distributed systems.
2. Cycle Detection: DFS can detect cycles in a graph efficiently.
By tracking back edges during the traversal, DFS can identify if
there are any cycles present in the graph. This is crucial in
various scenarios, such as detecting deadlocks in resource
allocation systems or identifying circular dependencies in
software projects.
3. Graph Connectivity: DFS can determine the connectivity of a
graph, i.e., whether all nodes in the graph are reachable from
each other. This information is vital in network analysis, social
network studies, and identifying communities within a network.
A J College of Science And Technology
 13

4. Path Finding: Although Depth-First Search doesn't guarantee

finding the shortest path, it can be adapted for pathfinding in
certain scenarios. For instance, in maze solving or navigating
grid-based environments, DFS can be used to explore possible
paths until a solution is found.
5. Strongly Connected Components (SCCs): DFS can be
employed to find strongly connected components in directed
graphs. SCCs represent subsets of nodes where each node is
reachable from every other node within the subset. This is
essential in modeling relationships in transportation networks,
telecommunications, and circuit design.
6. Spanning Trees: DFS can be utilized to find spanning trees in
connected graphs. In particular, it can generate depth-first
spanning trees, which are useful in network design, electrical
circuit analysis, and optimization problems.
7. Game Tree Search: In game theory and artificial intelligence,
DFS can be applied to search through the game tree, exploring
possible moves and evaluating potential outcomes. This is
crucial in developing game-playing algorithms, such as those
used in chess, Go, and other board games.
8. Backtracking Algorithms: Many backtracking algorithms,
such as Sudoku solvers, N-Queens problem solvers, and
constraint satisfaction problems, employ DFS as a fundamental
component. DFS is used to explore the solution space
systematically, backtracking when dead-ends are reached.
9. Language Processing: DFS can be used in natural language
processing tasks such as parsing, syntax analysis, and semantic
analysis. It helps in exploring linguistic structures, identifying
relationships between words, and building parse trees.
These applications showcase the versatility and utility of Depth-First
Search in various domains, highlighting its importance as a
fundamental algorithm in graph theory and computer science.

A J College of Science And Technology

 14

IMPLEMENTATION OF DFS IN PYTHON

Depth-first search is an algorithm for traversing or searching tree
or graph data structures. The algorithm starts at the root node (selecting
some arbitrary node as the root node in the case of a graph) and explores
as far as possible along each branch before backtracking.

The outcome of a DFS traversal of a graph is a spanning tree.

A spanning tree is a graph that is devoid of loops. To implement DFS
traversal, you need to utilize a stack data structure with a maximum
size equal to the total number of vertices in the graph.

To implement DFS traversal, you need to take the following stages:

Step 1: Create a stack with the total number of vertices in the graph as
the size.
Step 2: Choose any vertex as the traversal's beginning point. Push a
visit to that vertex and add it to the stack.
Step 3 - Push any non-visited adjacent vertices of a vertex at the top of
the stack to the top of the stack.
Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit
from the vertex at the top of the stack.
Step 5 - If there are no new vertices to visit, go back and pop one from
the stack using backtracking.
Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.
Step 7 - When the stack is entirely unoccupied, create the final
spanning tree by deleting the graph's unused edges.

A J College of Science And Technology

 15

Example for DFS:

Step 1: Mark vertex A as a visited source node by selecting it as a

source node.You should push vertex A to the top of the stack.

Step 2: Any nearby unvisited vertex of vertex A, say B, should be

visited.You should push vertex B to the top of the stack.

Step 3: From vertex C and D, visit any adjacent unvisited vertices of

vertex B. Imagine you have chosen vertex C, and you want to make C
a visited vertex. Vertex C is pushed to the top of the stack.

A J College of Science And Technology

 16

Step 4: You can visit any nearby unvisited vertices of vertex C, you need to
select vertex D and designate it as a visited vertex.Vertex D is pushed to the top
of the stack.

Step 5: Vertex E is the lone unvisited adjacent vertex of vertex D, thus marking
it as visited.Vertex E should be pushed to the top of the stack.

Step 6: Vertex E's nearby vertices, namely vertex C and D have been visited,
pop vertex E from the stack.

Step 7: Now that all of vertex D's nearby vertices, namely vertex B and C, have
been visited, pop vertex D from the stack.

A J College of Science And Technology

 17

Step 8: Similarly, vertex C's adjacent vertices have already been

visited; therefore, pop it from the stack.

Step 9: There is no more unvisited adjacent vertex of b, thus pop it

from the stack.

Step 10: All of the nearby vertices of Vertex A, B, and C, have

already been visited, so pop vertex A from the stack as well.

A J College of Science And Technology

 18

DFS PSEUDOCODE
// pseudocode for iterative method

DFS-iterative (G, s): //Where G is graph and s is

source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited

// pseudocode for recursive method

DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)

A J College of Science And Technology

 19

PYTHON CODE FOR IMPLEMENTING

DEPTH FIRST SEARCH

# BY ITERATIVE METHOD
def dfs_iterative(graph, start):
visited = set() # Initialize an empty set to keep track of
visited nodes
stack = [start] # Initialize a stack to store nodes to be
visited
while stack:
node = stack.pop() # Pop the top node from the stack
if node not in visited:
print(node, end=' ') # Process the node (e.g., print or store
its value)
visited.add(node) # Mark the node as visited

for neighbor in reversed(graph[node]): # Iterate over neighbors

in reverse order
if neighbor not in visited:
stack.append(neighbor) # Push unvisited neighbors
onto the stack
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B',
'F'],'F': ['C', 'E']}
start_node = 'A'
print("Depth-First Traversal (Iterative) starting from node", start_node,
":")
dfs_iterative(graph, start_node)
A J College of Science And Technology
 20

OUTPUT : Depth-First Traversal (Iterative) starting from node A :

ABDEFC
# BY RECURSIVE METHOD
def dfs(graph, node, visited=None):
if visited is None:
visited = set() # Initialize visited set if not provided
visited.add(node) # Mark the current node as visited
print(node, end=' ') # Process the current node (e.g., print its value)
# Recursively visit each neighbor of the current node
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B',
'F'],'F': ['C', 'E']}
start_node = 'A'
print("Depth-First Traversal starting from node", start_node, ":")
dfs(graph, start_node)
OUTPUT : Depth-First Traversal starting from node A :
ABDEFC

A J College of Science And Technology

 21

CONCLUSIONS
In summary the analysis of graph algorithms highlights
their importance, in addressing intricate issues and fostering progress
in various fields. By gaining expertise in these methods and embracing
education professionals can unlock fresh opportunities and make
valuable contributions, to the advancement of knowledge and
technology.The exploration of graph traversal algorithms, including
Breadth-First Search (BFS) and Depth-First Search (DFS), has
provided valuable insights into the fundamental principles and practical
applications of these algorithms in various domains. Through our case
study, we have highlighted the significance of graph traversal
techniques in solving complex problems across computer science,
engineering, and beyond. As technology continues to evolve, the
relevance of graph traversal algorithms is expected to grow. Future
research may focus on:
• Creating algorithms that leverage the advantages of both Breadth
First Search (BFS) and Depth First Search (DFS) to efficiently
tackle problem areas.
• Exploring graph traversal in dynamic and evolving networks,
such as social networks and Internet of Things (IoT) ecosystems.
• Investigating applications of graph traversal in emerging fields
such as quantum computing, bioinformatics, and autonomous
systems.

A J College of Science And Technology

 22

REFERENCES
1.https://www.ques10.com/p/17537/explain-dfs-and-bfs-algorithm-
with-example/
2.Sara Baase (2009), “Computer algorithms : introduction to design
and analysis: chapter 7 :Graph and Graph Traversal”
3.https://intellipaat.com/blog/graph-traversal-in-data-structure/
4.Introduction to The Design and Analysis of Algorithms,3rd edition
by Anany Levitin
5. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to Algorithms. MIT Press.

A J College of Science And Technology