3

我有一个无环有向图。我想以一种方式为每个顶点分配级别，以保证如果边（v1，v2）在图中，那么级别（v1）>级别（v2）。如果 level(v1) = level(v3) 每当 (v1,v2) 和 (v3,v2) 在图表中时，我也想要它。此外，可能的水平是离散的（不妨将它们视为自然数）。理想的情况是当 (v1,v2) 在图中并且没有从 v1 到 v2 的其他路径时 level(v1) = level(v2) + 1，但有时在其他约束条件下这是不可能的 -例如，考虑一个具有五个顶点的图，其边为 (a,b) (b,d) (d,e) (a,c) (c,e)。
有谁知道一个体面的算法来解决这个问题？我的图表相当小（|V| <= 25 左右），所以我不需要快速的东西——简单更重要。

到目前为止，我的想法是找到一个最小元素，将其指定为 0 级，找到所有父级，将它们指定为 1 级，并通过在适当的顶点上添加 +0.5 来解决矛盾，但这看起来很糟糕。

另外，我觉得删除所有“隐式”边可能会有所帮助（即，如果图形同时包含（v1，v2）和（v2，v3），则删除（v1，v3）。

4

2 回答 2

5

我认为让 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}
于 2010-08-06T04:05:54.563 回答
2

您可以使用拓扑排序为具有所需属性的每个顶点分配一个唯一编号类似地，您可以按拓扑顺序遍历节点并分配 max(parents) + 1

于 2010-08-06T04:33:55.640 回答