图中节点的计算级别

Question

我想计算有向图中每个节点的级别。我目前正在对没有传入边的顶点应用深度优先搜索算法。例如，考虑下图：

预期结果是：

Vertex | Level
1      | 0
2      | 1
3      | 2
4      | 1
5      | 3
6      | 4

在这种情况下，如果我们先在4上应用DFS，则顶点4、3、5和6的所有结果都将是错误的，因为1的级别为0。我试图始终考虑最大的结果对于每个节点，因此在这种情况下，在1上应用DFS时将替换3、5和6的结果。它可以工作，但是我找不到正确计算顶点4级别的方法。

我仅使用有向无环图。

我在这里不包含任何代码，因为它是一个非常简单的DFS实现，并且我在实现方面也没有遇到困难。

任何提示将不胜感激。

Answer 1

您可以从每个顶点开始计算级别，而无需输入边缘。然后，您可以存储每个顶点的最大值直到结束。例如：-顶点3分别从起点1和顶点4遍历时将具有值1和2。最后，您可以更新没有传入边（子代-1上的数字）的顶点。如果存在这样一个顶点的多个子节点的情况，那么您可能希望选择其上具有最大数目的子节点进行替换，然后再次从该顶点运行算法以查看是否更改了分配给其他任何子节点的数字。