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.
Procedure
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
do:
if u has not been visited then
set u as visited
enqueue u
Applications
- Copying garbage collection, Cheney’s algorithm.
- Finding the shortest path between two nodes
uandv, with a path length measured by the total number of edges - Testing a graph for bipartiteness
- Minimum Spanning Tree for an unweighted graph.
- Web Crawler
- Finding nodes in any connected component graph
- Ford-Fulkerson method for computing the maximum flow in a flow network (aka Edmonds-Karp)
- Serialization/Deserialization of a binary tree
For more concrete example problems, this blog post contains a list of the top 20 problems.
Next in the Series: