1
$\begingroup$

Firstly, I am trying to understand the meaning of LCA in DAG. I read a definition somewhere-"Define the height of a vertex v in a DAG to be the length of the longest path from root to v. Among the vertices that are ancestors of both v and w, the one with the greatest height is an LCA of v and w."

In a graph like this 1->3 1->4 2->3 2->4, 3 and 4 will have multiple LCA's because the height of 1 and 2 would be same.

So, How can I proceed to implement this? I am thinking of applying the same approach that we used to find LCA in a binary tree by starting from root node (In this case, nodes having in_degree=0) but due to cross edges between the nodes this approach wouldn't work.eg. 1->2 1->3 3->2.

So, Is there some better way to find the LCA in DAG's?

$\endgroup$
  • 2
    $\begingroup$ Not every two vertices have a least common ancestor. If you interpret your DAG as a poset (by taking transitive closure), then least common ancestor corresponds to meet ($\land$). A poset in which every two elements have a meet is called a meet-semilattice. Not every poset is one. $\endgroup$ – Yuval Filmus Apr 2 '18 at 11:51
  • $\begingroup$ "for a graph like this 1->2 1->3 3->2, the LCA would be 3 and not 1" -- the LCA of what? $\endgroup$ – j_random_hacker May 18 '18 at 7:57
  • $\begingroup$ I have updated my question $\endgroup$ – shiwang May 18 '18 at 8:08
0
$\begingroup$

Assume that you want to find the ancestors of x and y in a graph.

Maintain an array of vectors- parents (storing parents of each node).

  1. Firstly do a bfs(keep storing parents of each vertex) and find all the ancestors of x (find parents of x and using parents, find all the ancestors of x) and store them in a vector. Also, store the depth of each parent in the vector.

  2. Find the ancestors of y using same method and store them in another vector. Now, you have two vectors storing the ancestors of x and y respectively along with their depth.

  3. LCA would be common ancestor with greatest depth. Depth is defined as longest distance from root(vertex with in_degree=0). Now, we can sort the vectors in decreasing order of their depths and find out the LCA. Using this method, we can even find multiple LCA's (if there).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.