先想象一个画面编号 0 到 4 的五个小朋友站成一圈信息从 0 号手里出发只能沿着规则给定的方向传给指定的人而且必须恰好传 3 次最后信息要落在 4 号手里。让你数一数一共有多少种传法。这就是 LeetCode 的 LCP 07“传递信息”。这道题我愿称之为“邻接矩阵练习的第一课”。题面简单、数据范围友好DFS、动态规划、矩阵快速幂三种主流解法都能跑通而且每个解法的本质都绕不开图的表示方式尤其是邻接矩阵。很多刚接触图论的朋友一上来就被“邻接矩阵”这个概念劝退觉得不过是一张冷冰冰的二维表没什么好研究的。其实你完整做完这道题邻接矩阵从概念到应用基本就吃透了。这篇文章我会从题目本身开始拆解手把手带你把三种解法都实现一遍重点讲清楚 Python 里如何构建邻接矩阵、每一步为什么要这么写以及我练习过程中踩过的、足够让你少走弯路的坑。1. 先看清楚 LCP 07 到底在考什么1.1 游戏规则与两个官方示例原题描述比较口语化我帮你翻译成更直白的语言。一共有 n 名玩家编号从 0 到 n-1其中发起信息的是 0 号接收信息的是 n-1 号。游戏给了一张关系表 relation表中的每一项[u, v]表示“信息可以从 u 号传递给 v 号”注意这是一个有向关系只能按箭头方向传。现在要求信息从 0 出发恰好经过 k 次传递后到达 n-1问一共有多少种不同的传递方案。第一个官方示例是n 5, relation [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k 3答案返回 3。我当时第一次做的时候还专门把三条路径列出来验证了一遍0 - 2 - 1 - 40 - 2 - 3 - 40 - 2 - 0 - 4第二个示例是n 3, relation [[0,2],[2,1]], k 2答案是 0。为什么是 0因为信息从 0 出发第一轮只能到 2第二轮从 2 只能到 1根本没人能传到 2 号也就是 n-1 号手里所以方案数为 0。你注意看这里的关键词是“恰好”。不是“最多 k 次”不是“少于 k 次”是必须走满 k 轮。很多初学者在这里会看岔后面代码也会跟着写错这一点先记住。1.2 邻接矩阵用一张表装下整个图在继续讲解法之前我先把邻接矩阵这个概念讲透。所谓邻接矩阵就是用一个 n 行 n 列的二维数组来存储图。matrix[i][j]的值如果是 1表示存在一条从节点 i 指向节点 j 的边如果是 0表示没有这条边。如果是带权图matrix[i][j]就存权重但 LCP 07 是无权图所以只存 0 或 1 即可。拿上面那个 n5 的示例来说用邻接矩阵表示出来是下面这个 5×5 的表行 \ 列01234000101100001211010300001400000读法很简单第 0 行第 2 列是 1代表 0 可以传给 2第 2 行第 1 列是 1代表 2 可以传给 1。其他位置是 0代表没有对应的边。你可以把这张表理解成一张“直达航班表”行是出发城市列是到达城市相交的格子里标的是“有没有航班”有就是 1没有就是 0。为什么说这道题特别适合练邻接矩阵因为题目给的n ≤ 10矩阵只有 10×10 那么大你可以一行一行写出来自己手动算一遍整个过程完全透明。很多图论题目 n 动辄上万邻接矩阵根本存不下那时候才需要换邻接表但那是后话。在数据规模这么友好的前提下把邻接矩阵的构建、存储、应用全部做一遍是性价比极高的入门训练。2. 三种解法DFS、动态规划、矩阵快速幂2.1 DFS最直观的人肉传话模拟先讲最朴素的想法。信息从 0 号出发每一轮我们枚举当前持有信息的人能把消息传给谁。传一次步数加一。当步数达到 k 的时候检查信息是不是正好在 n-1 号手里如果是方案数加一。这种思路用递归实现就是深度优先搜索DFS代码写起来非常顺。我建议用邻接表来配合 DFS因为每一层只需要访问当前节点的出边邻居不需要遍历整个 n×n 矩阵。虽然这道题 n 很小邻接矩阵遍历也无所谓但养成好习惯后面做大图的时候不吃亏。from typing import List class Solution: def numWays(self, n: int, relation: List[List[int]], k: int) - int: # 构建邻接表 graph [[] for _ in range(n)] for u, v in relation: graph[u].append(v) ans 0 def dfs(node: int, step: int): nonlocal ans if step k: if node n - 1: ans 1 return for nxt in graph[node]: dfs(nxt, step 1) dfs(0, 0) return ans这里有一个细节递归终止条件直接写成step k不需要写step k再去剪枝因为在等于 k 的那一刻我们就 return 了根本不会进入下一层。很多人喜欢在第一行写if step k: return这只在step可能被递增超过 k 的时候才需要我们这种写法完全用不上。DFS 的时间复杂度最坏是 O(n^k)因为每一层最多有 n-1 个分支一共 k 层。不过题目限制了n 10, k 5最坏也就是十万级别的递归量跑起来毫无压力。如果将来遇到 k 很大的变体可以给dfs加上lru_cache(None)做记忆化本质上就变成了自顶向下的动态规划这就和第二种解法殊途同归了。2.2 动态规划按轮次统计方案数DFS 是站在“某一条路径”的角度一步步走完再判断动态规划则是站在“轮次”的角度直接统计第 i 轮到达每个节点的方案数。定义状态dp[i][j]表示“经过 i 轮传递到达节点 j 的方案数”。初始化是dp[0][0] 1因为第 0 轮信息只在起点 0 号手里。状态转移也很自然如果有一条边u - v那么所有能在第 i-1 轮到达 u 的方案都可以在第 i 轮走到 v所以dp[i][v] dp[i-1][u]。把第一维的轮次滚动掉可以优化成一维数组这是面试里很常见的滚动数组技巧。from typing import List class Solution: def numWays(self, n: int, relation: List[List[int]], k: int) - int: dp [0] * n dp[0] 1 for _ in range(k): nxt [0] * n for u, v in relation: nxt[v] dp[u] dp nxt return dp[n - 1]这段代码极其简洁但我建议你千万不要只是背下来一定要亲手把第一层循环展开一遍。我们拿官方示例来演算。初始dp [1, 0, 0, 0, 0]表示第 0 轮只有 0 号有信息方案数为 1。第 1 轮遍历所有边后边 0-2 让dp[2]加 1边 0-4 让dp[4]加 1所以第 1 轮的dp [0, 0, 1, 0, 1]意思是经过 1 轮到达 2 号有 1 种方案到达 4 号有 1 种方案。第 2 轮2-1 让dp[1]加 12-3 让dp[3]加 12-0 让dp[0]加 1这一轮dp [1, 1, 0, 1, 0]。注意这里没有从 4 号出发的边所以上一轮到达 4 号的 1 种方案在这里就断掉了。第 3 轮0-2 让dp[2]加 1这个 1 来自上一轮dp[0] 10-4 让dp[4]加 1同样来自上一轮dp[0] 11-4 让dp[4]加 1来自上一轮dp[1] 13-4 让dp[4]加 1来自上一轮dp[3] 1最后dp[4] 1 1 1 3和题目答案一致。你发现没有动态规划的做法本质上是在“数路”每一轮只是把所有边的可能性累加一遍完全不关心具体路径长什么样。这种做法的时间复杂度是 O(k × E)E 是关系表的长度比 DFS 的 O(n^k) 稳定得多而且不需要递归空间只有 O(n)是三种解法里我最推荐优先掌握的。2.3 矩阵快速幂邻接矩阵的 k 次方接下来是这篇文章的重头戏也是“邻接矩阵练习”这个标题真正的灵魂所在。在组合数学里有一个非常漂亮的结论对于一个有向图的邻接矩阵 A矩阵的 k 次幂A^k中A^k[i][j]的值就是从节点 i 出发经过恰好 k 步到达节点 j 的路径总数。为什么我们从矩阵乘法本身看。A^2[i][j] sum(A[i][t] * A[t][j] for t in range(n))。A[i][t] 1表示 i 到 t 有一条边A[t][j] 1表示 t 到 j 有一条边两者相乘等于 1等价于“i - t - j”构成一条长度为 2 的路径。把所有中间节点 t 的情况加起来就是 i 到 j 的长度为 2 的路径总数。把这个过程重复 k 次就能得到长度为 k 的路径数。所以 LCP 07 的答案直接就是A^k[0][n-1]。三步走的方案数是 A² 的功劳五步就把矩阵自己乘五次。这种思路不仅漂亮而且直接揭示了这道题和线性代数的联系。矩阵快速幂的完整实现如下from typing import List class Solution: def numWays(self, n: int, relation: List[List[int]], k: int) - int: # 构建邻接矩阵 A [[0] * n for _ in range(n)] for u, v in relation: A[u][v] 1 # 矩阵乘法 def mat_mul(X, Y): size len(X) Z [[0] * size for _ in range(size)] for i in range(size): for j in range(size): for t in range(size): Z[i][j] X[i][t] * Y[t][j] return Z # 矩阵快速幂 def mat_pow(mat, power): size len(mat) # 单位矩阵 res [[0] * size for _ in range(size)] for i in range(size): res[i][i] 1 base mat while power 0: if power 1: res mat_mul(res, base) base mat_mul(base, base) power 1 return res result mat_pow(A, k) return result[0][n - 1]注意这里res初始化为单位矩阵逻辑和整数快速幂里的ans 1完全一致。k如果是 0mat_pow直接返回单位矩阵result[0][n-1]在 n1 时是 0这也是合理的信息不传递就不可能从 0 到达 n-1。矩阵快速幂的时间复杂度是 O(n³ log k)听起来比 DP 的 O(kE) 慢但它的扩展性极强——如果 n 固定在 10 以内log k 的幂次计算远比你想象的快如果题目改成 k 达到 10^9DP 就无能为力了而矩阵快速幂依然能轻松应对。这就是为什么我想让你掌握它的原因。3. Python 构建邻接矩阵的细节与完整实现3.1 先学会正确建图别被浅拷贝坑了Python 里构建邻接矩阵的常规姿势很简单n 5 matrix [[0] * n for _ in range(n)] for u, v in relation: matrix[u][v] 1但是这里有一个几乎所有 Python 新手都会踩的坑不要用[[0] * n] * n来创建二维数组。很多第一次写的人觉得这样很简洁结果发现改了matrix[0][2] 1之后matrix[1][2]、matrix[2][2]全都变成了 1整个矩阵乱成一团。原因在于 Python 的列表乘法[0] * n生成的是值对象列表没问题但外层再乘 n 时复制的不是内容而是同一个行对象的引用。也就是说[[0] * n] * n创建了 n 个指向同一个列表的引用你修改任意一行其他行跟着全变。我建议你可以在本地随便试一下打印出来看看踩过一次这个坑以后就再也不会犯了。正确写法有两种。第一种是列表推导式matrix [[0] * n for _ in range(n)]第二种是显式循环matrix [] for _ in range(n): matrix.append([0] * n)两种效果一样推荐第一种简洁且没有引用陷阱。然后是关于重边的处理。虽然题目给的 relation 从语义上看应该没有重复边但你写代码的时候最好养成 1而不是 1的习惯for u, v in relation: matrix[u][v] 1因为如果同一对(u, v)出现了两次说明存在两条不同的传递边方案数应该翻倍。用 1会直接把前一条边覆盖掉导致答案变小。这道题不考这个点但换一道题可能就是你的失分点。再补充一个建模细节。LCP 07 是“无权有向图”所以邻接矩阵存 0/1 就行。如果你以后做带权图比如“从 i 到 j 花的费用是 c”就把matrix[i][j] c最短路径类的问题经常会用到这种写法。3.2 完整可运行的工程代码学习阶段我建议你把三种解法放在同一个脚本里方便对比验证。下面是一份完整的可运行代码包含 DFS、DP、矩阵快速幂以及一个简单的测试例子from typing import List class Solution: def numWays_dfs(self, n: int, relation: List[List[int]], k: int) - int: graph [[] for _ in range(n)] for u, v in relation: graph[u].append(v) ans 0 def dfs(node: int, step: int): nonlocal ans if step k: if node n - 1: ans 1 return for nxt in graph[node]: dfs(nxt, step 1) dfs(0, 0) return ans def numWays_dp(self, n: int, relation: List[List[int]], k: int) - int: dp [0] * n dp[0] 1 for _ in range(k): nxt [0] * n for u, v in relation: nxt[v] dp[u] dp nxt return dp[n - 1] def numWays_matrix(self, n: int, relation: List[List[int]], k: int) - int: A [[0] * n for _ in range(n)] for u, v in relation: A[u][v] 1 def mat_mul(X, Y): size len(X) Z [[0] * size for _ in range(size)] for i in range(size): for j in range(size): for t in range(size): Z[i][j] X[i][t] * Y[t][j] return Z def mat_pow(mat, power): size len(mat) res [[0] * size for _ in range(size)] for i in range(size): res[i][i] 1 base mat while power: if power 1: res mat_mul(res, base) base mat_mul(base, base) power 1 return res result mat_pow(A, k) return result[0][n - 1] if __name__ __main__: sol Solution() n 5 relation [[0, 2], [2, 1], [3, 4], [2, 3], [1, 4], [2, 0], [0, 4]] k 3 print(DFS:, sol.numWays_dfs(n, relation, k)) print(DP:, sol.numWays_dp(n, relation, k)) print(Matrix:, sol.numWays_matrix(n, relation, k))这段代码三种解法的输出应该都是 3。建议你跑完以后把第二个示例n3, relation[[0,2],[2,1]], k2也放进去试一下答案应该是 0。3.3 三种实现的核心差异对照我把三种解法的特点整理成一张表方便你对比记忆解法核心思路时间复杂度空间复杂度代码复杂度适用场景DFS递归枚举路径步数到 k 判断终点O(n^k) 最坏O(k n²)低n 和 k 都很小的题动态规划按轮次累加方案数O(k × E)O(n)低需要快速求方案数n 较大矩阵快速幂邻接矩阵 A^k 的路径计数含义O(n³ log k)O(n²)中k 很大或需要复用矩阵幂实际做题时DP 往往是性价比最高、最推荐直接写的解法。但如果你是为了学习图论和矩阵之间的关系矩阵快速幂那一版值得反复咀嚼。4. 边界条件与常见坑4.1 边界情况要提前想清楚写算法题最怕的不是主流程逻辑复杂而是边界条件没处理好。LCP 07 我整理了一下需要留意的边界情况主要有四个。第一k 0。理论上信息不传递只有起点 0 落在终点 n-1 时才可能有 1 种方案但题目设定 n 至少为 20 号不是 n-1 号所以答案是 0。正常写代码不用特殊处理但如果哪天你拿来改成别的题记得想想这点。第二relation为空。也就是说一张关系表都没有无论 k 是几方案数都为 0。DFS 解法里这个情况自然返回 0DP 解法里因为遍历边的循环不执行dp[n-1]也保持 0都安全。第三信息到达了死胡同。比如某条路径走到一个没有任何出边的节点但步数还没到 k这整条路径就宣告作废。DP 解法不需要关心这种情况因为累加过程自然会断掉DFS 解法中for 循环里没有邻居那就直接 return逻辑也是正确的。第四路径不能停在终点之前。有些读者会想优化一个剪枝如果 node 已经是 n-1 但 step 还没到 k是不是可以直接 return这里要小心。题目说的是“恰好 k 轮”不是“一旦到达终点就结束”。如果你在 node 是 n-1 但步数不够的情况下直接返回会漏掉“到达终点之后再传出去最后又绕回终点”的那些路径比如示例里的 0 - 2 - 0 - 4 就是这样第二轮信息已经不在 4 号但第三轮又从 0 传到 4。所以在 DFS 里千万不要在提前到达终点时中断递归。4.2 我练习时踩过的三个真实的坑第一个坑是浅拷贝。这个我在前面已经反复强调过[[0] * n] * n看起来人畜无害实际上一改全改。我印象很深刻第一次写完矩阵快速幂版本跑出来答案不对劲打印矩阵后发现所有行都一样排查了好久才意识到是创建方式的问题。从此我只要看到二维数组第一反应就是列表推导式。第二个坑是遗忘重边。有的题目关系表里不会出现完全相同的[u, v]两条边但也有的题会。如果在构建邻接矩阵时用 1覆盖而不是 1可能丢失计数最终答案少算。我后来给自己定了一条规矩凡是用矩阵做路径计数一律用累加宁可多写一个字符也不赌题目没重边。第三个坑是 DFS 里把“至少 k 步”和“恰好 k 步”搞混。如果我在一步到达终点时多加一个剪枝看起来“高效”了实际上会直接改变语义。比如示例里第二条路径 0 - 2 - 3 - 4如果我在 0 - 2 之后看到节点 2 不是终点就继续递归这没问题但假设有一条 0 - 4 的边而 k 2我绝不能因为第一轮已经到达 4 就把它当作成功路径。正确做法是必须等到 step k 那一刻再判断。这个语义问题最容易在面试紧张时出错。5. 拿到这类题怎么想邻接矩阵背后是一套通法5.1 什么时候用邻接矩阵什么时候用邻接表很多读者会把邻接矩阵和邻接表当成两种并列的选择纠结半天。我一般建议从两个维度判断。第一个维度是节点数量 n。n 在 200 以内邻接矩阵随便用因为矩阵需要 n² 的空间200² 40000完全没压力n 到 10⁵ 级别矩阵就变成 10¹⁰ 个元素直接内存爆炸只能用邻接表或者边列表。第二个维度是题目问法。如果题目问的是“从 i 到 j 是否存在长度为 k 的路径”“长度为 k 的路径条数”邻接矩阵的幂运算就是天然的数学工具如果题目问的是“从起点出发找一条可行路径并输出路径本身”DFS/BFS 邻接表更直观因为你不需要遍历矩阵中大量的 0。简单总结成一张决策表场景n 很小n 很大问路径数问具体路径邻接矩阵首选不适用强烈推荐不太方便邻接表也可以首选需要 DP 辅助首选LCP 07 的n最大只有 10所以 Adjacency Matrix 练习的定位非常精准你可以在完全不吃力的情况下把矩阵建好、用好、看得清清楚楚。5.2 从这道题延伸出去的三个方向当你理解了A^k[i][j]的含义之后很多问题都能归约到矩阵运算上这是这道题带给我最大的启发。第一个延伸方向是“不超过 k 步”的变体。如果题目改成“最多经过 k 轮到达终点”处理起来稍微绕一点但有一个很巧妙的技巧给每个节点加一条指向自己的自环。这样一来信息可以在任意一轮“留在原地”那么“不超过 k 步到达终点”就等价于“恰好 k 步到达终点”——因为多余的轮数都可以通过自环消耗掉。当然要注意如果原图本身就有自环语义需要小心别算重了。第二个延伸方向是 Floyd-Warshall 算法。它看起来是在做“动态规划求全源最短路”但本质上运行在邻接矩阵之上只是把矩阵乘法中的“乘法”替换成“加法”、“加法”替换成“取最小值”这就是所谓的广义矩阵乘法。你如果已经对 LCP 07 的矩阵快速幂非常熟悉再看 Floyd 就会有一种“原来都是同一套东西”的恍然大悟感。第三个延伸方向是路径可达性问题。判断两个节点之间是否存在任意长度的路径可以计算A A² A³ ... A^(n-1)看对应位置是否非零。这背后其实对应着图的传递闭包。虽然工程上通常用 BFS/DFS 做可达性判断矩阵方法在数学推导和理论分析里依然很有价值。再分享一点我个人的做题体会我当时练这道题的时候最有收获的一刻不是把答案跑出来而是把 DP 数组逐轮打印出来看着数字一行一行滚到终点。那一刻我才真正明白“状态转移”不是一句空话它就是在模拟信息逐轮流动的过程。后来再看邻接矩阵的幂次发现A^k[0][n-1]居然能把三条路径全部算出来我忍不住反复检查了两遍确认代码没写错那一刻确实有种“图论的大门被推开了一角”的感觉。如果你是从零开始做这道题我建议按这条路径走先手动把示例的 DP 过程推一遍然后写 DFS 版本再写 DP 版本最后再上矩阵快速幂。如果你想偷懒只写一个版本那一定是 DP 版本——它又好写又好理解复杂度也最优。但如果你想认真把“邻接矩阵”这四个字刻进脑子里请一定花时间看懂矩阵快速幂那一版哪怕只是跑通、打印结果、把三条路径在矩阵乘法里自己手算一遍这个功夫绝对值得。