Dependency graphs and the maze of connections
You are building a tool to resolve dependencies for a package manager. Module app imports lib-a and lib-b. Module lib-a imports lib-c. Module lib-b also imports lib-c. You need to determine the download order so that lib-c is available before lib-a or lib-b try to use it. You also need to detect if lib-a imports lib-b and lib-b imports lib-a, which would create a cycle and break the build.
You represent each module as a node and each import as a directed edge. The structure that holds this web of connections is a graph. In Go, the standard way to implement a graph is an adjacency list built from a map of slices. This approach gives you fast lookups, flexible node types, and memory efficiency for sparse connections.
Adjacency lists in plain words
An adjacency list stores a graph as a collection of lists. Each node has its own list of neighbors. If you ask the graph for the neighbors of node A, it returns the list attached to A. If A has no neighbors, the list is empty.
Think of a subway map. Each station is a node. Next to each station name, there is a list of other stations you can reach directly. If you are at Central, the list says "Union, Market, Park". If you are at Union, the list says "Central, River, Bridge". You do not store a giant grid of every possible pair of stations. You only store the connections that actually exist. This saves space when the graph is sparse, which describes most real-world graphs. A social network has millions of users but each user connects to a small fraction of the total. A dependency graph has many packages but each package imports only a few others.
In Go, the natural implementation is a map where the key is the node identifier and the value is a slice of neighbor identifiers. Maps provide O(1) average-time lookups. Slices grow dynamically as you add edges. The combination matches the mental model of an adjacency list perfectly.
Minimal implementation
Here is the skeleton. A struct holds a map where keys are nodes and values are slices of neighbors. The receiver is a pointer so methods can modify the graph without copying the map.
package main
// Graph stores nodes and their connections using an adjacency list.
type Graph struct {
// adj maps each node ID to a slice of neighbor IDs.
adj map[int][]int
}
// NewGraph creates a new empty graph.
func NewGraph() *Graph {
return &Graph{
// make initializes the map so AddEdge doesn't panic on nil map.
adj: make(map[int][]int),
}
}
// AddEdge records a directed connection from u to v.
func (g *Graph) AddEdge(u, v int) {
// append works safely even if adj[u] is missing;
// the map entry is created automatically with a new slice.
g.adj[u] = append(g.adj[u], v)
}
// Neighbors returns the list of nodes reachable directly from u.
func (g *Graph) Neighbors(u int) []int {
// returning the slice directly is efficient but exposes internal state;
// callers must not modify the returned slice.
return g.adj[u]
}
The receiver name g follows Go convention. Receiver names are usually one or two letters matching the type, like b for Buffer or g for Graph. This keeps method signatures clean and focuses attention on the arguments.
Runtime behavior and memory
When you call NewGraph, Go allocates a Graph struct and initializes the adj map. The map starts empty. The make call allocates the map header and an initial bucket array. If you skip make, the map remains nil.
When you call AddEdge(1, 2), Go looks up key 1 in the map. The key does not exist, so the map returns the zero value of the slice type, which is nil. The append built-in sees a nil slice, allocates a new underlying array, places 2 in it, and returns a slice pointing to that array. The assignment g.adj[u] = ... stores the new slice in the map. The map now holds 1: [2].
If you call AddEdge(1, 3), the map finds key 1 and returns the slice [2]. append checks the capacity of the slice. If there is room, it adds 3 in place. If the slice is full, append allocates a larger array, copies the existing elements, adds 3, and returns the new slice. The map updates the entry to point to the new slice. This growth strategy amortizes the cost of allocation, so adding edges remains fast on average.
The pointer receiver *Graph ensures all methods operate on the same graph instance. Maps are reference types in Go, so copying the struct would not copy the map data, but the pointer receiver makes the intent explicit: this method modifies the receiver. This is a common pattern for data structures. Methods that mutate state take a pointer. Methods that only read can take a value, but consistency often leads to using pointers for all methods on a struct.
Adjacency lists trade lookup speed for memory efficiency. Pick the structure that matches your access pattern.
Traversal with breadth-first search
Real code usually traverses the graph to find paths, detect cycles, or compute components. Here is a breadth-first search that checks if a path exists from a start node to a target node. BFS explores layer by layer, which guarantees finding the shortest path in an unweighted graph.
// HasPath checks if a path exists from start to target using BFS.
func (g *Graph) HasPath(start, target int) bool {
if start == target {
return true
}
// visited tracks nodes we've already queued to avoid cycles.
visited := make(map[int]bool)
visited[start] = true
// queue holds nodes waiting to be explored.
queue := []int{start}
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
// _ discards the index since we only need the neighbor value.
for _, neighbor := range g.adj[current] {
if neighbor == target {
return true
}
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
return false
}
The visited map prevents the algorithm from looping forever if the graph contains cycles. Without it, BFS would revisit nodes indefinitely. The queue implements a first-in-first-out structure using a slice. Dequeueing removes the first element, which is O(n) for a slice, but for small queues this is acceptable. For high-performance BFS, a ring buffer or a linked list is better, but the slice approach is simple and idiomatic for moderate sizes.
The loop for _, neighbor := range g.adj[current] uses the underscore _ to discard the index. This tells the compiler you intentionally ignored the index and prevents the "unused variable" error. It is a clear signal to readers that the index is irrelevant.
BFS finds the shortest path in unweighted graphs. DFS finds any path and uses less memory for deep trees. Choose the traversal that matches your goal.
Pitfalls and compiler errors
Nil maps are the most common crash. If you forget make(map[int][]int) in the constructor, the map stays nil. Calling AddEdge triggers panic: assignment to entry in nil map. The compiler does not catch this because nil maps are valid values. The crash happens at runtime when the map tries to write to a non-existent bucket. Always initialize maps with make or a composite literal.
Slice aliasing is a silent corruption risk. The Neighbors method returns the slice stored inside the map. If the caller does neighbors := g.Neighbors(1); neighbors = append(neighbors, 99), they might modify the graph's internal array if the slice has spare capacity. This corrupts the graph without any error. The fix is to return a copy or document that the slice is read-only. For performance, returning the slice is common, but you must trust the caller or return append([]int(nil), g.adj[u]...) to create a copy.
Duplicate edges break algorithms. AddEdge appends blindly. Calling it twice with the same pair adds the neighbor twice. This causes BFS to process the same edge multiple times, slowing down traversal and potentially causing infinite loops if the visited check is missing. You can add a check in AddEdge to skip duplicates, but it costs time. Decide if duplicates matter for your use case. If they do, iterate the slice before appending or use a set to track edges.
Undirected graphs require two updates. AddEdge(u, v) adds u -> v. For an undirected graph, you also need v -> u. You can wrap AddEdge in an AddUndirectedEdge method that calls AddEdge twice. Forgetting the second call creates a graph that behaves as directed even when you intended it to be undirected.
Nil maps panic. Shared slices corrupt. Check your invariants before you deploy.
Decision matrix
Use an adjacency list with map[T][]T when your graph is sparse and you need fast lookups for neighbors by node ID.
Use an adjacency matrix with [][]bool or [][]int when the graph is dense and you need O(1) checks for edge existence between any two nodes.
Use a slice of structs when node IDs are dense integers starting from zero and you want cache-friendly memory layout for traversal.
Use a third-party library like gonum/graph when you need weighted edges, directed/undirected toggles, or built-in algorithms like shortest path and cycle detection.
Use a simple slice of edges when you only need to iterate over all connections once and do not care about lookup speed.
Sparse graphs love maps. Dense graphs love matrices. Don't over-engineer the structure before you measure the bottleneck.