When I first started implementing graphs in Go, I fell into the "Java Trap." I spent hours designing these elaborate Node structs that held pointers to a slice of other Node structs. It felt "object-oriented" and intuitive. But in practice, it's a nightmare. Managing those pointers leads to circular reference headaches, makes debugging a slog because you're staring at memory addresses in the debugger, and frankly, it's not how we do things in Go.

Stop trying to build graphs with pointer-heavy Node structs

If you try to build a graph by linking objects together via pointers, you'll find that simple tasks—like checking if a node has been visited—require you to add a Visited bool field to your struct. But then what happens when you want to run two searches concurrently? You're stuck. You can't just reset the boolean without locking the whole graph.

// The "Wrong" Way (Don't do this)
type Node struct {
    Value    string
    Children []*Node
    Visited  bool // This is a disaster for concurrency or multiple passes
}

The better way—the Go way—is to decouple the topology of the graph from the state of your search. We use an adjacency list. In Go, the most flexible version of this is a map where the keys are your unique identifiers (like strings or ints) and the values are slices of those identifiers.

The Adjacency List: Leveraging Maps for Flexibility

By using a map[string][]string, the graph becomes a simple lookup table. If you need to know who "Station A" is connected to, you just hit the map. It's clean, it's fast, and it keeps your data separate from your logic.

type Graph struct {
    nodes map[string][]string
}

func NewGraph() *Graph {
    return &Graph{nodes: make(map[string][]string)}
}

func (g *Graph) AddEdge(u, v string) {
    g.nodes[u] = append(g.nodes[u], v)
    // For an undirected graph, add the reverse edge too:
    // g.nodes[v] = append(g.nodes[v], u)
}

BFS: Finding the Shortest Path with a Queue

Breadth-First Search is all about layers. Imagine you're dropping a pebble in a pond; the ripples move outward. In Go, we implement this using a slice as a queue. The key here is the visited map. Notice how it's created inside the search function, not stored on the graph itself. This allows multiple goroutines to search the same graph simultaneously without stepping on each other's toes.

func (g *Graph) BFS(start string) {
    visited := make(map[string]bool)
    queue := []string{start}
    visited[start] = true

    for len(queue) > 0 {
        // Dequeue the first element
        curr := queue[0]
        queue = queue[1:]
        fmt.Println("Visited:", curr)

        for _, neighbor := range g.nodes[curr] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

DFS: Diving Deep with Recursion

While BFS is about breadth, Depth-First Search is about exploration. It's the "go down this hallway until you hit a wall, then backtrack" approach. Recursion is the most natural way to write this in Go, though you can use a stack if you're worried about extremely deep graphs and stack overflows (though for most real-world data, recursion is just fine).

func (g *Graph) DFS(start string) {
    visited := make(map[string]bool)
    g.dfsRecursive(start, visited)
}

func (g *Graph) dfsRecursive(curr string, visited map[string]bool) {
    visited[curr] = true
    fmt.Println("Visited:", curr)

    for _, neighbor := range g.nodes[curr] {
        if !visited[neighbor] {
            g.dfsRecursive(neighbor, visited)
        }
    }
}

I'll leave you with a tip: if you're implementing these for a production system, consider using a map[int][]int if your nodes can be mapped to integers. It's significantly faster than using strings as keys. But for most logic problems, the string map is the gold standard for readability.

📋 Practical Task

Exercise: Implementing a Social Network Connection Validator

You are building a simplified "Connection Validator" for a professional networking site. Your goal is to determine if two users are connected through any chain of mutual connections.

Requirements:

• Implement a Network struct using an adjacency list (map).
• Implement a method AddConnection(user1, user2 string) that creates a bidirectional link between two users.
• Implement a method AreConnected(startUser, targetUser string) bool. This method should use either BFS or DFS to return true if there is a path between the two users, and false otherwise.

Test Case:

net := NewNetwork()
net.AddConnection("Alice", "Bob")
net.AddConnection("Bob", "Charlie")
net.AddConnection("David", "Eve")

fmt.Println(net.AreConnected("Alice", "Charlie")) // Expected: true
fmt.Println(net.AreConnected("Alice", "Eve"))     // Expected: false