[Solved]: Linear time labeling algorithm for a tree?

Problem Detail: 

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.

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

Asked By : Bob Whiz

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10819