Implementing Breadth-First Search in TypeScript: A Step-by-Step Guide

Breadth-first search (BFS) is a cornerstone algorithm in computer science, used for systematically exploring nodes and edges of a graph. It's akin to casting a stone into a pond and watching the ripples expand uniformly around the point of impact. In the realm of data structures, BFS starts at a node and explores all of its neighbors at the current depth before moving on to nodes at the next level.

What is Breadth-First Search?

BFS is an algorithm that operates on graphs, which consist of nodes (also called vertices) connected by edges. The purpose of BFS is to traverse the graph in the shortest path manner, meaning that it visits nodes in the order of their distance from the starting node, where the distance is the minimum number of edges that must be traversed to reach that node.

The algorithm uses a queue data structure to track the order in which nodes should be visited. As BFS progresses, it "discovers" new nodes, marking them to avoid revisiting and adding them to the queue.

How BFS Works

Here's a step-by-step breakdown of the BFS algorithm:

1. Initialization: Start by placing the root node (or any starting node in a graph) into the queue.
2. Exploration: Remove the next node from the queue and mark it as visited.
3. Neighbor Discovery: Add all unvisited neighbors of this node to the queue.
4. Repeat: Continue this process until the queue is empty.

Each time a node is visited, it's an opportunity to perform some operation, such as checking a condition or processing the node's value.

Implementing BFS in TypeScript

To implement BFS in TypeScript, we'll define a Node interface and a bfs function. The Node interface represents each node in the graph, and the bfs function encapsulates the BFS algorithm.

interface Node<T> {
  value: T
  next?: Node<T>
}

class Queue<T> {
  public length: number
  private head?: Node<T>
  private tail?: Node<T>

  constructor() {
    this.tail = this.head = undefined
    this.length = 0
  }

  enqueue(item: T): void {
    const node: Node<T> = { value: item }

    this.length++

    if (!this.tail) {
      this.head = this.tail = node
      return
    }

    this.tail.next = node
    this.tail = node
  }

  deque(): T | undefined {
    if (!this.head) {
      return undefined
    }

    this.length--

    const currentHead = this.head

    if (this.length === 0) {
      this.head = this.tail = undefined
      return currentHead.value
    }

    this.head = this.head.next
    return currentHead.value
  }

  peek(): T | undefined {
    return this.head?.value
  }
}

interface BinaryNode<T> {
  value: T
  left: BinaryNode<T> | null
  right: BinaryNode<T> | null
}

function bfs(head: BinaryNode<number>, needle: number): boolean {
  const queue = new Queue<BinaryNode<number>>()

  queue.enqueue(head)

  while (queue.length) {
    const curr = queue.deque()

    if (curr?.value === needle)
      return true

    if (curr?.left) {
      queue.enqueue(curr.left)
    }

    if (curr?.right) {
      queue.enqueue(curr.right)
    }
  }

  return false
}

const tree: BinaryNode<number> = {
  value: 20,
  right: {
    value: 50,
    right: {
      value: 100,
      right: null,
      left: null,
    },
    left: {
      value: 30,
      right: {
        value: 45,
        right: null,
        left: null,
      },
      left: {
        value: 29,
        right: null,
        left: null,
      }
    },
  },
  left: {
    value: 10,
    right: {
      value: 15,
      right: null,
      left: null,
    },
    left: {
      value: 5,
      right: {
        value: 7,
        right: null,
        left: null,
      },
      left: null,
    }
  }
}

// Example usage:
bfs(tree, 45)

Conclusion

This guide provides a clear path to implementing BFS in TypeScript, from understanding the algorithm to writing and running the code.

Happy coding!