Finding the height of all nodes in a forest

I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges to traverse in reverse to reach a vertex of height 0.

I also know that the average degree of a node is a small constant, say 2 or so. To find the height of all vertices, I can think of two algorithms:

Walking Algorithm

• Go through and mark $h=0$ for vertices with no incoming edges.

• For each vertex with $h=0$, follow the outgoing edges, updating the height of each encountered vertex if it's previous height is smaller.

Frontier Algorithm

• Go through and mark $h=0$ for vertices with no incoming edges, and mark these as the frontier.

• For every frontier vertex, see if it's parent has children at or below the frontier, If it does, mark the parent as having $1$ plus the largest height among its children. Mark the parent as being on the frontier.

• Repeat 2 until there is nothing beyond the frontier.

My questions:

• Is there a name for this problem, and a well known fastest solution?

• I tend to think simply walking up from all the $h=0$ vertices is the fastest solution. Am I right?

First of all, it depends a bit how you can access your data to say which algorithms works best.

Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that

$$\text{height}(v)=\begin{cases}
\left(\max_{u\text{ child of }v}\text{height}(u)\right)+1 & \text{if $u$ is not a leaf} \\
\hskip4ex 0 & \text{otherwise}
\end{cases}.
$$

So you can scan for all roots, and then determine the heights by divide an conquer. You will touch every vertex at most twice (scanning for the roots + traversing). In the approach that you have suggested you might have to touch some vertices many times.

Btw, since you have a forest, you have less edges than vertices, so you know that you have average degree less than two (and therefore you can test for roots in linear time).

StackExchange Computer Science Q#5027, answer score: 7