Home / Data Structures / Graph

Data Structures

Graph

Guide

A graph is a set of nodes and the connections between them, stored as a map from each node to its neighbors.

The shape

Adjacency map

Every node maps to the list of nodes it connects to.

AddEdge: append each node to the other one's list.
Neighbors: read one node's list back.
Degree: count the entries in that list.

start in the queue reached

The panel is the map the code actually stores. Hop outward a ring at a time, numbering cities by how many roads away they are.

Purpose

Record which things connect to which, and read those connections back.

Input

Edges added a pair at a time, as two string node names.

Output

The neighbors of any node, and how many it has.

Constraints

Edges here run both ways, so each one is stored twice, once under each end.
Adding the same edge again stores the pair twice. Guard it where duplicates matter.
A node's neighbors come back in the order they were added. The nodes themselves come back in map order, which is random.

How a graph is stored

A graph is a set of things and the connections between them. Cities joined by roads, people who know each other, pages that link to pages.

You store it as a map from each node to the nodes it touches, and everything else is following those lists. Nodes with no path between them stay separate.

\sum_{v \in V} \deg(v) = 2|E|

Every edge gets counted at both ends, so the degrees always add up to twice the number of edges.

What a graph keeps track of

Name	Type	What it is for
Graph	struct	Holds the whole thing.
edges	map[string][]string	For every node, the nodes it connects to.
node	string	One thing in the graph. A city here.
edge	a pair of nodes	One connection. A road between two cities.
seen	map[string]bool	Nodes already visited, so a loop cannot trap the walk.

Walk through it

1 Start with a map from each node to its neighbors

The keys are the nodes. Each value is the list of nodes you can step to from there.

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

g := &Graph{edges: map[string][]string{}}

2 Record an edge at both ends

Appending in both directions is what makes the graph undirected. Record it one way only and you have a one-way street.

func (g *Graph) AddEdge(a, b string) {
    g.edges[a] = append(g.edges[a], b)
    g.edges[b] = append(g.edges[b], a)
}

3 Ask a node who it touches

A missing key gives the zero value, and ranging a nil slice runs zero times. An unknown city needs no special case.

func (g *Graph) Neighbors(n string) []string {
    return g.edges[n]
}

func (g *Graph) Degree(n string) int {
    return len(g.edges[n])
}

4 Keep a queue and a record of what you have seen

Marking a node as it joins the queue is what stops a cycle looping forever.

seen := map[string]bool{start: true}
queue := []string{start}

5 Follow the links until the queue empties

Take a node off the front, add unseen neighbors, repeat. seen ends up holding everything reachable.

for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]

    for _, next := range g.edges[node] {
        if !seen[next] {
            seen[next] = true
            queue = append(queue, next)
        }
    }
}

The whole program

Five roads between seven cities, then three questions about them.

package main

import (
    "fmt"
    "slices"
)

// Graph stores, for every node, the nodes it connects to.
type Graph struct {
    edges map[string][]string
}

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

// AddEdge links a and b in both directions, which is what makes this graph
// undirected. Record it one way only and you have a directed graph.
func (g *Graph) AddEdge(a, b string) {
    g.edges[a] = append(g.edges[a], b)
    g.edges[b] = append(g.edges[b], a)
}

// Neighbors returns the nodes one hop from n.
func (g *Graph) Neighbors(n string) []string {
    return g.edges[n]
}

// Degree is how many edges touch n.
func (g *Graph) Degree(n string) int {
    return len(g.edges[n])
}

// Reachable lists every node you can get to from start.
func (g *Graph) Reachable(start string) []string {
    seen := map[string]bool{start: true}
    queue := []string{start}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        for _, next := range g.edges[node] {
            if !seen[next] {
                seen[next] = true
                queue = append(queue, next)
            }
        }
    }

    found := make([]string, 0, len(seen))
    for node := range seen {
        found = append(found, node)
    }
    slices.Sort(found)
    return found
}

func main() {
    g := NewGraph()
    g.AddEdge("Providence", "Boston")
    g.AddEdge("Boston", "Hartford")
    g.AddEdge("Hartford", "New Haven")
    g.AddEdge("New Haven", "New York")
    g.AddEdge("Portland", "Bangor")

    fmt.Println(g.Neighbors("Hartford"))
    fmt.Println(g.Degree("Boston"))
    fmt.Println(g.Reachable("Providence"))
    fmt.Println(g.Reachable("Portland"))
}

Terminal

$ go run main.go
[Boston New Haven]
2
[Boston Hartford New Haven New York Providence]
[Bangor Portland]

Breadth-First Search The queue walk in step 5, on its own page.Depth-First Search The same walk with a stack, going deep before wide.Dijkstra's Algorithm The shortest route once the roads have lengths.Maps Why reading a missing key is safe, and what nil ranges to.

Previous Insertion Sort Next Topic Breadth-First Search