时间戳

首页 > 解决方案 > 图顶点排序度问题：找到k-ordering

python - 图顶点排序度问题：找到k-ordering

问题描述

给定一个图 G，一个 k-ord

dering 为 3（k 是最大度数）

要更多的cd等等。

如果存在，则查找算法。

标签： pythonalgorithmmathgraph-theorygraph-traversal

解决方案

有几种可能的方法，具体取决于应用程序所需的复杂性等约束。

需要注意的一件事是，如果存在，贪心方法会产生有效的排序。IfV是节点的完整列表，并且d(v)是残差图中的度数：

order = []
while |V| > 0:
    let v be the node with a minimum degree
    if d(v) > k return false
    add v to order
    remove v from the graph
return order

主要挑战是维护尊重度数更新的节点顺序。这可以通过堆来解决，在这种情况下，斐波那契堆很有用，因为它可以在O(1)摊销时间内更新密钥。

构建堆需要O(n). 每个节点移除成本O(log(n)) + O(k)。因此，总体复杂度为O(n·log(n) + n·k)

推荐阅读