计算图着色代码复杂度的差异

Question

考虑下面的代码。假设所讨论的图有 N 个节点，每个节点最多有 D 个邻居，并且 D+1 种颜色可用于为节点着色，使得与边连接的两个节点都没有分配给它们相同的颜色。我估计下面代码的复杂度是 O(N*D)，因为对于 N 个节点中的每一个，我们循环遍历该节点的至多 D 个邻居来填充集合 illegal_colors，然后遍历颜色列表包含 D+1 种颜色。但是给出的复杂度是 O(N+M)，其中 M 是边的数量。我在这里做错了什么？

def color_graph(graph, colors):
    for node in graph:
        if node in node.neighbors:
            raise Exception('Legal coloring impossible for node with loop: %s' %
                            node.label)

        # Get the node's neighbors' colors, as a set so we
        # can check if a color is illegal in constant time
        illegal_colors = set([
            neighbor.color
            for neighbor in node.neighbors
            if neighbor.color
        ])

        # Assign the first legal color
        for color in colors:
            if color not in illegal_colors:
                node.color = color
                break

Answer 1

边数M、最大度数D和节点数N满足不等式： M <= N * D / 2.

因此 O(N+M) 包含在 O(N*(D+1)) 中。

在您的算法中，您遍历每个节点的每个邻居。它的确切复杂度不是 N*D，而是 d1 + d2 + d3 + ... + dN，其中 di 是节点 i 的度数。此总和等于 2*M，最多 N*D，但可能更少。

因此你的算法的复杂度是O(N+M)。因此它也是O(N*(D+1))。请注意 O(N*(D+1)) = O(N*D) 在假设 D >= 1.

下

说你的算法在 O(N+M) 中运行比说它在 O(N*D) 中运行稍微精确一些。如果大多数节点的邻居比 D 少很多，那么 M+N 可能比 N*D.

小得多

还要注意O(M+N) = O(M)假设每个节点至少有一个邻居。

计算图着色代码复杂度的差异

Discrepancy in calculating graph coloring code complexity

python

graph

graph-coloring