StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The 6 degrees is nice because it gives you a limitation. I realize the 6 can change, but I think the approach here still applies. Anywhere I say "6", just substitute in "# of degrees".</p> <p>If you wanted, you could use Breadth First Search (BFS). If I understand correctly, you're given a starting point (an actor/actress) and you need to find all paths to an endpoint (Kevin Bacon) that are less than or equal to 6 edges away. You can break that down into subproblems by saying first find all the connections that are 1 edge away, then all the paths 2 edges away, ... , and finally find all the paths six edges away. This is exactly how a BFS would work...first examine all the nodes one edge away, then two, etc.</p> <p>Alternately, you could also use a modified Depth First Search (DFS) by doing a normal DFS and follow each path as far as you can, but keep a counter and stop it from going more than 6 edges deep down any particular path.</p> <p>I would think your solution will likely be much better than the normal O(V + E) simply because you're likely not visiting all Vertices or travelling along all Edges (assuming our graph is the relationships between a large numbers of actors), but rather you're constrained to a subgraph of the overall graph. You start off your search algorithm acting like you you're going to visit all vertices/edges, but regardless of whether you use BFS or DFS, you'll be stopping at 6 edges out from your starting vertex rather than looking through the entire graph.</p> <p>Consider that something like DFS can be represented as O(V+E), but it can also be represented as O(b^d) where b is the branching factor and d is the graph depth (see <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">Wikipedia_DFS</a> for more info ). So given how many actors there are out there, what will b be? Given the constraints you know about the problem (6 degrees and what not), what will d be?</p> <p>I think I've probably said enough. Hopefully that kickstarts it for you. I should add the caveat that I don't actually know the answer for sure, this is just how the problem strikes me ;)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload