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$
2
  • $\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, 2014 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, 2014 at 20:29

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .