Harley Richard

Harley Richard

  • NA
  • 2
  • 1.7k

How to apply BFS algorithm on a Bipartite graph?

Dec 21 2015 2:44 PM
I need to calculate the shortest path between 2 nodes, say actor A and actor B but the problem is my graph is a bipartite graph so actor A and actor B are connected directly through another nodes let's say they can be connected directly through either movie0, or movie1, or movie2. How can I achieve that? like when I apply standard BFS it computes the distance as 2 when the distance should be one, and that's because the movies are considered as nodes,  and same for nodes that's are not connected directly, so how should I modify the BFS in order to let it skip over the movies nodes and consider it as an edge?