Understanding Algorithms (Graphs And Traversal), Part 14: Depth-First Search (DFS).

Depth First Search (DFS) is a graph traversal algorithm that explores as deep as possible along a path before backtracking. It uses recursion or a stack to visit nodes and is commonly used for path finding, cycle detection, and connectivity checks.

Depth-First Search is a fundamental graph traversal algorithm used to explore nodes by going as deep as possible before backtracking. Instead of exploring all neighbors at the same level, DFS follows a single path until no further progress can be made. This exploration-first behavior gives DFS its name and defines how it behaves across different data structures.

DFS starts from a chosen source node. From that node, it visits one unvisited neighbor, then continues visiting neighbors of that neighbor, and so on. This process continues until a node is reached that has no unvisited adjacent nodes. At that point, the algorithm backtracks to the previous node and explores the next available path. This pattern repeats until all reachable nodes have been visited.

DFS can be implemented using recursion or an explicit stack. In recursive implementations, the call stack implicitly manages the traversal state. Each recursive call represents moving deeper into the graph. When a node has no unvisited neighbors, the function returns, naturally triggering backtracking. In iterative implementations, a stack is used to simulate this behavior explicitly.

A key requirement for DFS is maintaining a visited set. Graphs may contain cycles, and without tracking visited nodes, DFS could enter an infinite loop. Each node is marked as visited when it is first encountered. This ensures that every node is processed at most once.

The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is examined once during traversal. The space complexity depends on the recursion depth or stack size, which in the worst case can be O(V) for deep or skewed graphs.

DFS behaves differently on trees and graphs. In a tree, DFS visits every node exactly once without needing cycle checks. In graphs, especially dense or cyclic ones, careful handling of visited states is mandatory. This difference explains why DFS is often taught using trees first before general graphs.

One of the most important uses of DFS is backtracking. Backtracking algorithms systematically explore possible solutions by going forward until a constraint is violated or a solution is found, then reversing direction. Problems like maze solving, path finding, and puzzle solving rely heavily on DFS-style backtracking.

DFS is also used to detect cycles in graphs. By tracking recursion states or parent relationships, the algorithm can identify whether a back edge exists. This is essential in applications like dependency resolution and deadlock detection.

Another major application of DFS is in ordering problems. Algorithms such as topological sorting use DFS to determine valid execution order in directed acyclic graphs. DFS finishing times provide the structure needed to compute such orderings correctly.

DFS naturally exposes the structure of a graph. By exploring paths deeply, it reveals connected components, articulation points, and strongly connected regions when combined with additional logic. Many advanced graph algorithms are extensions of basic DFS with extra bookkeeping.

Depth-First Search emphasizes controlled exploration. It shows how systematic traversal, combined with state tracking and backtracking, can explore complex structures without redundancy. This makes DFS a foundational tool for understanding graph behavior and algorithmic exploration strategies.

class DepthFirstSearch:
    def __init__(self):
        """
        This constructor initializes the Depth First Search setup.

        What this represents:
        - A graph traversal technique.
        - Exploration before backtracking.

        Why this matters:
        - Reaches deep paths quickly.
        - Forms the base of many graph algorithms.
        """
        pass

    # --------------------------------------------------
    # BUILD GRAPH (ADJACENCY LIST)
    # --------------------------------------------------
    def build_graph(self, edges):
        """
        Builds a graph using an adjacency list.

        Core idea:
        - Each node stores its neighbors.
        - Supports flexible connections.
        """

        graph = {}

        for u, v in edges:
            if u not in graph:
                graph[u] = []
            if v not in graph:
                graph[v] = []

            graph[u].append(v)
            graph[v].append(u)

        return graph

    # --------------------------------------------------
    # DEPTH FIRST SEARCH (RECURSIVE)
    # --------------------------------------------------
    def dfs(self, graph, node, visited=None):
        """
        Performs Depth First Search on a graph.

        Core idea:
        - Go as deep as possible.
        - Backtrack when no path remains.

        Key rule:
        - Track visited nodes to avoid cycles.
        """

        if visited is None:
            visited = set()

        # Mark current node as visited
        visited.add(node)
        print(node)

        # Explore neighbors
        for neighbor in graph[node]:
            if neighbor not in visited:
                self.dfs(graph, neighbor, visited)

# --------------------------------------------------
# EXAMPLE USAGE
# --------------------------------------------------

edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 5)
]

dfs_algo = DepthFirstSearch()
graph = dfs_algo.build_graph(edges)

print("DFS Traversal:")
dfs_algo.dfs(graph, 1)