1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ What do yo call the distance ? Euclidean distance or length of the shortest path (with unit or weighted edges) ? $\endgroup$
    – user16034
    Commented Jun 7, 2022 at 7:12

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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.
    Commented May 23, 2019 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
    Commented May 23, 2019 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
    Commented May 23, 2019 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.
    Commented May 23, 2019 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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