Before discussing DFS, let’s make a scenary about you together.
STORY
Suppose you are in the living room sitting on your couch. Now suddenly you had a sudden urge to watch the new Rick & Morty TV series. To watch TV, you need to find the TV remote. You are certain that the TV remote must be-
A. on the couch
B. Maybe in the Bedroom
C. Maybe in the Bedroom’s one of the drawer
D. Maybe on the Table in Dining room
E. Maybe your dog ate it
So you first go through the couch (A) but couldn’t find it. Then you go to the Bedroom (B) but get the same result. You check all of the drawers (C) in the bedroom but couldn’t find any trace. Now you went to the Dining Room but there you found nothing on the Table that can turn on your TV. So with last hope, you again go to your living room. There you see that your dog is Chewing your remote ( Thank God, It has not visited your Dog’s belly ). If you look behind your journey, you see that you had gone through all of the points in one direction and had to visit some of the points many time and ultimately got to the point where you get to the goal. This is how DFS or Depth First Search works.
DEFINITION
DFS or Depth First Search is a traversing or searching algorithm for graph or tree based data structure. It starts from a point (node) and explores neighboring points (nodes) as far as possible than backtracks other unvisited points (nodes) until all the points (nodes) are visited.
DFS is an algorithm for traversing or searching through a graph or tree data structure by exploring as far as possible along each branch before backtracking.
HISTORY
DFS is a fundamental graph traversal algorithm in Computer Science and Mathematics. It has been first described by the French mathematician Charles Pierre Trémaux in the 19th century as a technique for solving mazes. When he was working with solving mazes, he systematically set some rules,
1. Start at the entrance of the maze
2. Follow it until you reach a dead end
3. When you find a dead end, find the last junction where you had other ways to visit
4. Continue this process until you find the exit.
This process laid the foundation for the concept of DFS. Although this general idea was primarily used to solve mazes, this idea is now one of the major alogrithm to traverse a graph in the mathematics and was later formalized in computer science by the American mathematician and computer scientist John Hopcroft in the 1970s.
ALGORITHM
You probably have understood the idea from the definition but let’s see it in algorithm-
Recursive DFS:
1. Start at the initial node (often the root in a tree or an arbitrary node in a graph).
2. Mark the current node as visited to avoid revisiting it.
3. Explore each unvisited neighbor of the current node by recursively applying the DFS algorithm.
4. Repeat step 3 until you reach a node with no unvisited neighbors, then backtrack to the previous node and explore other unvisited neighbors.
5. Continue this process until you have visited all nodes you want to explore.
Iterative DFS (using a stack):
1. Initialize an empty stack.
2. Push the initial node onto the stack.
3. While the stack is not empty:
a. Pop a node from the stack.
b. Mark it as visited.
c. Push all unvisited neighbors of the node onto the stack.
4. Repeat steps 3a to 3c until the stack is empty.
CODE
( Will be added later )
COMPLEXITY
LIMITATIONS AND ISSUES
Depth First Search (DFS) is a useful algorithm for various tasks, but it has some limitations and issues to consider:
1. Completeness: DFS may not find a solution if the graph contains infinite loops or cycles. It can get stuck in infinite paths, so it’s not a complete algorithm in such cases.
2. Non-optimality: DFS does not guarantee that it will find the shortest path to a goal. It can find a solution along a longer path before exploring shorter ones.
3. Memory usage: In deep graphs or trees, DFS can use a lot of memory due to the need to maintain a call stack. This can lead to stack overflow errors.
4. Time complexity: In graphs with a large branching factor or deep paths, DFS can have a high time complexity in the worst case.
5. Lack of guidance: DFS doesn’t use heuristics or knowledge about the problem structure, which can make it less efficient for certain search problems.
USAGE
Depth First Search (DFS) is a versatile algorithm used in various applications. Here are 20 common usages of DFS:
1. Graph Traversal: DFS can be used to traverse and explore all nodes in a graph.
2. Path Finding: It can find paths between two nodes in a graph or a maze.
3. Topological Sorting: DFS can be used to perform topological sorting on a directed acyclic graph.
4. Cycle Detection: DFS can identify cycles in a graph.
5. Connected Components: It’s used to find connected components in an undirected graph.
6. Strongly Connected Components: DFS helps find strongly connected components in a directed graph.
7. Maze Solving: DFS can be used to navigate through mazes and find the exit.
8. Sudoku Solving: In combination with backtracking, DFS can solve Sudoku puzzles.
9. Crossword Puzzles: DFS can be used to fill in crossword puzzle grids.
10. Game Tree Search: It’s used in game-playing algorithms like chess, tic-tac-toe, and more.
11. Web Crawling: DFS can be employed for web crawling and indexing web pages.
12. Wireless Network Routing: DFS can find routes in wireless networks.
13. Image Processing: In image analysis, DFS can find connected components.
14. Circuit Analysis: It’s used in electrical circuit analysis to find paths.
15. Memory Allocation: DFS can be used in memory allocation and garbage collection.
16. Social Network Analysis: DFS can identify communities or influencers in social networks.
17. Language Parsing: It’s used in parsing grammatical structures in natural language processing.
18. Task Scheduling: DFS can help schedule tasks in project management.
19. Genetic Algorithms: In optimization problems, DFS can be part of genetic algorithms.
20. AI and Robotics: DFS can be used for path planning in autonomous robots and artificial intelligence applications.
These are just a few examples of the many applications of DFS in computer science and various fields.
SUMMARY
Depth First Search (DFS) is an algorithm used for traversing or searching through tree or graph data structures. It starts at the root node and explores as far as possible along each branch before backtracking. In other words, it goes deep into one branch, explores as much as it can, and backtracks only when necessary.
DFS can be implemented using a recursive approach or a stack-based iterative approach. It is commonly used for tasks like finding paths, solving puzzles, and exploring connected components in graphs.
Byronic 