Breadth First Search(BFS)

In this article I want to talk about Breadth First Search or BFS in short. When to use it and how to use it

First of all, when to use BFS?

• Connected components
  • Find all the connected nodes from a given node in a graph

• Level order traversal
  • Traverse a graph
  • Shortest path of a simple graph(Edges are of the same weight/length), sometimes in the format of finding the minimum value of something

• Topological sorting
  • Find any topological sort of a given graph
  • Find if a graph has any topological sort
  • Find the minimum topological sort
  • Find if a graph has only one topological sort

BFS vs DFS

Some of the graph related problems can be solved by both BFS and DFS, I would recommend using BFS if possible for the following reason.

• Easier to reason
• Easier to write
• DFS sometimes has stack overflow issues

Below is a general template for writing BFS in python, there could be some changes depending on the problem you are trying to solve

queue = collectios.deque([first_node])
visited = {first_node: 0}

while queue:
    node = queue.popleft()
    # find all the neighbors of the current node we are visiting
    # check each of them to see if they are already visited previously
    # if not add them to the queue and visited AT THE SAME TIME
    for neighbor in node.get_neighbors():
        if neighbor in visited:
            continue
        visited[neighbor] = visited[neighbor] + 1
        queue.append(neighbor)

Now let’s take a look at some problems

First is a simple and straight forward one, we can use this to just practice the BFS template.

https://leetcode-solution.com/leetcode-133-clone-graph-2

Let’s have more fun a take a look at a more complicated problem

BFS on matrix

The tricky thing on matrix is to find a good way of the next nodes(neighbor) to visit while making sure the neighbors are valid(within the matrix and not visited etc.). We can use something like below to iterate all the possible neighbors:

# if we can only go up, down, left and right
deltas = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for delta in deltas:
    x_delta, y_delta = delta
    if (x + x_delta) in range(len(grid)) and (y + y_delta) in range(len(grid[0])) and grid[x + x_delta][y + y_delta] meet requirement and grid[x + x_delta][y + y_delta] not in visited:
        # do something here

Topological sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u-v, vertex u comes before v in the ordering.

In another word, topological sort does NOT have rings or loops in the graph.

Before we dive deep into how to solve this kind of problems, we need to first know in-degree of a node.

In a directed graph, meaning edges between nodes have direction, node A can have an edge pointing to node B and B can also have an edge pointing to A.

In-degree of a node equals to the number of edges that points to the node.

Now let’s look at how we should solve topological sort problems:

1. Calculate the in degree for each node
2. Find all the nodes that have a in degree of 0 and put them in a queue, the sequence depends on individual problems.
3. Pop a node out of the queue, remove all the out going edges from this node, and update all the in degree values of the affected nodes.
4. If we see nodes whose in degree becomes 0 after the in degree, put them in the queue

Something to note:

• A graph can have multiple topological sort, only 1 topological sort, OR no topological sort at all.

That’s why there are a kinds of topological sorting problems aim to find:

• Any topological sort
• If there is at all any topological sort
• If there is only 1 topological sort
• The smallest topological sort

Let’s look at them one by one

First, return any one valid topological sort of graph

One thing to note from the above problem is that, we do NOT have a variable called visited to record visited nodes while BFS. Why?

First of all, let’s ask why we needed it for other BFS’ in the first place? Think about the timing when we put the node into visited, for general BFS’, when we see the node for the very first time, we added it to the queue so it can be process later, BUT it could also be seen at a later time from other parent node. That’s why we want to mark it as visited so it won’t be visited multiple times.

But for topological sort, things are a little bit different. Only when the in degree becomes 0 we put the node in the queue for later processing. This timing means, the node is seen for the very last time because there’s no other edges pointing to it anymore. That’s why we don’t have to worry about visiting it again.

Here’s another classical topological sorting problem: