Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 7 down vote favorite

I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This process continues in the obvious way until all vertices have a label. The reason I do this is I want to store the vertices in a queue, and go through them "leaves first". Is there an easy way to do this $O(n+m)$ time?

I can solve the problem by doing a BFS on every step. But in the worst case, on every step I go through every vertex, remove exactly two leaves and enqueue them. I believe this takes quadratic time.

Another idea was to first find all the leaves, and then do a BFS from every leaf. This doesn't give me the desired solution. For example, consider a kind of "crown graph" as in the figure below. The desired solution is shown, but launching a BFS from each leaf would result in only two labels used.

enter image description here

Ideally, the linear time algorithm would also be easy to explain and implement.

share|improve this question

1 Answer

up vote 7 down vote accepted

Unrooted Trees

You can use a priority queue to solve this in $O(E+V\log V)$:

  • Put all vertices in a priority queue, with their priority being their degree.
  • While the queue is non-empty:
    • Remove a vertex $v$ of minimal priority, which must be $1$ (or $0$ at the very end).
    • Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
    • Subtract $1$ from the priority of the unique remaining neighbor of $u$ (if any).

In fact, we don't really need a priority queue, and this algorithm can be implemented using a simple queue in time $O(E+V)$:

  • Initialize an array of length $V$ with the degrees of all vertices.
  • Initialize another array of length $V$ with "alive".
  • Go once through the first array, and push all vertices of degree $1$ to a queue.
  • While the queue is non-empty:
    • Pop a vertex $v$.
    • Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
    • Mark $v$ as "dead".
    • If $v$ has some "alive" neighbor $u$, subtract $1$ from the degree of $u$.
    • If the new degree of $u$ is $1$, push $u$ to the queue.

Rooted Trees

Use DFS instead. Here is a sketch of the algorithm.

  • Given a node $v$, if $v$ is a leaf, set $d(v) = 1$.
  • If $v$ is not a leaf, run the algorithm on all its children, and then let $d(v) = 1 + \max d(u)$, where $u$ goes over the set of all children.

You run this algorithm on the root.

share|improve this answer
Is this right? Consider the tree 1->2->3->4->5, where 1 is the root. 2 should be getting the label 1, but you give 3? Or by children you mean neighbors? Which node do we start the dfs from then? – Knoothe Mar 27 at 4:36
My implementation is "off by one", but according to your description, $2$ should be getting the label $4$, since you have to remove $5$, then $4$, then $3$, and only then does $2$ become a leaf. – Yuval Filmus Mar 27 at 4:46
I did not ask the question :-). I interpreted the question to be: An undirected tree. Label all leaves. Delete them. Recurse on the resulting tree. In that case the tree is actually 1-2-3-4-5, Step 1, you delete 1 and 5, then 2 and 4 and then 3. See the paragraph about "crown graph". This is one of the classic algorithms to find the center of a tree. – Knoothe Mar 27 at 4:47
1 is not a leaf. It is very far from being a leaf, it is the root. I interpreted the question as targeting rooted trees. Perhaps we should wait for the OP to respond. – Yuval Filmus Mar 27 at 4:48
2  
@YuvalFilmus, just to throw my 2 cents in, shouldn't it be $1+max\{d(u)\}$? The leaves are $1$, if you delete them then the new leaves should be $2$, so it's kind of a measure of how many layers you have to delete before the vertex becomes a leaf. With min, any vertex adjacent to a leaf gets 2, but it may not become a leaf when the leaves are deleted. That sentence had too many leaves in it. I need a broom. – Luke Mathieson Mar 27 at 5:09
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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