12
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Knoothe Mar 27 '13 at 4:36
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 27 '13 at 4:46
  • $\begingroup$ 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. $\endgroup$ – Knoothe Mar 27 '13 at 4:47
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 27 '13 at 4:48
  • 2
    $\begingroup$ @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. $\endgroup$ – Luke Mathieson Mar 27 '13 at 5:09
2
$\begingroup$

A straightforward answer is as follows:

  • Turn this into a directed graph, where we have an edge $(u,v)$ from each node $u$ to its parent $v$. Note that you get a dag (directed acyclic graph).

  • Topologically sort the graph.

  • Scan the vertices, in sorted order. Label each vertex with one more than the largest of the labels on its predecessors. Since we're scanning in topological order, all of the predecessors of $v$ will already have received a label before we try to label $v$.

Each of these steps can be done in $O(n+m)$ time, so the total running time is $O(n+m)$. I mention this alternative approach only in case you find it conceptually easier to understand than Yuval's answer.

$\endgroup$

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.