Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Basic Implementation

basic.go

package main

import "fmt"

func main() {
	adj := map[int][]int{
		1: {2, 3},
		2: {1, 4},
		3: {1, 4},
		4: {2, 3, 5},
		5: {4, 6},
		6: {5},
	}
	start := 1
	visited := map[int]bool{start: true}
	queue := []int{start}
	order := []int{}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		order = append(order, v)
		for _, nb := range adj[v] {
			if !visited[nb] {
				visited[nb] = true
				queue = append(queue, nb)
			}
		}
	}
	fmt.Println(order)
}

BFS uses a queue, so it visits the start vertex, then its neighbours, then the next layer.

Step 1 - Start at 1

The queue starts with [1] and visited starts with {1}.

Step 2 - Visit the first layer

After processing 1, neighbours 2 and 3 are marked and queued.

Step 3 - Deterministic visit order

With insertion-ordered neighbours, BFS visits [1, 2, 3, 4, 5, 6].

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Go: map[int][]int is the idiomatic adjacency list and keeps the vertex iteration shape visible; the lesson does not lean on container/list or any third-party graph package.
A map[int]bool is the explicit "visited" set; the queue is a plain []int slice with queue[0] / queue[1:] for dequeue and append for enqueue.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain `[]int` slice with `queue[0]` / `queue = queue[1:]` for dequeue and `append` for enqueue implements FIFO without hiding the iteration shape.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.