2.
Search Algorithms
Q2: Explain Depth-First Search (DFS) algorithm. Give its time and space complexity,
and discuss its advantages and disadvantages.
A2: Depth-First Search (DFS) Algorithm:
Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph
data structures. The algorithm starts at the root node (or an arbitrary node for a
graph) and explores as far as possible along each branch before backtracking. It
uses a stack (implicitly via recursion or explicitly) to keep track of the nodes to
visit.
Algorithm Steps:
Start: Place the starting node on top of a stack and mark it as visited.
Loop: While the stack is not empty:
Pop a node N from the stack.
If N is the goal node, return success.
For each unvisited neighbor M of N:
Mark M as visited.
Push M onto the stack.
No Goal: If the stack becomes empty and the goal node is not found, return failure.
Example (Conceptual):
Imagine a maze. DFS would follow one path as far as it can, hitting dead ends and
backtracking until it finds an unvisited path, and then exploring that path fully.
Time Complexity:
O(V+E) where V is the number of vertices (nodes) and E is the number of edges.
In the worst case, DFS might visit every vertex and every edge to explore the
entire graph.
For a tree, it's O(V).
Space Complexity:
O(V) in the worst case.
This is because, in the worst case (e.g., a long, thin graph or a deeply recursive
path), the stack might store all the vertices.
For a tree, it's O(h) where h is the maximum depth of the tree.
Advantages of DFS:
Memory Efficient: For graphs with many branches but short paths, DFS can be more
memory efficient than Breadth-First Search (BFS) because it doesn't need to store
all nodes at a given level.
Finds Solutions in Deep Trees: If there are many solutions, or if the solution is
very deep in a large search space, DFS can find it quickly without exploring the
entire breadth of the tree.
Simple to Implement: Often implemented recursively, which can lead to concise and
elegant code.
Useful for Cycle Detection and Topological Sorting: DFS is fundamental for these
graph algorithms.
Disadvantages of DFS:
Not Optimal (for shortest path): DFS does not guarantee finding the shortest path
to a goal. If there are multiple paths to the goal, DFS might find a longer path
first.
Can get Stuck in Infinite Loops (with cycles): Without proper visited node
tracking, DFS can get trapped in infinite loops if the graph contains cycles.
Completeness (for infinite or cyclic graphs): In an infinite state space or a graph
with cycles (without visited tracking), DFS might go down an infinite path and
never find the goal, even if a finite path exists. It is only complete for finite
state spaces or if it's guaranteed not to get stuck in infinite paths.
Risk of Deep Exploration: If the goal is near the root but requires exploring a
very deep path on the left side of the tree, DFS will explore that deep path first,
which can be inefficient.
