Introduction

In part 1 we covered Lists, in part 2 we covered Trees, in part 3 we covered Hash Tables, and in part 4 we covered Heaps and Priority Queues. Now we move into one of the most versatile structures in computer science: Graphs.

Graphs model relationships. Social networks, road maps, dependency trees, recommendation systems, and even the internet itself are graphs. When you need to represent connections between things, graphs are the natural fit.

As mentioned at the end of part 4, graphs connect naturally with priority queues because many graph algorithms (like Dijkstra's shortest path) rely on them.

As in previous articles, we keep the same base Container interface:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

What is a Graph?

A Graph is a collection of vertices (also called nodes) connected by edges. Unlike trees, graphs have no strict hierarchy and can contain cycles.

graph LR
  A((A)) --- B((B))
  A --- C((C))
  B --- D((D))
  C --- D
  D --- E((E))

Key terminology:

• Vertex (Node): an entity in the graph
• Edge: a connection between two vertices
• Directed vs Undirected: edges can have direction (A → B) or be bidirectional (A — B)
• Weighted vs Unweighted: edges can carry a cost/distance value
• Adjacent: two vertices connected by an edge
• Degree: number of edges connected to a vertex

Types of Graphs

Undirected Graph

Edges have no direction. If A connects to B, then B connects to A.

graph LR
  A((A)) --- B((B))
  B --- C((C))
  A --- C

Directed Graph (Digraph)

Edges have direction. A → B doesn't imply B → A.

graph LR
  A((A)) --> B((B))
  B --> C((C))
  C --> A

Weighted Graph

Edges carry a cost, distance or weight.

graph LR
  A((A)) ---|5| B((B))
  B ---|3| C((C))
  A ---|10| C

Graph Representation

There are two common ways to represent a graph in memory.

Adjacency List

Each vertex stores a list of its neighbors. This is memory-efficient for sparse graphs (few edges relative to vertices).

flowchart LR
  subgraph AdjList["Adjacency List"]
    A["A: [B, C]"]
    B["B: [A, D]"]
    C["C: [A, D]"]
    D["D: [B, C, E]"]
    E["E: [D]"]
  end

• Space: O(V + E) where V = vertices, E = edges
• Check if edge exists: O(degree) on average
• Iterate neighbors: O(degree)

Adjacency Matrix

A 2D matrix where matrix[i][j] indicates an edge between vertex i and vertex j. Better for dense graphs.

flowchart TD
  subgraph Matrix["Adjacency Matrix"]
    M["    A B C D E
    A [ 0 1 1 0 0 ]
    B [ 1 0 0 1 0 ]
    C [ 1 0 0 1 0 ]
    D [ 0 1 1 0 1 ]
    E [ 0 0 0 1 0 ]"]
  end

• Space: O(V²)
• Check if edge exists: O(1)
• Iterate neighbors: O(V)

When to use which

Operation	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add edge	O(1)	O(1)
Remove edge	O(degree)	O(1)
Check edge	O(degree)	O(1)
Iterate neighbors	O(degree)	O(V)

Use adjacency list for sparse graphs (most real-world graphs). Use adjacency matrix when you need fast edge lookups and the graph is dense.

Practical Go implementation (Graph)

We'll implement an adjacency list representation with support for weighted edges.

type Edge struct {
  To     string
  Weight int
}

type Graph struct {
  vertices map[string][]Edge
  directed bool
}

func NewGraph(directed bool) *Graph {
  return &Graph{
    vertices: make(map[string][]Edge),
    directed: directed,
  }
}

func (g *Graph) Empty() bool {
  return len(g.vertices) == 0
}

func (g *Graph) Size() int {
  return len(g.vertices)
}

func (g *Graph) Clear() {
  g.vertices = make(map[string][]Edge)
}

func (g *Graph) Values() []interface{} {
  result := make([]interface{}, 0, len(g.vertices))
  for v := range g.vertices {
    result = append(result, v)
  }
  return result
}

func (g *Graph) String() string {
  return fmt.Sprintf("%v", g.vertices)
}

func (g *Graph) AddVertex(v string) {
  if _, exists := g.vertices[v]; !exists {
    g.vertices[v] = []Edge{}
  }
}

func (g *Graph) AddEdge(from, to string, weight int) {
  g.AddVertex(from)
  g.AddVertex(to)

  g.vertices[from] = append(g.vertices[from], Edge{To: to, Weight: weight})

  if !g.directed {
    g.vertices[to] = append(g.vertices[to], Edge{To: from, Weight: weight})
  }
}

func (g *Graph) Neighbors(v string) []Edge {
  return g.vertices[v]
}

func (g *Graph) HasEdge(from, to string) bool {
  for _, edge := range g.vertices[from] {
    if edge.To == to {
      return true
    }
  }
  return false
}

func (g *Graph) Vertices() []string {
  keys := make([]string, 0, len(g.vertices))
  for k := range g.vertices {
    keys = append(keys, k)
  }
  return keys
}

Imports used:

import "fmt"

Graph Traversal

Traversal means visiting all vertices in a graph systematically. The two fundamental approaches are BFS and DFS.

Breadth-First Search (BFS)

BFS explores the graph level by level. It visits all neighbors of the current vertex before moving deeper. Uses a queue.

flowchart TD
  A["Start at source"] --> B["Add to queue"]
  B --> C["While queue not empty"]
  C --> D["Dequeue vertex"]
  D --> E["Process vertex"]
  E --> F["Enqueue unvisited neighbors"]
  F --> C

BFS is ideal for:

• Finding shortest path in unweighted graphs
• Level-order traversal
• Finding all vertices within k edges

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

  visited[start] = true

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

    result = append(result, vertex)

    for _, edge := range g.vertices[vertex] {
      if !visited[edge.To] {
        visited[edge.To] = true
        queue = append(queue, edge.To)
      }
    }
  }

  return result
}

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking. It follows one path until it can't continue, then returns to explore other branches. Uses a stack (or recursion).

flowchart TD
  A["Start at source"] --> B["Mark as visited"]
  B --> C["Process vertex"]
  C --> D["For each unvisited neighbor"]
  D --> E["Recursively DFS"]
  E --> D

DFS is ideal for:

• Detecting cycles
• Topological sorting
• Finding connected components
• Maze solving

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

  g.dfsRecursive(start, visited, &result)

  return result
}

func (g *Graph) dfsRecursive(vertex string, visited map[string]bool, result *[]string) {
  visited[vertex] = true
  *result = append(*result, vertex)

  for _, edge := range g.vertices[vertex] {
    if !visited[edge.To] {
      g.dfsRecursive(edge.To, visited, result)
    }
  }
}

Iterative version using explicit stack:

func (g *Graph) DFSIterative(start string) []string {
  visited := make(map[string]bool)
  result := []string{}
  stack := []string{start}

  for len(stack) > 0 {
    vertex := stack[len(stack)-1]
    stack = stack[:len(stack)-1]

    if visited[vertex] {
      continue
    }

    visited[vertex] = true
    result = append(result, vertex)

    neighbors := g.vertices[vertex]
    for i := len(neighbors) - 1; i >= 0; i-- {
      if !visited[neighbors[i].To] {
        stack = append(stack, neighbors[i].To)
      }
    }
  }

  return result
}

BFS vs DFS

Aspect	BFS	DFS
Data structure	Queue	Stack/Recursion
Space complexity	O(V) worst case	O(V) worst case
Shortest path (unweighted)	Yes	No
Memory usage	Higher for wide graphs	Higher for deep graphs
Use case	Level traversal, shortest path	Cycle detection, topological sort

Shortest Path: Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.

This is where priority queues from part 4 come in. Dijkstra uses a min-heap to always process the vertex with the smallest known distance.

flowchart TD
  A["Initialize distances to infinity"] --> B["Set source distance to 0"]
  B --> C["Add source to priority queue"]
  C --> D["While queue not empty"]
  D --> E["Extract vertex with min distance"]
  E --> F["For each neighbor"]
  F --> G{"new distance < current?"}
  G -->|Yes| H["Update distance"]
  H --> I["Add to queue"]
  I --> F
  G -->|No| F
  F --> D

Why it works

Dijkstra is a greedy algorithm. It always picks the unvisited vertex with the smallest distance. Because all edge weights are non-negative, once a vertex is processed, its shortest distance is final.

Practical Go implementation

type DijkstraResult struct {
  Distance map[string]int
  Previous map[string]string
}

type pqItem struct {
  vertex   string
  distance int
}

type minHeap []pqItem

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *minHeap) Push(x interface{}) {
  *h = append(*h, x.(pqItem))
}

func (h *minHeap) Pop() interface{} {
  old := *h
  n := len(old)
  item := old[n-1]
  *h = old[:n-1]
  return item
}

func (g *Graph) Dijkstra(start string) DijkstraResult {
  dist := make(map[string]int)
  prev := make(map[string]string)

  for v := range g.vertices {
    dist[v] = math.MaxInt
  }
  dist[start] = 0

  pq := &minHeap{{vertex: start, distance: 0}}
  heap.Init(pq)

  processed := make(map[string]bool)

  for pq.Len() > 0 {
    item := heap.Pop(pq).(pqItem)
    u := item.vertex

    if processed[u] {
      continue
    }
    processed[u] = true

    for _, edge := range g.vertices[u] {
      alt := dist[u] + edge.Weight

      if alt < dist[edge.To] {
        dist[edge.To] = alt
        prev[edge.To] = u
        heap.Push(pq, pqItem{vertex: edge.To, distance: alt})
      }
    }
  }

  return DijkstraResult{Distance: dist, Previous: prev}
}

func (r DijkstraResult) PathTo(target string) []string {
  path := []string{}
  current := target

  for current != "" {
    path = append([]string{current}, path...)
    current = r.Previous[current]
  }

  return path
}

Additional imports:

import (
  "container/heap"
  "math"
)

Complexity

• Time: O((V + E) log V) with a binary heap
• Space: O(V) for distance and previous maps

Limitations

Dijkstra doesn't work with negative edge weights. For that, you'd need Bellman-Ford (which is slower at O(V * E)).

Cycle Detection

Detecting cycles is a common graph operation, especially important for dependency resolution and deadlock detection.

In Directed Graphs

Use DFS with three states: unvisited, visiting (in current path), visited (completely processed).

func (g *Graph) HasCycle() bool {
  white := make(map[string]bool) // unvisited
  gray := make(map[string]bool)  // visiting
  black := make(map[string]bool) // visited

  for v := range g.vertices {
    white[v] = true
  }

  for v := range g.vertices {
    if white[v] {
      if g.hasCycleDFS(v, white, gray, black) {
        return true
      }
    }
  }

  return false
}

func (g *Graph) hasCycleDFS(v string, white, gray, black map[string]bool) bool {
  white[v] = false
  gray[v] = true

  for _, edge := range g.vertices[v] {
    if gray[edge.To] {
      return true
    }
    if white[edge.To] && g.hasCycleDFS(edge.To, white, gray, black) {
      return true
    }
  }

  gray[v] = false
  black[v] = true

  return false
}

Real-world use cases

• Social networks: friends, followers, connections
• Maps and navigation: roads, routes, shortest paths
• Dependency management: package dependencies, build order
• Web crawling: pages and links
• Recommendation systems: user-item relationships
• Network routing: routers and connections
• Game AI: pathfinding in game maps

Choosing the right algorithm

Problem	Algorithm
Visit all nodes	BFS or DFS
Shortest path (unweighted)	BFS
Shortest path (weighted, non-negative)	Dijkstra
Shortest path (negative weights)	Bellman-Ford
Detect cycles	DFS with coloring
Topological sort	DFS
Minimum spanning tree	Prim or Kruskal

Conclusion

Graphs are one of the most flexible structures for modeling relationships. Their power comes from the variety of algorithms that operate on them efficiently.

In this article we covered graph representation (adjacency list vs matrix), traversal (BFS and DFS), shortest path (Dijkstra), and cycle detection. The priority queue from part 4 showed up naturally in Dijkstra's algorithm.

This concludes our data structures series. We've gone from basic Lists through Trees, Hash Tables, Heaps, and now Graphs. Each structure optimizes for different access patterns and operations. The key skill is recognizing which structure fits your problem.