Depth-First Search

Ever felt like truly diving deep into a rabbit hole, exploring every twist and turn before ever looking back? That's the spirit of Depth-First Search (DFS)! This graph traversal algorithm is your go-to when you want to explore a graph by plunging as far as possible down a single path before backtracking and trying another.

Think of DFS as a determined spelunker in a cave system. They pick a tunnel, go as far as they can, mark their path, and only if they hit a dead end or already-explored territory, do they backtrack to the last junction and try a different unexplored tunnel. This makes it excellent for tasks like finding any path between two nodes, detecting cycles, or solving mazes.

To keep its adventurous journey organized, DFS relies on two trusty tools: a stack (its "next tunnel to explore" list) and a map (its "already been here, don't get lost!" tracker).

Here's a straightforward Go implementation of DFS that simply prints each node as it's discovered:

func DFS(graph map[int][]int, start int) {
    visited := map[int]bool{}   // Our "been there, done that" map
    s := Stack{}                // Our trusty stack to manage the deep dives
    s.Push(start)               // Start the adventure by pushing the starting node onto the stack

    for !s.IsEmpty() { // Keep exploring as long as there are nodes on our stack
        cur := s.Pop() // Grab the node from the *top* of the stack (LIFO!)

        if visited[cur] { // Have we already explored this deep, dark corner?
            continue      // If yes, no need to revisit. Move along!
        }
        visited[cur] = true // Mark this node as officially explored

        fmt.Println(cur) // "Aha! Found you, node!"

        // Now, add all this node's unseen neighbors to the stack.
        // The one pushed *last* will be explored *first* in the next iteration.
        for _, n := range graph[cur] {
            s.Push(n)
        }
    }
}

This simple DFS version is great for understanding the core mechanism. But what if we want to trace the entire path taken to reach a node, or even find all unique paths from our starting point? For that, we'll need to upgrade our stack to hold slices of integers (representing full paths) instead of just single nodes.

Here's a custom stack built to store these paths:

type Stack struct {
    Paths [][]int // A slice of slices, where each inner slice is a path
}

func (s *Stack) Push(path []int) {
    s.Paths = append(s.Paths, path) // Add a new path to the top
}

func (s *Stack) Pop() ([]int, error) {
    if len(s.Paths) == 0 {
        return []int{}, errors.New("Stack is empty") // Can't pop from an empty stack!
    }
    last := s.Paths[len(s.Paths)-1] // Get the top path
    s.Paths = s.Paths[:len(s.Paths)-1] // Remove it
    return last, nil
}

func (s *Stack) IsEmpty() bool {
    return len(s.Paths) == 0
}

With our PathStack ready for action, our DFS function can now print every unique path it discovers:

func DFS(graph map[int][]int, start int) {
    visited := map[int]bool{} // Still tracking visited *nodes*
    s := Stack{}              // Initialize our new path-aware stack
    s.Push([]int{start})      // Push the starting node as our very first path

    for !s.IsEmpty() {
        path, _ := s.Pop()              // Get the current path (e.g., [1, 3, 7])
        last := path[len(path)-1]       // The very last node in this path (e.g., 7)

        // Important: For paths, we check if the *next neighbor* is already in *this specific path*
        // to avoid cycles within a single path, rather than using a global 'visited' for nodes.
        // A global 'visited' is fine if we only care about visiting each *node* once, not finding all paths.
        // For distinct paths, we often need to check path history.
        // For simplicity here, we'll keep the global visited for nodes, but note the common pitfall.
        // The `slices.Contains` check is more robust for unique paths.

        fmt.Println(path) // "Behold, a complete journey!"

        // Explore neighbors of the last node in the current path
        for _, n := range graph[last] {
            // Check if the neighbor is already part of the *current* path to prevent infinite loops in cycles
            if slices.Contains(path, n) { // Requires Go 1.21+ for `slices` package
                continue
            }

            // For path printing, we often don't use a global 'visited' map for nodes if we want *all* unique paths.
            // However, if the goal is only to print paths without repeating *nodes* in the path, `slices.Contains` is key.
            // If the goal is to prevent revisiting *nodes across different paths* (e.g., in a maze solver),
            // a global visited map might still be used, but careful consideration is needed.
            // For now, let's keep it simple and focus on avoiding cycles *within* a path.
            // visited[n] = true // Uncomment if you want to prevent paths that revisit *any* node globally.

            newSlice := []int{}             // Create a brand new path slice
            newSlice = append(newSlice, path...) // Copy all nodes from the current path
            newSlice = append(newSlice, n)      // Add the new neighbor to extend the path
            s.Push(newSlice)                     // Add this extended path to the stack
        }
    }
}

A quick note on pathfinding: While DFS can find a path to a target node, it's crucial to remember that the first path DFS finds is not guaranteed to be the shortest. That's a job for its cousin, Breadth-First Search, which systematically finds paths in increasing order of length. If you need the shortest path, BFS is usually your champion. DFS is better for finding any path, detecting cycles, or exploring all connected components.

Time Complexity: Every Node, Every Edge (Like BFS!)

Just like its breadth-first counterpart, the time complexity of Depth-First Search is O(N + E), where N represents the number of nodes (vertices) and E represents the number of edges in your graph. In the worst case, DFS needs to visit every node and examine every edge to complete its thorough exploration.

Space Complexity: The Deep Dive's Footprint

The space complexity of DFS is O(N), where N is the number of nodes. Why? Because in the worst-case scenario (imagine a very long, single-line graph, or a tree that's essentially a long chain), the stack might end up holding almost all the nodes, tracing the entire depth of the path before backtracking.

Conclusion: The Deep Thinker of Graphs

Depth-First Search is a powerful and elegant algorithm for traversing graphs. Its "go deep, then backtrack" strategy makes it distinct from BFS, using a stack where BFS uses a queue. This difference in data structure fundamentally changes how they explore, making DFS particularly well-suited for problems like cycle detection, topological sorting, and finding any path in a labyrinthine graph.

Once you truly grasp its mechanics, DFS becomes a remarkably intuitive and indispensable tool in your algorithmic arsenal.

Ready to explore the deepest corners of your own graphs?