# 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.

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