Depth First Search(DFS) Algorithm
Take a look at the below Pseudocode which explains the working of DFS
function findPath(robot, start, goal):
stack ← empty stack
visited ← empty set
stack.push(start)
while not stack.isEmpty( ):
current ← stack.pop( )
if current == goal:
return "Path found"
visited.add(current)
neighbors ← robot.getNeighbors(current)
for neighbor in neighbors:
if neighbor not in visted:
stack.push(neighbor)
return "Path not found"
Step wise DFS Pseudocode Explanatioin
- Initialize an empty stack and an empty set for visited vertices.
- Push the start vertex onto the stack.
- While the stack is not empty:
- Pop the current vertex.
- If it’s the goal vertex, return “Path found”.
- Add the current vertex to the visited set.
- Get the neighbors of the current vertex.
- For each neighbor not visited, push it onto the stack.
- If the loop completes without finding the goal, return “Path not found”.
Time complexity of DFS:
- Explicit Time Complexity: This time complexity arises because DFS traverses each vertex and edge exactly once in the worst-case scenario. This complexity is for explicit traversing of DFS without any repetition. The time complexity of DFS is commonly represented as
O(|V| + |E|)
Where,
- V- represents the number of vertices,
- E – represents the number of edges.
- Implicit Time Complexity: This implicit time complexity is appropriate while considering the time complexity in terms of the number of nodes visited in the tree instead of the number of edges and vertices in a graph. For implicit traversing of DFS can be simply depicted as,
O(bd)
where,
- b – represents the branching factor,
- d – represents the depth of the search.
Space complexity of DFS:
- Explicit Space Complexity: The space complexity of DFS is commonly represented as
O(|V|)
Where,
- V – represents the number of vertices.
This is because DFS typically uses additional data structures like stack or recursion stack to keep track of visited vertices.
- Implicit Space Complexity: For an implicit search in a graph, DFS’s space complexity can be represented as follows:
O(bd)
where,
- b – represents the branching factor,
- d – represents the depth of the search.
This space complexity is said to be considered when the space is required to store the nodes on the current path during the search.
Depth First Search (DFS) for Artificial Intelligence
Depth-first search contributes to its effectiveness and optimization in artificial intelligence. From algorithmic insights to real-world implementations, DFS plays a huge role in optimizing AI systems. Let’s dive into the fundamentals of DFS, its significance in artificial intelligence, and its practical applications.
Table of Content
- What is a Depth-First Search in AI?
- Edge classes in a Depth-first search tree based on a spanning tree:
- Depth First Search(DFS) Algorithm
- DFS Behavior Across Different State Space Structures
- DFS Implementation in Robotics Pathfinding
- Applications of DFS in AI
- Conclusion
- FAQs on Depth First Search(DFS) for Artificial Intelligence