Introduction
Depth-First Search (DFS): DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (either explicitly or via recursion) to keep track of the nodes to be visited.
DFS is commonly used in applications such as solving puzzles, pathfinding, and detecting cycles in graphs.
How does it work?
- Start from the source node and mark it as visited.
- Recursively visit all unvisited neighbors of the current node.
- Backtrack when no unvisited neighbors are left.
- Repeat the process for disconnected components if necessary.
Important Observations
- DFS explores nodes as deep as possible before backtracking.
- It does not guarantee the shortest path in an unweighted graph.
- It uses a stack (or recursion) to manage the traversal order.
Key Characteristics:
- Depth-first traversal of graph nodes.
- Suitable for both connected and disconnected graphs.
- Works for both directed and undirected graphs.
Advantages:
- Requires less memory compared to BFS.
- Can be easily implemented using recursion.
- Useful for topological sorting and detecting cycles.
Disadvantages:
- May get stuck in an infinite loop if the graph contains cycles and visited nodes are not tracked.
- Does not guarantee the shortest path in an unweighted graph.
Time Complexity: