树的顶点覆盖是线性时间还是多项式时间

Question

我有以下算法来找到树的最小顶点覆盖。这是一个最小大小的顶点集S，使得对于G中的每个边(v，u(，v在S中或u在S中。

有人告诉我，该算法具有线性时间复杂性，但我不明白这是怎么回事，因为边的数量不是O(n(阶的u，所以复杂性是O(n^2(？

设T＝<V、 E>成为一棵树。也就是说，顶点集是V，边集是E。还假设覆盖集＝C。算法可以描述如下：

while V != [] do
Identify a leaf vertex v
Locate u = parent(v), the parent vertex of v.
Add u to C
Remove all the edges incident to u
return C.

Answer 1

在树中，|E|=|V|-1，因此总共有O(n(条边需要处理。