Week 2: BFS and Topological Sorting

Breadth-first Search (BFS) appears in interviews A LOT. It is very simple and versatile, so it is worthy to spend some time and tackle it down. One cool thing about BFS is that we could solve most BFS problems using two templates, which I will show you later. If you study really hard, it is possible to master BFS in just one single day (expect 8 hours of effort). BFS utilizes a queue to keep track on elements that are waiting to be searched. In Python, we use collections.deque() to realize this functionality. Also, we need a set to record the nodes that had been visited already. If we don’t do this, the algorithm might falls into infinite loops.

When do we use BFS? There are three major scenarios:

  1. Graph Traversal (level order traversal, connected components, topological sorting)
  2. Finding shortest path in simple graph (every edge has equal weight)
  3. Iteration solution for all possible results (will appear in later posts)

There are two types of BFS, either without-level-order or with-level-order. We will begin our discussion using the simpler case, which is the without-level-order case.

BFS without Level Order:

If we are not asked to record level order, just simply visit the neighbors of head, and then the neighbors of neighbors, and so on, one by one. If we are asked to record level order, we need insert an additional for loop inside the while loop to traverse all nodes in a certain level, and then move on to the next level, level by level. That is the only difference, which is a simple modification of the code. Let’s take a look at the simpler case:

"""
BFS without level order
"""
from collections import deque

seen = set()
queue = deque()

seen.add(start)
queue.append(start)
while len(queue):
    head = queue.popleft()
    for neighbor in head.neighbors:
        if neighbor not in seen:
            seen.add(neighbor)
            queue.append(neighbor)

One thing to note is that, for a graph BFS, seen and queue always come in pairs. We initialize them together, and each time one of them needs to be updated, the other would need to be updated too. You may use some silly phrase like “have you seen queue today?” to help memorization. If we use BFS on a binary tree, then we don’t need to use seen, because trees don’t contain any cycle, so there won’t be any potential danger of infinite loop. Also, note that in a binary tree, the neighbors of a node are its left child and right child (if there is any), so the for loop will be replaced by two if statement.

Sample Problems:

LeetCode #133. Clone Graph (medium)

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

  1. The number of nodes will be between 1 and 100.
  2. The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
  3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
  4. You must return the copy of the given node as a reference to the cloned graph.

Solution:

BFS with level order:

As mentioned, now we need to insert an additional for loop into the code. Here is how it works:

"""
BFS with level order
"""
from collections import deque

seen = set()
queue = deque()

seen.add(start)
queue.append(start)
while len(queue):
    size = len(queue)
    for _ in range(size):
        head = queue.popleft()
        for neighbor in head.neighbors:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)

Sample Problems:

LeetCode #102. Binary Tree Level Order Traversal (medium)

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        queue = collections.deque([root])
        level_order = []
        
        while queue:
            level = []
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            level_order.append(level)
            
        return level_order

Next, we are going to introduce topological sorting. Topological sorting is a hidden gem that many people forget to prepare before coding interviews. This topic only takes a few pages in standard algorithm textbooks, but it’s a rather important topic that most tech companies want you to know.

Time Complexity:

In short, the time complexity of BFS is O(|V|+|E|), where |V| is the number of nodes and |E| is the number of edges. Why? Note that the while loop is executed at most once for each vertex, since we use the set seen to avoid any revisiting on node. This gives O(|V|). The for loop inside the while loop is executed at most once for each edge, since each node is popped out of the queue at most once, and we visit its neighbors through edges if and only if the node is popped. This gives O(|E|). Combining the two loops gives us O(|V|+|E|).

Topological Sorting:

Topological sorting works for directed acyclic graphs (DAG) only, and the goal is to find a topological order of the given graph. The graph may have more than one topological order, and we only need to find one of them. By topological order, we mean

Algorithm:

  1. Record the in-degrees of all nodes, and initialize an empty list “topological_order”.
  2. Append all nodes with in-degree 0 to the queue.
  3. Feed the nodes in start_nodes to topological_order one by one. Each time we release a node,
    we visit all its neighbors, and subtract 1 from the in-degree of each neighbor.
  4. If the indegree of any node becomes 0 after this subtraction, we append this node to the queue.
  5. If the queue becomes empty, stop the while loop and return topological_order.

Template:

"""
Definition for a Directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""

class Solution:
    """
    @param graph: A list of Directed graph node
    @return: A list of integer
    """
    def topSort(self, graph):
        node_to_indegree = self.get_indegree(graph)

        # BFS
        topological_order = []
        start_nodes = [n for n in graph if node_to_indegree[n] == 0]
        queue = collections.deque(start_nodes)

        while queue:
            node = queue.popleft()
            topological_order.append(node)
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] -= 1
                if node_to_indegree[neighbor] == 0:
                    queue.append(neighbor)
                
        return topological_order
    
    # Record indegree of all nodes
    def get_indegree(self, graph):
        node_to_indegree = {x: 0 for x in graph}

        for node in graph:
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] += 1
                
        return node_to_indegree

Follow-up: Bidirectional BFS

LeetCode Time!

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s