Bi-Directional BFS

Eg1.

determine if two persons are friends. determine if two persons are level 2 friends.

Uni-Directional BFS.

from one person A , do 2 steps bfs, check if person B exists.

Time: O(k ^ n) branching factor : k , level : n

Bi-Directional BFS from A, do level n / 2 BFS.

from B, do level n / 2 BFS.

Time : O(n ^ k / 2).

Eg2.

find common friends

Method 1 : uni - directional for 3 levels.

Time : O(k ^ 3) Space: O(k ^ 3)

Method 2 : bi-directional

Method 3: DFS with restricted level.

Time : O(k ^ 3) Space : O(1)

Method 4: restrict space O(1)

1. if level 2 :
   1. find all A level 1 friends
   2. find all B level 1 friends.
   3. see if any intersection, two sorted array.

Now considering level 3, (2 + 1) ?

 for X in all A's level 1 friends {
   find all x's level 1 friends : 
       see if there is any intersection with B's level 1 friends.
 }