[yetanotherphd]

It is the final inner loop that is problematic.

Instead, your graph should comprise movies and actors as vertices (edge = actor was in a given movie), and to get the Bacon number you just halve the distance in this graph.

So you code would look like

    for bucket in hashtable:
        add node for bucket
        for actor in bucket:
            if actor not in graph, add a node for actor
            add an edge between actor and bucket
            add an edge between bucket and actor

If each movie contains exactly K actors, and there are N movies, then your graph has O(NK^2) edges while mine has O(NK) edges.

[mcintyre1994]

Ah that's awesome, really smart optimisation, thanks. I hadn't really thought of the possibility of having the two different features in the same graph but that's definitely better!