Graph - Bash DSA

Visit every vertex of a small undirected graph in BFS order from a starting vertex. Uses an explicit FIFO queue and a visited hash to avoid re-visiting.

Algorithm

Canonical input is the graph 1 -- 2 -- 4 -- 5 -- 6, 1 -- 3 -- 4 with start=1. The BFS order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
declare -A adj
adj[1]="2 3"
adj[2]="1 4"
adj[3]="1 4"
adj[4]="2 3 5"
adj[5]="4 6"
adj[6]="5"
start=1
declare -A visited
visited[$start]=1
queue=("$start")
order=()
head=0
while [ "$head" -lt "${#queue[@]}" ]; do
	v=${queue[head]}
	head=$((head + 1))
	order+=("$v")
	read -ra neighbours <<< "${adj[$v]}"
	i=0
	while [ "$i" -lt "${#neighbours[@]}" ]; do
		nb=${neighbours[i]}
		if [ -z "${visited[$nb]+_}" ]; then
			visited[$nb]=1
			queue+=("$nb")
		fi
		i=$((i + 1))
	done
done
printf '['
sep=''
for v in "${order[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

Complexity

Time: O(V + E)
Space: O(V) for the queue and visited hash

Implementation notes

Bash: declare -A adj stores adjacency lists as space-separated strings keyed by vertex; read -ra neighbours <<< "${adj[$v]}" splits each list into a positional array per pop without spawning a subshell.
The queue is an indexed array with a moving head cursor instead of unset-based dequeue, mirroring the stack lesson's cursor pattern.
visited is a separate declare -A hash so the +_ parameter expansion can test for set/unset without confusing zero-valued keys.
The replay reports each pop frame with the enqueued frontier so the viewer follows the BFS layer order.

queue and visited set Initialise `queue=(start)` and `visited[start]=1`. Pop the front, record it, then enqueue every unvisited neighbour while marking it visited.

layer order Because the queue is FIFO and a node is marked visited at enqueue time, BFS visits nodes in layer order from the start.