Graph traversal in Go
You are building a dependency resolver for a build system. Package A depends on B and C. B depends on D. You need to know the exact order to compile, or you need to find if a specific package is reachable from the root. This is graph traversal. Go gives you slices and maps to build these algorithms from scratch. You don't need a heavy library. You need to understand the data structures.
Graph traversal comes in two main flavors. Breadth-First Search (BFS) explores neighbors before neighbors' neighbors. Depth-First Search (DFS) explores one branch fully before backtracking. BFS uses a queue. DFS uses a stack or recursion.
Think of BFS like a stone dropped in a pond. The ripples expand outward evenly. You check the closest nodes first, then the next ring, then the next. Think of DFS like a mouse in a maze. It runs down a corridor until it hits a wall, then backs up to the last junction and tries a new path. It goes deep before it goes wide.
The minimal BFS implementation
BFS requires a queue to track which nodes to visit next. A slice works perfectly as a queue. You append to the end and remove from the front. You also need a visited set to avoid infinite loops if the graph contains cycles.
Here's the simplest BFS: spawn a queue with the start node, loop while the queue has items, process the head, and enqueue unvisited neighbors.
// Node represents a vertex in a graph
type Node struct {
ID string
Neighbors []*Node
}
// BFS visits nodes level by level using a slice as a queue
func BFS(start *Node) []string {
if start == nil {
return nil
}
visited := make(map[*Node]bool)
queue := []*Node{start}
var result []string
for len(queue) > 0 {
// Dequeue the first element
current := queue[0]
queue = queue[1:]
if visited[current] {
continue
}
visited[current] = true
result = append(result, current.ID)
// Enqueue neighbors
for _, neighbor := range current.Neighbors {
if !visited[neighbor] {
queue = append(queue, neighbor)
}
}
}
return result
}
The minimal DFS implementation
DFS can be implemented with a stack or recursion. Recursion is the most readable approach for small graphs. The call stack acts as your stack. You visit a node, mark it, then immediately recurse into its neighbors.
Here's the recursive DFS: check for nil or visited, mark the node, then loop through neighbors and recurse.
// DFSRecursive visits nodes by going deep into one branch before backtracking
func DFSRecursive(node *Node, visited map[*Node]bool, result *[]string) {
if node == nil || visited[node] {
return
}
visited[node] = true
*result = append(*result, node.ID)
for _, neighbor := range node.Neighbors {
// Recurse immediately to go deeper
DFSRecursive(neighbor, visited, result)
}
}
How the algorithms run
The BFS loop is driven by len(queue) > 0. Each iteration pulls the head of the queue with queue[0] and drops it with queue = queue[1:]. This slicing operation creates a new slice header that points to the same underlying array, starting at index 1. The elements before index 1 are no longer accessible through the slice, but the underlying array remains allocated until the slice goes out of scope.
The visited map prevents cycles. Without it, a graph where A points to B and B points to A would loop forever. The map uses *Node as the key. Pointers are unique identities. Two nodes might have the same ID string, but they are different objects in memory. Using the pointer ensures you track the actual node instance.
The DFS recursion relies on the call stack. Each recursive call adds a frame. When a node has no unvisited neighbors, the function returns, popping the frame. The result slice is passed as a pointer. This avoids copying the slice on every recursive return. Slices are small headers, but copying them repeatedly in deep recursion adds overhead. Passing a pointer keeps the accumulation efficient.
Realistic BFS with index tracking
The queue = queue[1:] idiom is clean but has a hidden cost. Slicing does not free memory. The underlying array keeps growing as you append neighbors. If you process a large graph, the slice header moves forward, but the old elements stay in memory, referenced by the underlying array. This can cause memory pressure.
The fix is to use an index pointer. You keep the slice intact and increment a head index. This avoids slicing overhead and lets the garbage collector reclaim memory when the function returns.
Here's the index-based BFS: track the head with an integer, increment it each loop, and append to the slice without slicing.
// BFSIndex performs BFS using an index pointer to avoid slice copying overhead
func BFSIndex(start *Node) []string {
if start == nil {
return nil
}
visited := make(map[*Node]bool)
queue := []*Node{start}
var result []string
head := 0
for head < len(queue) {
current := queue[head]
head++ // Move the logical head forward
if visited[current] {
continue
}
visited[current] = true
result = append(result, current.ID)
for _, neighbor := range current.Neighbors {
if !visited[neighbor] {
queue = append(queue, neighbor)
}
}
}
return result
}
This pattern is standard in Go for high-performance queues. The slice grows as needed. The head index tracks progress. No slicing means no hidden memory retention. The slice is freed when the function returns.
Pitfalls and runtime errors
Infinite loops are the most common bug. Forgetting the visited check turns a cycle into an infinite loop. The program hangs until you kill it. Always mark a node as visited before processing its neighbors.
Stack overflow is the danger with recursive DFS. Go's stack grows dynamically, but there is a limit. The runtime panics with runtime: goroutine stack exceeds 1000000000-byte limit if the recursion gets too deep. Deep graphs require iterative DFS with an explicit stack.
Slice aliasing can cause subtle bugs. If you return the result slice and the caller modifies it, you might affect internal state if the slice shares an underlying array with other data. This is rare in traversal but worth noting. Return the slice and assume the caller owns it.
Context cancellation is missing from these examples. Real-world traversal often needs cancellation. If the graph is huge, you might want to stop early. Pass a context.Context as the first parameter. Check ctx.Err() in the loop. Context is plumbing. Run it through every long-lived call site.
When to use BFS versus DFS
Use BFS when you need the shortest path in an unweighted graph. BFS explores level by level, guaranteeing the first time you reach a node is via the shortest route.
Use DFS when you need to explore all paths or detect cycles. DFS goes deep, making it ideal for topological sorting or finding connected components.
Use recursive DFS when the graph depth is shallow and code clarity matters. Recursion is elegant and easy to read.
Use iterative DFS when the graph is deep and you need to avoid stack overflow. An explicit stack gives you control over memory usage.
Use an index-based queue when the graph is large and memory efficiency matters. Slicing a queue retains memory. An index pointer avoids this overhead.
Use a visited map with pointer keys when nodes have unique identities. String IDs can collide. Pointers are unique.
BFS finds the shortest path. DFS finds a path. Pick the tool that matches the shape of your problem.