http://www.perlmonks.org?node_id=644964


in reply to OT(ish) - Best Search Algorithm

Here is a simple approach:

Say your starting vertex is A. First, find the biconnected component containing A. Biconnectivity means that there is no single vertex whose removal would disconnect the graph. But a consequence of this condition is what we're really looking for:

Now that you have A's biconnected component, there are a few cases:

Sorry this is at such a high level with no code ;), but I think you should have no problem, if you were already considering implementing A* search on your own. Check out Graph.pm, it has a method for computing biconnected components, and that will be the main step in this algorithm.

Now, if you are interested in finding the smallest such cycle, I'm not sure exactly how to do it. You might want to find the non-immediate-friend of A who is closest to A, and use him as the basis of your cycle. But I don't think this is guaranteed to give the shortest cycle overall. But it would at least be a reasonable heuristic.

blokhead