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.

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
```