Breadth-First Search

Ever felt lost in a tangled web of connections? Think of a social network, a maze, or even just city streets. How do you efficiently explore everything, or find the quickest way from point A to point B? Enter Breadth-First Search (BFS), the systematic explorer of the graph world!

BFS is a graph traversal algorithm that's all about exploring broadly before deeply. Imagine dropping a pebble in a pond: the ripples expand outwards, reaching every point at one "distance" before moving to the next. That's BFS in a nutshell! It meticulously checks all immediate neighbors of a starting point before venturing out to their neighbors, and so on. It's like finding a party guest's friend by first checking everyone they know personally, then checking those friends' friends.

To keep track of its grand exploration plan, BFS relies on two trusty companions: a queue (its "to-do list" of nodes to visit next) and a map (its "visited" list, ensuring it doesn't get stuck in an endless loop or re-explore familiar territory).

Here's a simple Go implementation to kick things off, which just prints out each node as it's visited:

func BFS(graph map[int][]int, start int) {
    visited := map[int]bool{}   // Our "been here, done that" map
    visited[start] = true       // Mark our starting point as visited
    q := Queue{}                // Time to grab our trusty queue!
    q.Put(start)                // Put the starting node on the to-do list

    for !q.IsEmpty() {          // Keep going as long as there are nodes on our to-do list
        cur, _ := q.Get()       // Grab the next node from the front of the queue

        fmt.Println(cur)        // "Hello, world!" (or rather, "Hello, node!")

        for _, neighbour := range graph[cur] { // Check all of our current node's friends (neighbors)
            if visited[neighbour] { // Have we already said hello to this friend?
                continue            // If yes, let's not be redundant. Skip.
            }

            visited[neighbour] = true // Mark this new friend as visited
            q.Put(neighbour)          // Add this new friend to the to-do list
        }
    }
}

This simple version is great for seeing how BFS works, but in the real world, we want to do more than just print nodes. How about finding all possible paths from our starting node? For that, we'll need to upgrade our queue to store entire paths instead of just single nodes.

Here's a custom queue specifically designed to hold slices of integers (representing paths):

type PathQueue struct {
    Paths [][]int
}

func (q *PathQueue) Get() ([]int, error) {
    if q.IsEmpty() {
        return []int{}, errors.New("Queue is empty")
    }
    first := q.Paths[0]
    q.Paths = q.Paths[1:]
    return first, nil
}

func (q *PathQueue) IsEmpty() bool {
    return len(q.Paths) == 0
}

func (q *PathQueue) Put(path []int) {
    q.Paths = append(q.Paths, path)
}

With our snazzy PathQueue, our BFS implementation transforms into a path-finding machine:

func BFS(graph map[int][]int, start int) {
    visited := map[int]bool{}
    visited[start] = true
    q := PathQueue{}            // Our new queue, ready for paths!
    q.Put([]int{start})         // The starting node is now our first "path"

    for !q.IsEmpty() {
        path, _ := q.Get()              // Get the current path (e.g., [1, 5, 8])
        last := path[len(path)-1]       // Find the last node in this path (e.g., 8)

        fmt.Println(path)               // "Look ma, a path!"

        for _, n := range graph[last] { // Explore neighbors of the last node in the current path
            if visited[n] {
                continue // Already been here, move along
            }
            visited[n] = true // Mark this new neighbor as visited

            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
            q.Put(newSlice)                     // Add this shiny new, longer path to the queue
        }
    }
}

Finding the Shortest Path: The GPS of Graphs

One of BFS's coolest tricks is its ability to find the shortest path between two nodes in an unweighted graph (where all connections have the same "cost"). Because it explores layer by layer, the first time it hits your target node, it guarantees that path is the shortest!

We can adapt our path-finding BFS with a tiny modification to stop once we hit our target:

func BFS(graph map[int][]int, start, target int) {
    visited := map[int]bool{}
    visited[start] = true
    q := PathQueue{}
    q.Put([]int{start})

    for !q.IsEmpty() {
        curPath, _ := q.Get()
        lastNode := curPath[len(curPath)-1] // Get the last node in the current path

        if lastNode == target { // Is this the node we've been looking for?!
            fmt.Println("Shortest path found:", curPath) // Yes! Print the path!
            break // And we're done here, no need to explore further!
        }

        for _, neighbour := range graph[lastNode] {
            if visited[neighbour] {
                continue
            }
            visited[neighbour] = true

            newPath := []int{}
            newPath = append(newPath, curPath...)
            newPath = append(newPath, neighbour)
            q.Put(newPath)
        }
    }
}

This version will print the first path found to the target, which, by BFS's nature, is guaranteed to be one of the shortest paths (or the shortest if edge weights are uniform).

---

Time Complexity: Every Node, Every Edge (Mostly)

The time complexity of Breadth-First Search is typically expressed as O(N + E), where N is the number of nodes (vertices) and E is the number of edges (connections) in your graph.

Why N + E? Because in the worst case, BFS has to:

1. Visit every single node (that's the N part).
2. Look at every single edge to find new neighbors (that's the E part).

So, whether your graph is a sprawling metropolis or a sparsely connected village, BFS will make sure it checks all the necessary paths.

Space Complexity: The Queue Can Get Cozy

The space complexity of BFS is O(N), where N is the number of nodes. This is primarily because, in the worst-case scenario, the queue might need to hold almost all the nodes in the graph (e.g., if you have a "star" graph where one central node is connected to many others, and those are all on the same "level"). Plus, our visited map also needs to store up to N entries. So, it's efficient, but it does need enough memory to keep track of its ongoing exploration.

---

Conclusion: Mastering the Ripple Effect

Breadth-First Search is a cornerstone algorithm for graph traversal. Its systematic, layer-by-layer approach makes it perfect for finding the shortest path in unweighted graphs, exploring all reachable nodes, or simply understanding the structure of a network.

Once you grasp the core idea – the expanding "radius" and the vital role of the queue and visited map – BFS will become one of those algorithms you simply know how to implement and apply. It's an indispensable tool in any programmer's toolkit.

What kind of graphs are you excited to explore with BFS?