Graphs: BFS & DFS

Represent networks, grids and dependencies as graphs, then explore them depth-first or breadth-first, including shortest paths in unweighted graphs.

Kinds of graphs#

Property	Meaning	Example
undirected	edges go both ways	friendships
directed	edges have a direction	"course A is required before B"
weighted	edges have a cost	road distances
cyclic / acyclic	whether you can return to a node	dependencies should be acyclic
implicit	edges computed on the fly	a grid: each cell connects to its 4 neighbors

Representing a graph in Go#

Representation	Go type	Memory	Best for
adjacency list	`[][]int` (nodes are 0..n-1)	O(n + m)	almost everything
adjacency list with any keys	`map[string][]string`	O(n + m)	named nodes
adjacency matrix	`[][]bool`	O(n²)	dense graphs, "is there an edge u→v?" in O(1)
grid	`[][]byte` plus a direction list	O(rows·cols)	maps, mazes, images

Building an undirected adjacency list from an edge list:

adj := make([][]int, n)
for _, e := range edges {
	adj[e[0]] = append(adj[e[0]], e[1])
	adj[e[1]] = append(adj[e[1]], e[0]) // omit for directed graphs
}

Try it

Build the graph used in the BFS trace below, then print each node's neighbors and look up a single edge:

adjacency.go

package main
 
import (
	"fmt"
	"slices"
)
 
func main() {
	n := 6
	edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {4, 5}}
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		adj[e[1]] = append(adj[e[1]], e[0])
	}
	for u, nbrs := range adj {
		fmt.Printf("%d: %v (degree %d)\n", u, nbrs, len(nbrs))
	}
	fmt.Println("edge 1-4?", slices.Contains(adj[1], 4), " edge 3-5?", slices.Contains(adj[3], 5))
 
	// Named nodes: a map of slices.
	follows := map[string][]string{"ana": {"bo", "cy"}, "bo": {"cy"}}
	fmt.Println("ana follows", follows["ana"], "| dee follows", follows["dee"])
}

Output

0: [1 2] (degree 2)
1: [0 3 4] (degree 3)
2: [0 4] (degree 2)
3: [1] (degree 1)
4: [1 2 5] (degree 3)
5: [4] (degree 1)
edge 1-4? true  edge 3-5? false
ana follows [bo cy] | dee follows []

Looking up follows["dee"] returns a nil slice, so nodes without edges need no special handling.

Depth-first search#

DFS follows one path as deep as it can, then backtracks. Recursion makes it short:

var dfs func(u int)
dfs = func(u int) {
	visited[u] = true
	for _, v := range adj[u] {
		if !visited[v] {
			dfs(v)
		}
	}
}

Use DFS for: connectivity ("which nodes can I reach?"), counting components (islands), flood fill, cycle detection, and anything where the order of discovery within a path matters.

Run the trace

Each call prints when it enters a node, indented by recursion depth, and when it backtracks. DFS follows 0 → 1 → 3, hits a dead end, backs up to 1, and continues to 4:

dfs_trace.go

package main
 
import (
	"fmt"
	"strings"
)
 
func main() {
	adj := [][]int{{1, 2}, {0, 3, 4}, {0, 4}, {1}, {1, 2, 5}, {4}}
	visited := make([]bool, len(adj))
	var dfs func(u, depth int)
	dfs = func(u, depth int) {
		pad := strings.Repeat("  ", depth)
		visited[u] = true
		fmt.Printf("%svisit %d\n", pad, u)
		for _, v := range adj[u] {
			if !visited[v] {
				dfs(v, depth+1)
			}
		}
		fmt.Printf("%sdone with %d\n", pad, u)
	}
	dfs(0, 0)
}

Output

visit 0
  visit 1
    visit 3
    done with 3
    visit 4
      visit 2
      done with 2
      visit 5
      done with 5
    done with 4
  done with 1
done with 0

Breadth-first search#

BFS uses a queue. Start with the source; repeatedly take the front node and enqueue its unvisited neighbors. Nodes come out in order of distance from the source, so the first time BFS reaches a node is via a shortest path (fewest edges).

Trace on this graph, starting at 0:

0 — 1 — 3
|   |
2 — 4 — 5

dequeue	enqueue (unvisited neighbors)	queue after	dist
	start	[0]	0:0
0	1, 2	[1 2]	1:1, 2:1
1	3, 4	[2 3 4]	3:2, 4:2
2	(4 already queued)	[3 4]
3		[4]
4	5	[5]	5:3
5		[]

Node 5 is 3 edges away. Notice node 4 was reached from 1 first; when 2 also pointed at it, it was already marked, which is why you mark on enqueue.

Run the trace

bfs_trace.go

package main
 
import "fmt"
 
func main() {
	adj := [][]int{{1, 2}, {0, 3, 4}, {0, 4}, {1}, {1, 2, 5}, {4}}
	dist := []int{0, -1, -1, -1, -1, -1} // -1 = not reached yet
	queue := []int{0}
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		var added []int
		for _, v := range adj[u] {
			if dist[v] == -1 { // mark on enqueue
				dist[v] = dist[u] + 1
				queue = append(queue, v)
				added = append(added, v)
			}
		}
		fmt.Printf("dequeue %d (dist %d)  enqueue %-6s queue %v\n", u, dist[u], fmt.Sprint(added), queue)
	}
	fmt.Println("dist:", dist)
}

Output

dequeue 0 (dist 0)  enqueue [1 2]  queue [1 2]
dequeue 1 (dist 1)  enqueue [3 4]  queue [2 3 4]
dequeue 2 (dist 1)  enqueue []     queue [3 4]
dequeue 3 (dist 2)  enqueue []     queue [4]
dequeue 4 (dist 2)  enqueue [5]    queue [5]
dequeue 5 (dist 3)  enqueue []     queue []
dist: [0 1 1 2 2 3]

Grids are graphs#

Each cell is a node; neighbors are the cells up, down, left and right. Keep the four directions in a slice, and check bounds before indexing:

var dirs = [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for _, d := range dirs {
	nr, nc := r+d[0], c+d[1]
	if nr < 0 || nc < 0 || nr >= rows || nc >= cols {
		continue
	}
	// visit (nr, nc)
}

You can often mark visited cells by changing the grid itself (sinking land to water), saving a separate visited array.

Try it: flood fill

Each island is filled with its own letter, so you can see which cells DFS reached from each starting point:

floodfill.go

package main
 
import "fmt"
 
func main() {
	grid := [][]byte{
		[]byte("11000"),
		[]byte("11010"),
		[]byte("00011"),
		[]byte("10000"),
	}
	rows, cols := len(grid), len(grid[0])
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
 
	var fill func(r, c int, mark byte) int
	fill = func(r, c int, mark byte) int {
		if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1' {
			return 0
		}
		grid[r][c] = mark // visited: overwrite the land
		size := 1
		for _, d := range dirs {
			size += fill(r+d[0], c+d[1], mark)
		}
		return size
	}
 
	mark := byte('A')
	for r := range rows {
		for c := range cols {
			if grid[r][c] == '1' {
				fmt.Printf("island %c starts at (%d,%d), size %d\n", mark, r, c, fill(r, c, mark))
				mark++
			}
		}
	}
	for _, row := range grid {
		fmt.Println(string(row))
	}
}

Output

island A starts at (0,0), size 4
island B starts at (1,3), size 3
island C starts at (3,0), size 1
AA000
AA0B0
000BB
C0000

Step through it

Edit the maze (# is a wall, rows are separated by /). Block every route to see BFS report that no path exists.

InteractiveBFS on a grid: shortest pathBFS explores in rings of equal distance, so the first time it reaches E is along a shortest path. Edit the maze: # is a wall.

queue 1

S



							E

Start with S in the queue at distance 0. Numbers show the distance from S; outlined cells are waiting in the queue.

1 / 27

Multi-source BFS#

When several sources spread at the same speed (rotting oranges, fire, distance to the nearest exit), put all of them in the queue at the start. BFS then computes, for every cell, the distance to the nearest source. Processing the queue level by level counts the minutes.

Run the trace

Rotting oranges, printed minute by minute: 2 is rotten, 1 is fresh, 0 is empty. Every rotten orange starts in the queue, and each round of the loop processes exactly one minute:

multisource_trace.go

package main
 
import "fmt"
 
func show(g [][]int) {
	for _, row := range g {
		fmt.Println(" ", row)
	}
}
 
func main() {
	g := [][]int{
		{2, 1, 1},
		{1, 1, 0},
		{0, 1, 2},
	}
	var queue [][2]int
	for r := range g {
		for c := range g[r] {
			if g[r][c] == 2 {
				queue = append(queue, [2]int{r, c}) // every source at once
			}
		}
	}
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	fmt.Println("minute 0:")
	show(g)
	for minute := 1; len(queue) > 0; minute++ {
		var next [][2]int
		for _, p := range queue {
			for _, d := range dirs {
				r, c := p[0]+d[0], p[1]+d[1]
				if r >= 0 && c >= 0 && r < len(g) && c < len(g[0]) && g[r][c] == 1 {
					g[r][c] = 2
					next = append(next, [2]int{r, c})
				}
			}
		}
		if len(next) == 0 {
			break
		}
		fmt.Printf("minute %d:\n", minute)
		show(g)
		queue = next
	}
}

Output

minute 0:
  [2 1 1]
  [1 1 0]
  [0 1 2]
minute 1:
  [2 2 1]
  [2 1 0]
  [0 2 2]
minute 2:
  [2 2 2]
  [2 2 0]
  [0 2 2]

Word Ladder: BFS on an implicit graph#

"Transform hit into cog, changing one letter at a time, where every intermediate word must be in the dictionary. What is the fewest number of words in the sequence?" No graph is given, but there is one: words are nodes, and two words are neighbors if they differ in exactly one letter. Fewest steps with equal-cost moves means BFS.

Comparing every pair of words to build the edges is O(n² · L). Instead, generate neighbors on demand: for each position, try all 26 letters and keep the results that are in the dictionary set. That is O(26 · L) per word.

hit → hot → dot → dog → cog        (5 words)

wordladder.go

package main
 
import "fmt"
 
func ladderLength(begin, end string, wordList []string) (int, []string) {
	dict := make(map[string]bool, len(wordList))
	for _, w := range wordList {
		dict[w] = true
	}
	if !dict[end] {
		return 0, nil
	}
	prev := map[string]string{begin: ""} // also serves as the visited set
	queue := []string{begin}
	for steps := 1; len(queue) > 0; steps++ {
		for range len(queue) { // one BFS level
			w := queue[0]
			queue = queue[1:]
			if w == end {
				var path []string
				for x := end; x != ""; x = prev[x] {
					path = append([]string{x}, path...)
				}
				return steps, path
			}
			b := []byte(w)
			for i := range b {
				orig := b[i]
				for c := byte('a'); c <= 'z'; c++ {
					if c == orig {
						continue
					}
					b[i] = c
					next := string(b)
					if _, seen := prev[next]; dict[next] && !seen {
						prev[next] = w // mark when enqueuing
						queue = append(queue, next)
					}
				}
				b[i] = orig
			}
		}
	}
	return 0, nil
}
 
func main() {
	words := []string{"hot", "dot", "dog", "lot", "log", "cog"}
	fmt.Println(ladderLength("hit", "cog", words))
	fmt.Println(ladderLength("hit", "cog", []string{"hot", "dot", "dog", "lot", "log"}))
}

Output

5 [hit hot dot dog cog]
0 []

The same "implicit graph" thinking solves Open the Lock (states are 4-digit codes, neighbors turn one wheel), Minimum Genetic Mutation, and sliding puzzles. When both the start and the goal are known, bidirectional BFS (searching from both ends and stopping when the frontiers meet) explores far fewer states.

The full program#

graphs.go

package main
 
import "fmt"
 
var dirs = [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
 
func bfsDistances(adj [][]int, src int) []int {
	dist := make([]int, len(adj))
	for i := range dist {
		dist[i] = -1 // -1 means unvisited
	}
	dist[src] = 0
	q := []int{src}
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		for _, v := range adj[u] {
			if dist[v] == -1 {
				dist[v] = dist[u] + 1 // mark on enqueue
				q = append(q, v)
			}
		}
	}
	return dist
}
 
func countComponents(adj [][]int) int {
	visited := make([]bool, len(adj))
	var dfs func(u int)
	dfs = func(u int) {
		visited[u] = true
		for _, v := range adj[u] {
			if !visited[v] {
				dfs(v)
			}
		}
	}
	count := 0
	for u := range adj {
		if !visited[u] {
			count++
			dfs(u)
		}
	}
	return count
}
 
func numIslands(grid [][]byte) int {
	rows, cols := len(grid), len(grid[0])
	var sink func(r, c int)
	sink = func(r, c int) {
		if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1' {
			return
		}
		grid[r][c] = '0'
		for _, d := range dirs {
			sink(r+d[0], c+d[1])
		}
	}
	count := 0
	for r := range rows {
		for c := range cols {
			if grid[r][c] == '1' {
				count++
				sink(r, c)
			}
		}
	}
	return count
}
 
func orangesRotting(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	var q [][2]int
	fresh := 0
	for r := range rows {
		for c := range cols {
			switch grid[r][c] {
			case 2:
				q = append(q, [2]int{r, c}) // every rotten orange is a source
			case 1:
				fresh++
			}
		}
	}
	minutes := 0
	for len(q) > 0 && fresh > 0 {
		var next [][2]int
		for _, cell := range q {
			for _, d := range dirs {
				r, c := cell[0]+d[0], cell[1]+d[1]
				if r >= 0 && c >= 0 && r < rows && c < cols && grid[r][c] == 1 {
					grid[r][c] = 2
					fresh--
					next = append(next, [2]int{r, c})
				}
			}
		}
		q = next
		minutes++
	}
	if fresh > 0 {
		return -1
	}
	return minutes
}
 
func main() {
	n := 6
	edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {4, 5}}
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		adj[e[1]] = append(adj[e[1]], e[0])
	}
	fmt.Println("distances from 0:", bfsDistances(adj, 0))
 
	adj2 := [][]int{{1}, {0}, {3}, {2}, {}}
	fmt.Println("components:", countComponents(adj2))
 
	grid := [][]byte{
		[]byte("11000"),
		[]byte("11000"),
		[]byte("00100"),
		[]byte("00011"),
	}
	fmt.Println("islands:", numIslands(grid))
 
	oranges := [][]int{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}
	fmt.Println("minutes to rot:", orangesRotting(oranges))
	fmt.Println("impossible case:", orangesRotting([][]int{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}))
}

Output

distances from 0: [0 1 1 2 2 3]
components: 3
islands: 3
minutes to rot: 4
impossible case: -1

Complexity#

With n nodes and m edges (for a grid, n = rows × cols and m ≈ 4n):

Algorithm	Time	Space
BFS	O(n + m)	O(n) queue and distances
DFS	O(n + m)	O(n) recursion depth worst case
islands, flood fill, rotting oranges	O(rows · cols)	O(rows · cols)

Recognizing the pattern#

"shortest", "minimum steps", "fewest moves" with equal-cost steps: BFS.
"connected", "reachable", "count groups", "fill a region": DFS (or BFS; both work).
States that are not obviously a graph (word transformations, lock combinations, board positions) become one when you define "neighbor" as "one move away". Then BFS gives the minimum number of moves.

Summary#

Graphs are nodes plus edges; store them as adjacency lists ([][]int) in most problems.
DFS goes deep: connectivity, components, flood fill.
BFS goes level by level with a queue: shortest paths in unweighted graphs.
Grids are implicit graphs with four (or eight) neighbors per cell.
Multi-source BFS starts with every source in the queue.

Kinds of graphs#

Representing a graph in Go#

Try it

Depth-first search#

Run the trace

Breadth-first search#

Run the trace

Grids are graphs#

Try it: flood fill

Step through it

Multi-source BFS#

Run the trace

Word Ladder: BFS on an implicit graph#

The full program#

Complexity#

Recognizing the pattern#

Summary#

Check your understanding

Practice in Go