DEPTH FIRST SEARCH
NAME- GAURAV THAKUR
ROLL NO. – 114/20
CLASS=CSE (6TH)
SUBMITTED TO:- DR PARVEEN KAKKAR
CONTENT
WHAT IS DFS
IMPLEMENTATION
ADVANTAGES OF DFS
DISADVANTAGES OF DFS
APPLICATION OF DFS
CONCLUSION
REFERENCES
P R E S E N TAT I O N T I T L E 2
DFS (DEPTH FIRST SEARCH)
Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.
It starts at the root node and explores as far as possible along each branch before backtracking.
DFS is a recursive algorithm, meaning it calls itself during its execution. It uses a stack to keep track of the nodes that
it has visited, and it visits each node only once.
3
IMPLEMENTATION OF DFS
DFS is a recursive algorithm and uses a stack data structure to keep
track of the nodes that need to be explored.
It is implemented using a stack, which is a Last In First Out (LIFO)
data structure. Each node is visited once, and the algorithm follows
all the edges from that node until it reaches a leaf node or a node that
has already been visited.
The algorithm then backtracks to the previous node and continues
exploring the graph.
A D VA N TA G E S O F D F S
DFS is a simple and effective strategy for traversing a tree or graph. It is often used to find a path between two
nodes, or to find all nodes connected to a certain node.
DFS is also useful for topological sorting, finding strongly connected components in a graph, and solving puzzles
such as mazes.
Consumes less memory
Takes less time in small graph than BFS algorithm.
5
DISADVANTAGES OF DFS
DFS is not suitable for large graphs, as it may take a long time to traverse the entire graph.
It is also not suitable for graphs with cycles, as the algorithm may get stuck in an infinite loop.
Finally, DFS is not optimal for finding the shortest path between two nodes, as it may not explore all the possible
paths.
DFS is also not suitable for solving problems that require optimal solutions, as it may not find the best solution.
For example, it may not find the shortest path between two nodes in a graph, or the most efficient way to solve a
problem.
6
APPLICATIONS OF DFS
DFS is used in many applications such as finding connected components
in a graph, solving puzzles like mazes, finding the shortest path between
two nodes, topological sorting, and solving problems like the traveling
salesman problem.
DFS is also used in artificial intelligence applications such as game
playing, natural language processing, and robotics.
It is also used in data mining and machine learning applications such as
clustering, classification, and anomaly detection.
7
CONCLUSION
Depth First Search is a simple and intuitive algorithm for traversing or searching tree or graph data structures. It is
easy to implement and requires less memory compared to other searching algorithms.
It is used in many applications such as finding connected components, solving puzzles, and finding the shortest
path between two nodes.
DFS has some drawbacks such as not being suitable for large graphs or graphs with cycles, and not being optimal
for finding the shortest path between two nodes.
Despite these drawbacks, DFS is still a useful algorithm for many applications.
8
9
