In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, which gives us $\mathcal{O}(V + E)$ running time.

Is there any better way to do this? possibly with one BFS?

EDIT: We can start two BFS from $w$ and $v$ simultaneously and one step at a time. First we find the nodes in distance 1 of the $w$ then the nodes in distance 1 of $v$ and then nodes at distance 2 of $w$ and so on. by the time there is no node in the queue of BFS of node $v$, we can end the search. any node which is first visited with $v$ BFS is closer to $v$ than $w$.

But again I suppose there is a more efficient way to do this.

  • $\begingroup$ Please clarify that whether "any node which is closer to node $v$ than node $w$" means "any node $x$ such that $dist(x,v)<dist(w,v)$ " or "any node $x$ such that $dist(x,v)<dist(x,w)$". $\endgroup$ – John L. May 23 '19 at 2:49
  • $\begingroup$ I edited the post. $\endgroup$ – mahdi gh May 23 '19 at 9:04

You can do this with only one BFS and the solution is very simple.

I will assume that you have as input a graph $G = (V, E)$. Let $dist$ be a vector which stores the distance of all nodes of your graph to node $v \in V$.

You must run a BFS algorithm starting on node $v$ and store the distance from each node to $v$ in $dist$. This value can be simply obtained during the BFS execution. Then, you can iterate through this vector marking (or deleting) all nodes $i$ such that $dist[i]$ < $dist[w]$.

The overall complexity of this algorithm is $\mathcal{O}(V + E + V)$. In a tree, we have that $|E| = |V|-1$. Thus, the complexity is $\mathcal{O}(3 V) = \mathcal{O}(V)$.

| cite | improve this answer | |
  • $\begingroup$ I am afraid this answer is wrong. Consider the graph with edges $xu$, $uv$ and $vw$. $dist_v[x]=2 > dist_v[w]=1$. However, $x$ is nearer to $v$ than $w$. $\endgroup$ – John L. May 23 '19 at 0:30
  • $\begingroup$ Why $x$ is nearer to $v$ than $w$? In your example, $dist_v[w] = 1$ (it follows the path $<w, v>$) and $dist_v[x] = 2$ (it follows the path $<x, u, v>$). Thus, you will not delete or mark node $x$. $\endgroup$ – Iago Carvalho May 23 '19 at 1:21
  • $\begingroup$ I see now... There are two possible interpretations of this question. The first one (which I answered) is to find the nodes whose distance to $v$ are smaller than the distance from $v$ to $w$. The second interpretation (which I now answered) is @Appas Jack interpretation. $\endgroup$ – Iago Carvalho May 23 '19 at 1:28
  • $\begingroup$ Now I see your point of view. Indeed, your interpretation should have been more natural had there not been the fact that asker can solve the problem with two BFS but not with one BFS. $\endgroup$ – John L. May 23 '19 at 2:45

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.