0
$\begingroup$

I'm given a tree $T$. I have $n-1$ edges of the form $\{p_i,c_i\}$ where $p_i$ is a parent of $c_i$. The tree has a root, which is a vertex that's a parent and never a child in the edges I'm given. I need an algorithm to determine for two vertices $a$ and $b$ if $a$ lies on a path from $b$ to the root.

Well I thought of it this way.

First I convert the edges I'm given into adjacency lists which takes me $O(m)$ time. All along I keep track of whether I found the root or not (I keep a boolean table for all $n$ vertices, when vertex $x$ is found to be one of $c_i$ I put false in the table, the one in the table with true by the end of the procedure is the root).

So now I have a adjacency list for the graph. Since the graph is a tree, and in a tree there is only one path between two vertices, then there is one path between the root and $b$. Now when I run DFS from the root when I meet $b$ before I meet $a$ then I return false, when I meet $a$ and then $b$ I return true, and when I meet $a$ and return to the root I return false. Overall the complexity of this operation is $O(n+m)$, because I use DFS.

Is this correct?

$\endgroup$
  • $\begingroup$ Please specify what you mean by "meet $a$ and then $b$". Depending on how you do this, your algorithm could be correct or incorrect. (You don't want to accept when $a$ and $b$ are on different branches, but you searched $a$'s branch first.) Also the parameter $m$ doesn't exist for this problem. $\endgroup$ – Thomas Belulovich Feb 26 '14 at 20:00
  • $\begingroup$ $m$ is the number of edges in the graph, meaning $n-1$. Sorry for the confusion, it's a standard notation on my University. If we meet $a$, but we go back to the root in the DFS, I return false. If we meet $a$ and then $b$, all without getting back to the root, I return true. $\endgroup$ – Arek Krawczyk Feb 26 '14 at 20:29
1
$\begingroup$

Assuming every vertex other than the root has a unique parent, why not just store the parent relationships in a length $n$ array $x$? Start with $x=[0,0,...,0]$. For each $\{v_i, v_j\}=\{p_k,c_k\} \in V(T)$, let $x[j]=i$. Suppose $b=v_b$ and $a=v_a$. Then do:

c=x[b];
While[c!=0,
  If[c==a, Return True];
  c=x[c]];
Return False;

This has complexity $O(m+n)$, and only requires $O(n)$ memory.

$\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.