CC++ & Algorithm

矩阵快速幂在图论中的应用

极难2
语言版本：通用
概述：利用邻接矩阵的幂来快速计算图中固定长度路径的数目。

好的，这是根据您的要求扩展后的文章。我保留了所有原有内容，并在薄弱处补充了更多解释、生活化例子和常见错误，使文章更丰容完整。

矩阵快速幂在图论中的妙用 -- 几步能到？从走迷宫到传纸条

你学过图论吗？图是由一些点和连接这些点的边组成的。比如你在地图上，城市是点，道路是边。现在老师问你：“从城市 A 到城市 B，恰好走 k 步（允许重复经过点和边），有多少种不同的走法？” 你能快速回答吗？如果图很大，k 很大，用普通搜索会非常慢。但用矩阵快速幂，可以轻松搞定。

这其实是图论中一个非常酷的应用：用邻接矩阵的幂来快速计算图中恰好走固定步数的路径数目。无论图是有向还是无向、有没有自环，矩阵快速幂都能帮你几秒钟算出答案。想象一下，你有一张朋友圈关系图，想知道从“小明”开始，经过恰好 5 次转发（允许重复），有多少种方式能传到“小红”手里？矩阵快速幂就是解决这类问题的利器。

生活中的例子：迷宫寻宝 & 班级传纸条

例子一：迷宫寻宝（原例）

假设有个迷宫，有 3 个房间（编号 0,1,2），房间之间有门连接（可以双向走）。你从房间 0 出发，每走一步进入下一个房间，请问走 2 步后有多少种方式到达房间 2？我们可以逐步模拟，但如果走 100 步，手动就太困难了。矩阵快速幂可以自动算出任意步数的方案数。

例子二：班级传纸条（新例子）

班级里 4 个同学围坐一圈（编号 0,1,2,3），只能传给相邻的人（即 0 只能传给 1 和 3，1 只能传给 0 和 2，等等），而且可以传回来。你从同学 0 出发，想传一张纸条，恰好经过 3 次传递到达同学 2，有多少种传递路线？用矩阵快速幂，只要写出邻接矩阵，算它的 3 次幂，直接读出 (0,2) 位置的数字即可。而且你还可以改步数，比如 10 步、100 步，手动无法完成，但计算机只花零点几秒。

图的邻接矩阵

对于一个有 n 个节点的图（节点编号 0~n-1），我们可以构造一个 n×n 的矩阵 A，称为邻接矩阵。A[i][j] 表示从节点 i 到节点 j 是否有直接边（若有则为1，否则为0，也可以带权值）。对于无向图，矩阵对称；有向图不一定对称。

关键定理：邻接矩阵的 k 次幂 Aᵏ 的 (i, j) 元素，表示从节点 i 恰好走 k 步到达节点 j 的不同路径数目（允许重复经过节点和边）。为什么呢？因为矩阵乘法本身就对应了“通过中间节点”的组合计数。A²[i][j] = sumₖ A[i][k]·A[k][j]，正是先走一步到 k，再走一步到 j 的路径数。以此类推，归纳可得 Aᵏ 的 (i,j) 就是长度 k 的路径数。

举个简单例子帮理解

假设图只有 2 个节点 0 和 1，并且有一条边 0→1，没有其他边。邻接矩阵：

A = [ [0, 1],
      [0, 0] ]

计算 A²：

  • (0,0): A[0][0]·A[0][0] + A[0][1]·A[1][0] = 0·0 + 1·0 = 0
  • (0,1): A[0][0]·A[0][1] + A[0][1]·A[1][1] = 0·1 + 1·0 = 0
  • (1,0): A[1][0]·A[0][0] + A[1][1]·A[1][0] = 0·0 + 0·0 = 0
  • (1,1): A[1][0]·A[0][1] + A[1][1]·A[1][1] = 0·1 + 0·0 = 0 所以走 2 步，任何节点之间都没有路径（因为只有一条单向边，无法走 2 步）。这符合直觉。

算法步骤

  1. 建图：根据图的边构造邻接矩阵 A（n×n）。如果有两条重边（比如两条不同的路径从 i 到 j），就把 A[i][j] 设为边的数量。
  2. 快速幂：使用矩阵快速幂计算 Aᵏ。
  3. 读结果：结果矩阵的 (i,j) 元素即为从 i 到 j 恰好走 k 步的路径数目。
  4. 模数可选：如果结果很大，可以取模（比如 10⁹+7），避免溢出。

注意：如果图有自环（自己连自己），则邻接矩阵对角线上为 1，这样路径可以停留在原地。

常见错误（新手容易踩的坑）

  1. 忘记考虑自环
    有些图允许节点原地不动（比如电梯停在某一层），此时邻接矩阵对角线应为 1。如果忘记设，路径计数会漏掉“停留”的情况。

  2. 编号从 0 还是 1？
    矩阵下标从 0 开始，图节点编号也尽量从 0 开始，避免混淆。如果题目节点从 1 开始，记得减 1 处理。

  3. 整数溢出
    路径数目可能非常大，超过 int 范围。在 C++ 中要用 long long，Python 整数无限大但可能很慢，建议取模。

  4. 模运算位置
    在矩阵乘法中，每次加法后都应该取模（如果使用模数），否则中间结果可能溢出。代码中 if (mod) sum %= mod; 是对的。

  5. 快速幂边界条件
    当 k=0 时，A⁰ 应该是单位矩阵，表示“不走”的情况。我们的代码已经处理了（初始化 res 为单位矩阵）。

  6. 无向图与有向图
    无向图的每条边要拆成两条有向边，如 0-1 要设 adj[0][1]=1 和 adj[1][0]=1。容易只设一个方向。

完整代码示例（带详细注释）

C++ 实现（增强注释版）

#include <iostream>
#include <vector>
using namespace std;

// 矩阵乘法函数，返回 A * B
// 如果 mod 不为 0，则结果对 mod 取模
vector<vector<long long>> matMul(const vector<vector<long long>>& A,
                                 const vector<vector<long long>>& B,
                                 long long mod = 0) {
    int n = A.size();               // 矩阵大小
    vector<vector<long long>> C(n, vector<long long>(n, 0)); // 结果矩阵初始化为0
    for (int i = 0; i < n; i++) {   // 行
        for (int j = 0; j < n; j++) { // 列
            long long sum = 0;      // 累加中间乘积
            for (int k = 0; k < n; k++) { // 中间节点
                sum += A[i][k] * B[k][j];
                if (mod) sum %= mod;
            }
            C[i][j] = sum;
        }
    }
    return C;
}

// 矩阵快速幂：计算 M 的 k 次幂
vector<vector<long long>> matPow(vector<vector<long long>> M, long long k, long long mod = 0) {
    int n = M.size();
    // 单位矩阵：对角线上为1，其余为0
    vector<vector<long long>> res(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) res[i][i] = 1;
    while (k > 0) {          // 快速幂循环
        if (k & 1LL) {        // 如果当前二进制位是1
            res = matMul(res, M, mod);  // 累乘
        }
        M = matMul(M, M, mod); // 底数平方
        k >>= 1;               // 右移一位
    }
    return res;
}

int main() {
    // 示例：3个节点的有向图，边：0->1, 0->2, 1->2, 2->0
    int n = 3;
    vector<vector<long long>> adj(n, vector<long long>(n, 0));
    adj[0][1] = 1;   // 0 -> 1
    adj[0][2] = 1;   // 0 -> 2
    adj[1][2] = 1;   // 1 -> 2
    adj[2][0] = 1;   // 2 -> 0

    long long k = 4;  // 走4步
    auto Ak = matPow(adj, k);
    cout << "从节点i到j走" << k << "步的路径数:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << "(" << i << "," << j << "):" << Ak[i][j] << " ";
        }
        cout << endl;
    }
    // 输出例如 (0,0): 2, (0,1): 1, (0,2): 1 等，可以手动验证
    return 0;
}

Python 实现（增强注释版）

def mat_mul(A, B, mod=None):
    """矩阵乘法，可选取模"""
    n = len(A)
    C = [[0]*n for _ in range(n)]
    for i in range(n):          # 行
        for j in range(n):      # 列
            s = 0
            for k in range(n):  # 中间节点
                s += A[i][k] * B[k][j]
                if mod:
                    s %= mod
            C[i][j] = s
    return C

def mat_pow(M, k, mod=None):
    """矩阵快速幂，计算 M 的 k 次幂"""
    n = len(M)
    # 单位矩阵：对角线为1，其余为0
    res = [[1 if i==j else 0 for j in range(n)] for i in range(n)]
    base = M
    while k > 0:
        if k & 1:           # 当前二进制位为1
            res = mat_mul(res, base, mod)
        base = mat_mul(base, base, mod)   # 底数平方
        k >>= 1
    return res

# 示例
if __name__ == "__main__":
    n = 3
    adj = [[0]*n for _ in range(n)]
    adj[0][1] = 1  # 0 -> 1
    adj[0][2] = 1  # 0 -> 2
    adj[1][2] = 1  # 1 -> 2
    adj[2][0] = 1  # 2 -> 0

    k = 4
    Ak = mat_pow(adj, k)
    print(f"走{k}步的路径数：")
    for i in range(n):
        for j in range(n):
            print(f"({i}->{j}): {Ak[i][j]}", end=" ")
        print()

深入理解：为什么邻接矩阵的幂能计数？

我们用数学归纳法再梳理一遍。

  • 基础步 (k=1)：从 i 到 j 恰好走 1 步的路径数就是直接边是否存在，即 A[i][j]。显然成立。
  • 归纳假设：假设对于步数 k-1，A^(k-1)[i][j] 恰好等于从 i 到 j 走 k-1 步的路径数。
  • 归纳步 (k)：走 k 步的路径可以分解为：先走 1 步到某个中间节点 t，再从 t 走 k-1 步到 j。所以路径总数 = Σₜ (从 i 到 t 走 1 步的路径数) × (从 t 到 j 走 k-1 步的路径数) = Σₜ A[i][t] × A^(k-1)[t][j]。
  • 恰好，矩阵乘法 (A × A^(k-1))[i][j] 的定义就是 Σₜ A[i][t] × A^(k-1)[t][j]。
  • 所以 A^k = A × A^(k-1)，其 (i,j) 元素就对应了走 k 步的路径数。归纳完成。

这个证明也反过来帮助我们理解为什么矩阵乘法的规则恰好对应路径计数——因为乘法把两条路径“拼接”起来，加法把不同中间节点的选择加起来。

应用扩展

  • 带权路径数：如果边上有多种类型（比如不同颜色的边），可以把邻接矩阵的元素设为边的数量（2条边则值为2）。
  • 最短路径（不同乘法）：如果要求最短路径长度，可以用 min-plus 矩阵乘法（即加法变成取 min，乘法变成加法），此时矩阵快速幂对应 Floyd 算法的思想，可以求经过恰好 k 条边的最短路。但这里我们只讲计数。
  • 有自环的图：自环相当于可以在原地停留一次，对走 k 步的计数有贡献。
  • 概率转移矩阵：如果把邻接矩阵元素改为“转移概率”（概率值在 0~1 之间），那么 A^k 的 (i,j) 就表示从 i 出发走 k 步到达 j 的概率。这在马尔可夫链中非常常见。

练习

  1. 自环的影响：修改上面的代码，加入自环（比如节点0有自环，则 adj[0][0]=1），重新计算 k=2 时 0->0 的路径数。观察结果比之前多出哪些路径。
  2. 完全图：给你一个完全图（每对不同节点间都有双向边），求从节点0到节点1恰好走3步的路径数。理论上可以用组合数学计算，然后验证矩阵快速幂结果。
  3. 取模练习：把上面的代码加上取模 mod = 10**9+7，计算 k=100 时从 0 到 1 的路径数（节点数目可改为 10 个）。体会取模防止溢出的好处。

总结

矩阵快速幂在图论中非常实用，它把路径计数问题转化为矩阵幂运算，利用快速幂在 O(n³ log k) 时间内解决。对于节点数较小但步数很大的图，这个方法是不可替代的。学到这里，你已经掌握了从数字快速幂到矩阵快速幂，再到具体应用的全套技能。

相关指引：

  • 如果你对“如何构造邻接矩阵”还不熟悉，可以回顾“图论基础：图的表示（邻接矩阵和邻接表）”。
  • 想进一步优化时间复杂度到 O(n² log k) 吗？那是利用矩阵乘法的 Strassen 算法，目前对初学者不推荐。
  • 想探索概率转移矩阵？那其实是马尔可夫链，在机器学习里非常重要。
  • 如果遇到边带权值且要求“最短路径”，可以学习 min-plus 矩阵乘法（也称为热带数学）。
  • 另外，矩阵快速幂还能用来加速递推数列（如斐波那契数列），这是它的另一个经典应用。

继续加油，未来可以向更复杂的算法（如状态压缩DP、概率转移矩阵、图神经网络）迈进！

例题精讲

1单选题

给定一个n个顶点的有向图，其邻接矩阵为A。设P = A^k，其中k是正整数。则P[i][j]的含义是？

A从顶点i到顶点j的长度为k的路径数目
B从顶点i到顶点j的最短路径长度
C从顶点i到顶点j的所有路径总数（长度不限）
D从顶点i到顶点j的简单路径数目（顶点不重复）
2判断题

在使用矩阵快速幂计算无向图中长度为k的路径数目时，邻接矩阵是对称矩阵，且每次矩阵乘法后得到的矩阵仍然保持对称。

3填空题
以下代码用矩阵快速幂计算有向图中长度为k的路径数目（模MOD）。请补全while循环中的条件判断。

struct Mat { int n; int a[MaxN][MaxN]; };
Mat mul(Mat A, Mat B, int mod) { /* 返回A*B%mod */ }
Mat mat_pow(Mat base, int k, int mod) {
    Mat res = identity(base.n); // 单位矩阵
    while (k) {
        if (___) res = mul(res, base, mod);
        base = mul(base, base, mod);
        k >>= 1;
    }
    return res;
}
4单选题

一个图有n个顶点，使用矩阵快速幂计算长度为k（k很大，如10^18）的路径数目（模M），则算法的时间复杂度为（矩阵乘法采用标准O(n^3)实现）？

AO(n^3 log k)
BO(n^2 log k)
CO(n^3 k)
DO(n log n log k)
5判断题

在计算图中长度为k的路径数目时，如果k非常大（如10^12），使用矩阵快速幂仍然可以在较短时间内得出结果，这是因为快速幂将指数k分解为二进制，只需O(log k)次矩阵乘法。