Graph traversal: BFS and DFS

A graph is nodes connected by edges: road networks, social follows, service dependencies, grids in a puzzle. Most graph problems start with a traversal — visiting every node reachable from a start — in one of two orders.

#Breadth-first search

BFS uses a queue. It visits the start, then all its neighbours, then all of theirs, expanding level by level like ripples in water. Because it reaches every node at distance 1 before any at distance 2, the first time it finds a node is along a shortest path in an unweighted graph.

queue := []string{start}
dist := map[string]int{start: 0}
for len(queue) > 0 {
	n := queue[0]
	queue = queue[1:]
	for _, next := range graph[n] {
		if _, seen := dist[next]; !seen {
			dist[next] = dist[n] + 1
			queue = append(queue, next)
		}
	}
}

Use it for minimum steps, levels in a tree, degrees of separation, and the nearest matching node.

#Depth-first search

DFS uses a stack — usually the call stack, through recursion. It follows one path as deep as possible, then backtracks. Use it to explore everything reachable, count connected components (flood fill), detect cycles, enumerate paths, and compute a topological order: listing tasks so that every task comes after its dependencies, which is how build systems, package managers and migration tools decide what runs first.

Very deep recursion can overflow the stack in some languages; an explicit stack avoids that. (Go grows goroutine stacks dynamically up to a large limit, so recursion depth is rarely the issue in practice, but memory still is.)

#The rules that apply to both

• Track visited nodes. Without a visited set, a cycle makes the traversal loop forever, and shared nodes are processed repeatedly.
• Cost is O(V + E): every vertex and every edge is handled once.
• Weighted edges need a different algorithm. BFS gives shortest paths only when every edge costs the same; with weights, use Dijkstra's algorithm (a BFS with a priority queue).

Store graphs as adjacency lists — a map from each node to its neighbours. The algorithms lesson works through both traversals in Go.