Graph Algorithms: BFS

3 minute read Published: 2021-08-18

Graph Algorithms: Bredth First Search (BFS)

In preparation for programming interviews, and generally improving my own understanding of algorithms I've decided to put together a series of blog posts about popular algorithm interview questions.

This is an introduction to Graph Algorithms written in Typescript. This is due to the fact that JavaScript is my strongst language, and that there is a deficit of examples in Typescript.

I may do a second pass with in Rust.

From the wikipedia:

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.


Input: A graph G and a starting vertex (node) root of G

Output: Goal State, the verticies that provide a traced shorted path back to the root node

Given G and root
    let Q be a queue
    mark the root as visited
    enqueue root
    while Q is not empty do:
        let v equal a dequeued index value
        if v is the target goal node then
            return v
        for all edges from v (current)
            to u (next node) in adjoining adjacent edges to v
            if u has not been visited then
                set u as visited
                enqueue u


For more concrete example problems, this blog post contains a list of the top 20 problems.

Next in the Series:

  1. Graph Algorithms in Typescript: Breadth-First Search
  2. Graph Algorithms in Rust: Breadth-First Search