BFS and Bi-directional BFS

Originally published at https://shawnlyu.com on August 18, 2020.

Apart from vanilla BFS introduced in Intro to Graph Algorithms — BFS & DFS, there’s another variant of BFS called bi-directional BFS. Instead of searching from source to target, bi-directional BFS starts with the source and the target at the same time, and search the graph simultaneously. The improvement of time complexities is shown as below, as referring to @ Huahua.

Comparing vanilla BFS and bi-directional BFS.

Let’s take Leetcode 127. Word Ladder as an example.

It asks for the shortest transformation from beginWord to endWord, so BFS is the algorithm that we will apply. Before that, we need to construct the graph, i.e., define nodes and edges. The vanilla BFS is as follows:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        l = len(beginWord)
        edges = collections.defaultdict(list)
        for word in wordList:
            for i in range(l):
                edges[word[:i]+'*'+word[i+1:]].append(word)
         
        q = collections.deque([beginWord])
        visited = set([beginWord])
        ret = 0
        while q:
            ret += 1
            q_len = len(q)
            for _ in range(q_len):
                word = q.popleft()
                if word == endWord:
                    return ret
                for i in range(l):
                    for e in edges[word[:i]+'*'+word[i+1:]]:
                        if e not in visited:
                            q.append(e)
                            visited.add(e)
        return 0

For bi-directional BFS, we would initiate two queues/sets containing the beginWord and the endWord accordingly. One small trick is we would expand the smaller queue/set each time. The code is as follows:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        edges = collections.defaultdict(list)
        l = len(beginWord)
        for word in wordList:
            for i in range(l):
                edges[word[:i]+'*'+word[i+1:]].append(word)
         
        q1 = set([beginWord])
        q2 = set([endWord])
        visited = set([beginWord,endWord])
        steps = 0
        while q1 and q2:
            steps += 1
            if len(q1) > len(q2): # expand the smaller queue first
                q1,q2 = q2,q1
            tmp_len = len(q1)
            q = set([])
            for word in q1:
                for i in range(l):
                    for e in edges[word[:i]+'*'+word[i+1:]]:
                        if e in q2:
                            return steps + 1
                        if e not in visited:
                            q.add(e)
                            visited.add(e)
            q,q1 = q1,q
        return 0

Reference