Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from one node to all other nodes in a weighted graph.

Say we had the following graph, which represents the travel cost between different cities in the southeast US:

Dijkstra's algorithm lets us find the cheapest route from one city to all other cities. So for Memphis:

Backtracking

Our table above stores the cost of getting to any city from Memphis, but it doesn't store the actual path. To find it, we'd start at that city and use the Via column to backtrack through the graph until we get to Memphis. This is the same way you recover paths after doing a breadth-first search ↴

Breadth-First Search is an algorithm that systematically explores a graph level by level. Starting from a source point, BFS visits all its immediate neighbors first, then their neighbors, and so on. This methodical approach makes it incredibly useful for finding shortest paths in unweighted graphs, exploring tree-like structures, and solving a variety of problems that come up frequently in coding interviews.

BFS is a cornerstone algorithm. It's often favored in interviews because it strikes a balance: it's conceptually straightforward to understand and implement, yet adaptable to a wide range of challenging questions.

In this article, we’ll cover core concepts of BFS, look at some implementations with time / space complexity analysis, and explore a few different problems where BFS shines. Let's dive in!

Understanding the Core Concepts of BFS

What is Breadth-First Search?

Breadth-First Search (BFS) explores a graph or tree level by level. Imagine dropping a pebble into still water: the ripples spread outwards in circles. BFS mimics this, starting at a source node and systematically visiting all nodes at the current level before moving to the next level. This level-by-level approach ensures you explore the graph in layers of "hops" from the starting point.

Starting from one point in the graph,

we look at all the nodes one level away,

then all the nodes two levels away,

then all the nodes three levels away,

and so on - until we’ve seen every node.

Key Data Structure: The Queue

The key behind BFS's level-by-level exploration is a queue. A queue is a First-In, First-Out (FIFO) data structure: items are added to the back and removed from the front.

In BFS, a queue stores the nodes we need to explore. When we visit a node, we add its unvisited neighbors to the back of the queue. Then, we process the next node at the front of the queue. This FIFO behavior ensures that we explore all nodes at the current "level" before moving to the next level.

The Visited Set

To prevent infinite loops and redundant processing in graphs (especially those with cycles), we need to keep track of visited nodes. This is where a visited set is essential.

Before adding a neighbor to the queue, we check if it's already in the visited set. If it is, we skip it. Otherwise, we add it to the queue and mark it as visited by adding it to the visited set. Using an efficient set data structure, these checks and inserts can be done in $O(1)$ time on average.

Path Reconstruction: The Predecessor Dictionary

In many BFS problems, especially shortest path problems, you'll need to reconstruct the path from the starting node to the target node once you find it. To do this, we use a predecessor dictionary (or parent dictionary).

As we explore the graph with BFS, whenever we enqueue a neighbor node, we record in the predecessor dictionary that we reached this neighbor from the current node. This dictionary stores each node and its immediate predecessor in the BFS traversal.

Once BFS finds the target node, we can easily reconstruct the path by starting at the target node and using the predecessor dictionary to trace back to its predecessor, then to its predecessor, and so on, until we reach the starting node. This backtracking process gives us the shortest path in reverse order, which we can then reverse to get the correct path.

Path reconstruction takes time proportional to the length of the shortest path. In the worst case, every node in the graph could be in the path, so reconstructing takes $O(V)$ overall.

The BFS Algorithm: Step-by-Step

Let's break down the BFS algorithm into clear steps:

1. Initialization:
   • Create an empty queue, queue.
   • Create an empty predecessor dictionary, predecessors
   • Create an empty set, visited
   • Enqueue the starting node into the queue.
   • Add the starting node to visited and predecessors.
2. Iteration (while the queue is not empty):
   • Dequeue a node from the front of the queue. Let's call this current_node.
   • Process current_node. This might involve:
     • Checking if it's the target node you're searching for.
     • Performing some operation based on the node's value.
     • Simply noting that you've visited it.
   • Explore Neighbors: Get all valid, unvisited neighbors of current_node.
   • For each unvisited neighbor:
     • Enqueue the neighbor into the queue.
     • Add it to visited.
     • In predecessors, record that we got to this neighbor via current_node

3. Termination: The algorithm terminates when we reach our target node or the queue becomes empty.

   At this point, you often will reconstruct the path from start_node to end_node using the predecessors dictionary.

  from collections import deque


def reconstruct_path(predecessors, start_node, end_node):
    reversed_shortest_path = []

    # Start from the end of the path and work backwards
    current_node = end_node
    while current_node:
        reversed_shortest_path.append(current_node)
        current_node = predecessors[current_node]

    # Reverse our path to get the right order
    reversed_shortest_path.reverse()  # flip it around, in place
    return reversed_shortest_path  # no longer reversed


def bfs_get_path(graph, start_node, end_node):
    if start_node not in graph:
        raise Exception('Start node not in graph')
    if end_node not in graph:
        raise Exception('End node not in graph')

    queue = deque()
    queue.append(start_node)

    visited = set([start_node])

    predecessors = {start_node: None}

    while len(queue) > 0:
        current_node = queue.popleft()

        # Stop when we reach the end node
        if current_node == end_node:
            return reconstruct_path(predecessors, start_node, end_node)

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
                predecessors[neighbor] = current_node

    # If we get here, then we never found the end node
    # so there's NO path from start_node to end_node
    return None

CC#C++JavaJavaScriptObjective-CPHPPython 2.7Python 3.6RubySwift

Analyzing Time and Space Complexity of BFS

Once you’ve coded up an algorithm, interviewers are going to ask you to analyze its time and space complexity.

Time Complexity: $O(V+E)$

$V$ is the number of vertices (nodes) and $E$ is the number of edges in the graph. We visit each vertex at most once (due to the visited set). For each vertex, we iterate through its neighbors. In total, across all vertices, we examine each edge at most twice (once for the node on each end). Putting it all together, we’ve got $O(V+E)$ time complexity.

Space Complexity: $O(V)$

$V$ is the number of vertices. Our three data structures are the node queue, the visited set, and the backtracking dictionary. Because each node gets added to the queue exactly once, the queue won’t grow beyond $O(V)$. Our visited set also grows to hold all the nodes, $O(V)$ size. Finally, our backtracking dictionary has one entry per node, so it’s $O(V)$, too. Putting these together, we’re still $O(V)$ space.

Applications of BFS: Where is BFS Useful?

Because of its versatility, BFS shows up in a lot of places. Look for these problem structures that suggest BFS is the appropriate algorithm:

• Problems where you’re exploring a set of states and have to find the shortest sequence from one state to another.
• Problems involving grid-based structures (mazes, grids, etc.) where each step has the same cost.
• Problems where you need to look at connected items (friends in a social network, links within a website, railroads between cities, etc.).

When approaching a problem that might be solved with BFS, consider these steps:

• Identify BFS Applicability: Does the problem involve finding the shortest path in an unweighted graph, exploring levels or layers, or searching connected components? If so, BFS might be a good fit.
• Define the Graph/States: What are the "nodes" in your problem? How are they connected (what are the "edges" or transitions)? This could be explicit graph nodes, grid cells, words in a word ladder, etc.
• Define Start and End: What is the starting node(s)? Is there a specific target node or condition you are searching for?
• Define Neighbors: How do you find the valid neighbors of a node? Consider constraints (walls in a maze, valid word transformations, etc.).
• Handle Boundary Conditions: Consider edge cases like empty inputs, disconnected components, and whether BFS is feasible given the input size.

Sample BFS Interview Questions

Here are some common interview problems where a BFS-style algorithm could work:

Binary Tree Level Order Traversal

Problem Description: Given a binary tree, return its node values in level order traversal. That is, nodes at each level are visited from left to right, level by level.

Applying BFS:

• Our starting node is the root of the binary tree. We don't have a specific ending node; we'll continue until the queue is empty.
• Each node's neighbors are their left and right children (if they have them).
• We can check for an empty tree (comparing the root node to None). And, assuming the tree is a reasonable size, BFS should be feasible.

Shortest Path Through a Maze

Problem Description: Given an ASCII maze where each step has the same cost, find the shortest path from the top left to the bottom right.

  .#######             @####### 
..#.#..#             @@#.#..#
#.....##             #@@@@@##
###.#..#      ==>    ###.#@.#
#...#.##             #...#@##
#.###.#.             #.###@#.
#.....##             #....@##
#####...             #####@@@

CC#C++JavaJavaScriptObjective-CPHPPython 2.7Python 3.6RubySwift

Applying BFS:

• Our starting node is the top left corner. Our ending node is the bottom right corner.
• Each node's neighbors are the points above, below, left, and right - as long as they're not walls. We need to be careful of boundary conditions, like nodes on the edges of the grid.
• We can check for edge cases like the start or end position being a wall or mazes where there's no path from the start to the finish.
• If the maze is very large, it's possible BFS will be too slow or require too much memory. Ask your interviewer how large the maze is expected to be!

Number of Islands

Problem Description: Given a 2D grid indicating land and water, count the number of islands.

Applying BFS:

• Start with a set of visited nodes, initially empty.
• Iterate through the entire grid. When we reach a point that's an island:
  • If the point is already visited, do nothing.
  • Otherwise, increase our count by 1 and do BFS from that point outwards. Each BFS visits all the points on a single island. A point's neighbors are adjacent points that are also land.
• Return the total number of islands seen.

Word Ladder

Problem Description: Given a start word and a target word, find the fewest steps required to transform one into the other, changing only one letter at a time.

As an example, to transform head into tail, we could generate this sequence:

• head
• heal
• teal
• tell
• tall
• tail

Applying BFS:

• Our starting node is the start word. Our ending node is the target word.
• Each node's neighbors are words that differ by one letter. As an example, some neighboring words for node would be:
  • code
  • mode
  • nods
  • note
  • rode
  • ...
• We should check for edge cases like:
  • The start or target not being valid words
  • The start and target being different lengths
  • No possible word ladder

Conclusion: BFS - A Powerful Tool in Your Interview Toolkit

Breadth-First Search is an indispensable algorithm in your coding interview toolkit. Its systematic level-by-level exploration makes it a powerful and efficient approach for a wide range of problems. By mastering the core concepts – the queue, visited set, predecessor dictionary – and practicing its implementation, you'll be well-prepared to confidently tackle BFS-related interview questions.

Remember to:

• Practice recognizing problems where BFS could be used.
• Clearly articulate your BFS approach during interviews, highlighting how you are defining nodes, neighbors, and handling visited states.
• Understand and be able to explain the time and space complexity for different BFS variants.

With practice and a solid understanding of BFS, you'll be ready to impress in your next coding interview! Good luck!

Time and Space Complexity

What's the time complexity?

• Our initialization involves a constant amount of work per node, plus inserting $O(N)$ nodes into priority_queue will take $O(N*lg(N))$ time. (Priority queues are built on heaps, which have $O(\lg{n})$ insertions ↴

  Quick reference

  	Worst Case
  get min	$O(1)$
  remove min	$O(lg(n))$
  insert	$O(lg(n))$
  heapify	$O(n)$
  space	$O(n)$

  A binary heap is a binary tree where the smallest value is always at the top.

  

  A min-heap has the smallest value at the top. A max-heap has the largest value at the top. We'll describe min-heaps here, but the implementation for max-heaps is nearly identical.

  Strengths:

  • Quickly access the smallest item. Binary heaps allow you to grab the smallest item (the root) in $O(1)$ time, while keeping other operations relatively cheap ($O(lg(n))$ time).

  • Space efficient. Binary heaps are usually implemented with lists, saving the overhead cost of storing pointers to child nodes.

  Weaknesses

  • Limited interface. Binary heaps only provide easy access to the smallest item. Finding other items in the heap takes $O(n)$ time, since we have to iterate through all the nodes.

  Uses

  • Priority queues are often implemented using heaps. Items are enqueued by adding them to the heap, and the highest-priority item can quickly be grabbed from the top.
  • One way to efficiently sort a list of items is to make a heap out of them and then remove items one at a time—in sorted order.

  Implementation

  Heaps are implemented as complete binary trees.

  In a complete binary tree:

  • each level is filled up before another level is added, and
  • the bottom tier is filled in from left to right.

  As we'll see, this allows us to efficiently store our heap as a list.

  In a heap, every node is smaller than its children.

  

  

  

  

  Inserting a new item

  

  1. Add the item to the bottom of the tree.

     

  2. Compare the item with its parent. If the new item is smaller, swap the two.

     

  3. Continue comparing and swapping, allowing the new item to "bubble up" until the it's larger than its parent.

     

  Because our heap is built on a complete binary tree, we know it's also balanced. Which means the height of the tree is $\lg{n}$. So we'll do at most $\lg{n}$ of these swaps, giving us a total time cost of $O(\lg{n})$.

  Removing the smallest item

  Easy—it's right there at the top:

  

  Now, we have to shuffle some things around to make this a valid heap again.

  1. Take the bottom level's right-most item and move it to the top, to fill in the hole.

     

  2. Compare the item with its children.

     

     If it's larger than either child, swap the item with the smaller of the two children.

     

  3. Continue comparing and swapping, allowing the item to "bubble down" until it's smaller than its children.

     

  As with inserting (above), we'll do at most $\lg{n}$ of these swaps, giving us a total time cost of $O(\lg{n})$.

  Heaps are built on lists

  Complete trees and heaps are often stored as lists, one node after the other, like this:

  

  Using a list to store a complete binary tree is very efficient. Since there are no gaps in complete trees, there are no unused slots in the list. And, inserting a new item in the bottom right part of the tree just means appending to the list.

  But how do we traverse the tree when it's a list? How do we go from a node to its left and right children? With a bit of clever indexing! See if you can come up with the formulas for a node's left child, right child, and parent. Then, check your answer. ↴

  Looking at a few nodes, it's easy enough to derive the general formulas.

  • Left Child: Index 0's left child is at index 1. Index 1's left child is at index 3. And index 2's left child is a 5. In general, a node at index $i$'s left child will be at index $2*i + 1$.

  • Right Child: This node always comes right after the left child. In general, a node at index $i$'s right child will be at index $2*i + 2$.

  • Parent: The nodes at indices 1 and 2 have their parent at index 0. The nodes at indices 3 and 4 have their parent at index 1. And the nodes at indices 5 and 6 have their parent at index 2. In general, a node at index $i$ has its parent at index $(i-1)/2$.

  Don't bother memorizing these ... just work through a few examples and you'll be able to come up with them on the fly. Just remember the main idea is that you're multiplying or dividing by 2. This makes sense, because the number of nodes on each level of a complete binary tree doubles as you move down level by level.

  Heapify: Transform a List Into a Heap

  Say we want to make a heap out of the items in a list.

  We could create a new empty heap and add in the items from the list one at a time. If the list has $n$ elements, then this takes $O(n*\lg(n))$.

  It turns out that there's a more efficient way to transform a list into a heap.

  We'll take our input list and treat it like the nodes in a complete binary tree, just like we did above:

  

  To transform the tree into a valid heap, we'll compare each node to its children and move nodes around so that parent nodes are always smaller than their children.

  This causes larger nodes to move lower in the tree, "bubbling down" to allow smaller values to reach the top.

  Look familiar? This is the same bubbling down we were doing to remove items from the heap!

  We'll work from the leaf-nodes at the bottom upwards. To start off, let's look at the leaves.

  The leaf nodes don't have any children, so they don't need to move down at all. Great.

  

  Let's look at the nodes in the next level:

  

  We'll start with the left node (3) and its children:

  

  Since 3 is smaller than both 7 and 9, it's already in the right spot.

  But, looking at the right node (2) and its children, since 1 is smaller than 2, we'll swap them.

  

  Notice how we've got two small valid min-heaps. We're getting close!

  

  Moving up, we've got an 8 at the root.

  

  Since 8 is larger than 1, 8 bubbles down, swapping places with the smaller child: 1.

  

  Then, we need to compare 8 to its two children—2 and 4. Since 8 is bigger than both of them, we swap with the smaller child, which is 2.

  

  At this point, we've transformed the input tree into a valid min heap. Nice!

  Heapify complexity

  What's the time complexity of heapify'ing a list?

  It's tempting to say it's $O(n*\lg(n))$. After all, we have to examine all $n$ nodes, and a node might bubble down $O(\lg(n))$ levels.

  That's an overestimate of the amount of work though. All of the leaf nodes at the bottom of the tree won't have to move down at all. And the parents of those nodes will only move down once. In fact, there's only one node that might move down $O(\lg(n))$ times: the root node.

  Since binary heaps are based on complete binary trees, there will be $n/2$ nodes in the bottom level, $n/4$ nodes in the second-to-last level, etc. Each time we go up a level we cut the number of nodes in half.

  

  So, we'll move $n/2$ nodes on the bottom level 0 times. The $n/4$ nodes one level up move at most 1 time. Then, $n/8$ nodes move at most 2 times. And so on, until we get to the root node, which moves $\lg(n)$ times.

  Adding this all up, we've got:

  $0 * \frac{n}{2} + 1 * \frac{n}{4} + 2 * \frac{n}{8} + 3 * \frac{n}{16} + \ldots$

  Alternatively, this can be expressed as a summation:

  $n * \sum \frac{i}{2^{i + 1}}$

  The sum is a geometric series that converges to 1/2. (Take our word for it—the arithmetic to prove this gets a bit hairy.) Then, multiplying by $n$, we have $n/2$. That's $O(n)$.

  ) That's $O(N*lg(N))$ time overall for all the initialization work.
• We'll go through the loop $O(N)$ times, and each time we call remove_min(), taking $O(lg(N))$ time (assuming a heap-based priority queue). Over the entire algorithm, that's $O(N*lg(N))$ time.
• We'll update cost_to_get_to once per edge, or $O(M)$ times. Each priority queue update costs $O(lg(N))$ time. That's $O(M*lg(N))$ time overall.

Putting all the steps together, the time complexity for Dijkstra's algorithm is $O(N*lg(N) + M*lg(N))$. Sometimes, this complexity is written $O((N + M)lg(n))$.

What about space complexity? All our data structures hold a constant amount of data for each node in the graph. That's $O(N)$ space in total.