如何结合代码分析回溯法实现的图着色问题时间复杂度？

让我们一步步从你提供的核心代码出发，拆解图着色回溯算法的时间复杂度推导过程，其中n是顶点数，m是颜色数。

1. 先看辅助函数 isSafe 的时间开销 #

bool isSafe (int v, bool graph[V][V], int color[], int c) {
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;
    return true;
}

这个函数的作用是校验：给顶点v分配颜色c是否合法（即相邻顶点没有使用同一种颜色）。它会遍历全部V个顶点（V就是顶点数n），所以单次调用的时间复杂度是O(n)。

2. 递归回溯核心 graphColoringUtil 的逻辑与递归树分析 #

bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
    if (v == V)
        return true; // 所有顶点着色完成，终止递归
    for (int c = 1; c <= m; c++) { // 尝试m种颜色选项
        if (isSafe(v, graph, color, c)) {
            color[v] = c;
            if (graphColoringUtil(graph, m, color, v+1))
                return true;
            color[v] = 0; // 回溯，撤销当前颜色分配
        }
    }
    return false;
}

这个函数是回溯逻辑的核心，我们从递归树的角度拆解时间开销：

• 递归终止条件：当v == V时，说明n个顶点全部完成着色，这一步时间为O(1)。
• 递归分支展开：对于当前顶点v，我们会尝试m种不同的颜色。每尝试一种颜色，都要先调用isSafe做合法性检查（O(n)），如果合法，就递归处理下一个顶点v+1。

递归树的节点数量量级 #

递归过程可以看作一棵多层的树：

• 第0层（处理第1个顶点v=0）：有m个节点（对应m种颜色选择）。
• 第1层（处理第2个顶点v=1）：每个第0层节点会衍生m个新节点，共m²个节点。
• ...
• 第n-1层（处理第n个顶点v=n-1）：共有mⁿ个叶子节点（对应所有可能的颜色组合）。

递归树的总节点数是等比数列 m + m² + ... + mⁿ，求和后量级为O(mⁿ)。

总时间复杂度计算 #

最坏情况下（比如图中没有任何边，所有颜色选择都合法），每个颜色尝试都会进入下一层递归。此时：
每个递归节点都需要执行一次O(n)的isSafe检查，再加上递归调用的开销。总时间就是「单次节点的时间开销 × 总节点数」，即：
O(n) × O(mⁿ) = O(n*mⁿ)

即使在有边的图中，最坏情况依然是每个顶点都能尝试m种颜色（比如特定图结构下，每个顶点的相邻顶点颜色都不冲突所有m种选择），所以时间复杂度的上界依然是O(n*mⁿ)。

内容的提问来源于stack exchange，提问作者Rahul Krishna