如何为非循环有向图的顶点分配“级别”？

如何为非循环有向图的顶点分配“级别”？

我认为将v的水平设为v的最长有向路径的长度可能对您来说很好。在Python中：

# the level of v is the length of the longest directed path from vdef assignlevel(graph, v, level):    if v not in level:        if v not in graph or not graph[v]: level[v] = 0        else: level[v] = max(assignlevel(graph, w, level) + 1 for w in graph[v])    return level[v]g = {'a': ['b', 'c'], 'b': ['d'], 'd': ['e'], 'c': ['e']}l = {}for v in g:    assignlevel(g, v, l)print l

输出：

{'a': 3, 'c': 1, 'b': 2, 'e': 0, 'd': 1}