我有一个无环有向图。我想以一种方式为每个顶点分配级别,以保证如果边 (v1,v2) 在图中,则级别 (v1) > 级别 (v2)。如果 level(v1) = level(v3) 无论何时 (v1,v2) 和 (v3,v2) 在图中,我也想要它。此外,可能的级别是离散的(不妨将它们视为自然数)。理想情况是 level(v1) = level(v2) + 1 只要 (v1,v2) 在图中并且没有从 v1 到 v2 的其他路径,但有时在其他约束条件下这是不可能的 -例如,考虑具有边 (a,b) (b,d) (d,e) (a,c) (c,e) 的五个顶点的图。
有谁知道解决这个问题的体面算法?我的图表相当小(|V| <= 25 左右),所以我不需要快速的东西 - 简单更重要。
到目前为止,我的想法是只找到一个最小元素,将其分配为 0 级,找到所有父元素,将它们分配为 1 级,并通过向适当的顶点添加 +0.5 来解决矛盾,但这看起来很糟糕。
此外,我觉得删除所有“隐式”边可能会有所帮助(即,如果图形同时包含 (v1,v2) 和 (v2,v3),则删除 (v1,v3)。
最佳答案
我认为让 v 的层级为从 v 出发的最长有向路径的长度可能对你很合适。在 Python 中:
# the level of v is the length of the longest directed path from v
def 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}
关于java - 如何将 "levels"分配给无环有向图的顶点?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3420685/