How can I find the shortest cycle in an undirected bipartite graph using BFS ?

Question

How can I find the shortest cycle in a simple (not directed ) bipartite graph using Breadth First Search ?

Answer 1

In a bipartite graph, the shortest possible circle is at least 4 edges long. Since you are using breadth first search you will find the optimum quite fast as long as you increase your travel distance accordingly. All possible 4 edges long path, all possible 5 edges long paths, and so on. The moment you find a path that is a circle, you are done, it is the shortest possible or at least tied for that prize.

Keep all paths explored as to only increase these by 1 more edge each cycle of the search. And use BFS to make sure you have explored all paths.