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

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.R

adj <- list()
adj[["1"]] <- c(2, 3)
adj[["2"]] <- c(1, 4)
adj[["3"]] <- c(1, 4)
adj[["4"]] <- c(2, 3, 5)
adj[["5"]] <- c(4, 6)
adj[["6"]] <- c(5)
start <- 1
visited <- list()
visited[[as.character(start)]] <- TRUE
queue <- c(start)
order <- integer(0)
head <- 1
while (head <= length(queue)) {
	v <- queue[head]
	head <- head + 1
	order[length(order) + 1] <- v
	neighbours <- adj[[as.character(v)]]
	i <- 1
	while (i <= length(neighbours)) {
		nb <- neighbours[i]
		if (is.null(visited[[as.character(nb)]])) {
			visited[[as.character(nb)]] <- TRUE
			queue[length(queue) + 1] <- nb
		}
		i <- i + 1
	}
}
cat("[", paste(order, collapse = ", "), "]\n", sep = "")

Complexity

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

Implementation notes

R: adj is a named list keyed by as.character(vertex) with integer neighbour vectors. The lesson keeps the queue as a vector plus a head cursor rather than reaching for queue <- queue[-1], so the enqueue / dequeue moves stay explicit and avoid the O(n) reshuffle that negative-index slicing would impose every step.
A visited named list is the explicit "visited" set keyed by as.character(vertex) (is.null(visited[[as.character(nb)]]) checks absence); the queue grows via queue[length(queue) + 1] <- nb to keep the append visible.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain `queue <- c(start)` integer vector with an integer `head` cursor 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.