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 &amp; \text{if $u$ is not a leaf} \\
\hskip4ex 0 &amp; \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).