Depth-First Search (DFS)
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far along a branch as possible before backtracking. It dives deep into the graph, visiting vertices along a path until it reaches a vertex with no unvisited neighbors, and then it backtracks to explore other paths. DFS can be implemented using either recursion or a stack.
Key Concepts:
Graph: DFS works on both directed and undirected graphs, as well as connected or disconnected graphs.
Stack or Recursion: DFS uses a stack-like structure, either explicitly (via a stack data structure) or implicitly (via recursion).
Visited List: A list or set is used to keep track of the visited nodes to avoid re-exploration and infinite loops.
Steps:
Start from a source node, mark it as visited.
Recursively explore each unvisited neighbor by visiting the next deepest node until no more unvisited neighbors remain.
Backtrack to the previous node and explore any remaining unvisited neighbors.
Repeat this process until all reachable nodes are visited.
Key Points:
Backtracking: DFS dives deep into the graph, and when it reaches a node with no unvisited neighbors, it backtracks to explore other branches.
Component Exploration: DFS is great for exploring entire components of a graph, making it useful for identifying connected components in an undirected graph.
Topological Sorting: DFS is the basis for topological sorting in directed acyclic graphs (DAGs).
Cycle Detection: DFS can detect cycles in a graph by encountering a node that has already been visited but is not the parent of the current node (for undirected graphs).
Example Usage:
Pathfinding in mazes (though it doesn’t guarantee the shortest path like BFS).
Finding connected components in a graph.
Cycle detection in a graph.
Topological sorting of a directed acyclic graph.