A cute little shell script to do BFS traversals.

bfs-search.sh

#!/bin/sh
set -e

################################################################################
# Usage: $SCRIPT_NAME <neighbors-cmd> < roots
#
#   neighbors-cmd: command that takes a node name as argument and outputs its neighbors
#   roots: initial nodes read from stdin (one per line)
################################################################################

if [ $# -eq 0 ]; then
  sed -n '/^##\+$/,/^##\+$/p' "$0" \
    | grep "^#" \
    | sed -E 's/^# ?//;1d;$d' \
    | SCRIPT_NAME=$(basename "$0") envsubst
  exit 2
fi

TEMPDIR=$(mktemp -d)
trap 'rm -rf "$TEMPDIR"' EXIT

QUEUE_FILE="$TEMPDIR/queue"
NEIGHBORS_CMD="$*"

: > "$QUEUE_FILE"

while IFS= read -r root; do
  [ -z "$root" ] && continue
  echo "$root" >> "$QUEUE_FILE"
done

while IFS= read -r node; do
  [ -z "$node" ] && continue

  seen_count=$(grep -c "^${node}$" "$QUEUE_FILE" || true)
  if [ "$seen_count" -gt 1 ]; then
    continue
  fi

  1>&2 echo "visit node: $node"

  sh -c "$NEIGHBORS_CMD" -- "$node" | while IFS= read -r neighbor; do
    [ -z "$neighbor" ] && continue

    if ! grep -q "^${neighbor}$" "$QUEUE_FILE"; then
      echo "$neighbor" >> "$QUEUE_FILE"
    fi
  done

done < "$QUEUE_FILE"

cat "$QUEUE_FILE"

test-bfs-search.sh

#!/usr/bin/env bash
set -euo pipefail
SCRIPT_DIR=$(cd -- "$(dirname -- "${BASH_SOURCE[0]}")" &> /dev/null && pwd)

TEMPDIR=$(mktemp -d)
trap 'rm -rf "$TEMPDIR"' EXIT
cd "$TEMPDIR"

1>&2 printf "using temp dir: %s\n" "$TEMPDIR"

cat > a << EOF
b
c
EOF

cat > b << EOF
c
d
EOF

cat > c << EOF
d
e
EOF

cat > d << EOF
e
f
EOF

cat > e << EOF
e
EOF

cat > f << EOF
EOF

cat > init << EOF
a
EOF

cat > expect << EOF
a
b
c
d
e
f
EOF

"$SCRIPT_DIR/bfs-search.sh" 'cat $1' < init > actual

if diff -u expect actual; then
  1>&2 printf "\n*** TEST PASSED ***\n"
else
  1>&2 printf "\n*** TEST FAILED ***\n"
  exit 1
fi