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

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

标签： pythonalgorithm

Answer 1

从您谈论它的方式来看，听起来您比图表更想要一棵树。否则，您实际上并不是在编写“级别”算法，而是在编写“与节点的距离”算法。树可以有级别，您要求图表上两个节点之间的最远距离。

如果您打算自己编写代码，则基本上可以执行广度优先搜索类型算法，您可以在其中获取源节点（在本例中为 0）找出与之链接的内容。如果您要返回地图，则将等于这些节点的键和值设置为 1。然后找到指向这些节点的下一个链接，不包括先前的节点，迭代这些链接并将值保存到地图中，但现在的值为 2。循环直到你没有更多的孩子。如果您对树执行此操作，则可以删除检查以排除先前的节点。