计算有向图中每个节点的级别的最快方法是什么？

Question

给定一个由两个节点和链接列表表示的层次图，找到所有节点级别的最佳解决方案是什么？你知道吗

以下节点的名称纯粹是虚构的，不会排序。 请注意，源节点应该很容易找到，因为它是唯一一个没有父节点的节点。你知道吗

如果发生特殊情况（如多个级别），则只应返回最大的一个。你知道吗

插图：

输入：

g = Graph()
g.addNodes([0, 1, 2, 3, 4, 5, 6, 7])
g.addLink(0, 1)
g.addLink(0, 2)
g.addLink(1, 3)
g.addLink(1, 4)
g.addLink(1, 5)
g.addLink(2, 6)
g.addLink(6, 7)
getLevels(g.nodes, g.links)

输出：

#Node : Level
0 : 0
1 : 1
2 : 1
3 : 2
4 : 2
5 : 2
6 : 2
7 : 3

Answer 1

从你谈论它的方式来看，听起来你更想要一棵树而不是一张图。否则，您并不是真正编写“levels”算法，而是“distance from node”算法。树可以有层次，你要求的是图上两个节点之间的最远距离。你知道吗

如果你自己编写代码，你基本上可以做一个breadth first search类型的算法，把你的源节点（在这个例子中是0）拿出来找出它的链接。如果要返回贴图，请将关键帧设置为这些节点，并将值设置为1。然后找到指向这些节点的下一个链接（不包括以前的节点），对这些节点进行迭代，并将值保存到映射中，但现在值为2的情况除外。循环直到你没有更多的孩子。如果对树执行此操作，则需要删除复选框以排除先前的节点。你知道吗

Answer 2

根据树的表示形式，您需要某种机制来枚举节点的子节点。然后使用如下函数

TellLevels(Root, Level):
    Say "The node ", Root.Id, " has level ", Level
    for Son= FirstSon(Root) to LastSon(Root)
        TellLevels(Son, Level + 1)

并用

TellLevels(Root, 0)

这仅在图具有树拓扑时有效。你知道吗

---

避免骑车：

TellLevels(Root, Level):
    Root.Visited= true
    Say "The node ", Root.Id, " has level ", Level
    for Son= FirstSon(Root) to LastSon(Root)
        if not Son.Visited
            TellLevels(Son, Level + 1)