Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at the root (or any arbitrary node) and explores deeper into the graph, visiting all unvisited nodes. DFS can be implemented using either a recursive approach or an explicit stack.
Algorithm:
- Start at the root node, mark it as visited.
- Explore each unvisited adjacent node by recursively calling DFS.
- Backtrack when no unvisited neighbors are left.
DFS is useful in solving problems like finding connected components, topological sorting, and pathfinding in a graph. It can be implemented using both adjacency matrix or adjacency list representations.