StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If the graph has cycles then 'ancestor' is loosely defined. Perhaps you mean the ancestor on the tree output of a DFS or BFS? Or perhaps by 'ancestor' you mean the node in the digraph that minimizes the number of hops from <code>E</code> and <code>B</code>? </p> <p>If you're not worried about complexity, then you could compute an A* (or Dijkstra's shortest path) from every node to both <code>E</code> and <code>B</code>. For the nodes that can reach both <code>E</code> and <code>B</code>, you can find the node that minimizes <code>PathLengthToE + PathLengthToB</code>.</p> <p>EDIT: Now that you've clarified a few things, I think I understand what you're looking for.</p> <p>If you can only go "up" the tree, then I suggest you perform a BFS from <code>E</code> and also a BFS from <code>B</code>. Every node in your graph will have two variables associated with it: hops from <code>B</code> and hops from <code>E</code>. Let both <code>B</code> and <code>E</code> have copies of the list of graph nodes. <code>B</code>'s list is sorted by hops from <code>B</code> while <code>E</code>'s list is sorted by hops from <code>E</code>. </p> <p>For each element in <code>B</code>'s list, attempt to find it in <code>E</code>'s list. Place matches in a third list, sorted by hops from <code>B</code> + hops from <code>E</code>. After you've exhausted <code>B</code>'s list, your third sorted list should contain the LCA at its head. This allows for one solution, multiple solutions(arbitrarily chosen among by their BFS ordering for <code>B</code>), or no solution.</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