如果你最近在补图论的基础题大概率会在 LeetCode 上刷到 LCP 07 这道题题目名很直白叫“传递信息”。名字听着像脑筋急转弯骨子里考的却是非常实在的东西邻接矩阵的构建以及在一个有向无权图上统计“恰好 k 步”的路径方案数。我刷这题时第一次认真把“python 构建邻接矩阵”这件小事单独拎了出来因为后边的 DFS、BFS、动态规划甚至矩阵快速幂套路全都建立在你能把图正确装进数据结构里这件事上。这道题的难度标记只是“简单”但它能把一整套图论基础操作串起来。对刚入门图论的人来说它可以用来练邻接表和邻接矩阵对准备面试的人来说它又能引出路径计数和 DP 状态设计哪怕你已经在刷中等题了顺手用矩阵快速幂再过一遍这题也会有一种“原来如此”的通透感。这篇文章我就按自己实际刷题时的思路把它从题目拆解讲到矩阵快速幂每一步都给出能直接跑的代码和踩过的坑。1. 题目拆解传递信息到底在求什么1.1 题目里的图和路径到底长什么样先描述一下题目本身。有 n 个玩家编号是 0 到 n-1。信息从 0 号玩家出发沿着给定的有向关系传递要求恰好经过 k 轮传递后到达 n-1 号玩家。输入里给了一个 relation 数组数组里每个元素是[a, b]表示信息可以从 a 传给 b。举个例子我自己刷题时常用这个小图来验证n 3 relation [[0, 1], [1, 2], [0, 2], [2, 2]] k 2这里一共有 3 个玩家信息要从 0 传到 2恰好走 2 步。肉眼数一下有两条路径路径一0 - 1 - 2路径二0 - 2 - 2注意路径二里玩家 2 在第二步又传给了自己只要题目允许这条边存在它就构成一个合法方案。所以输出应该是 2。把例子抽象成图论语言就一句话给定 n 个点和 m 条有向边求从节点 0 出发经过恰好 k 条边到达节点 n-1 的不同路径条数。1.2 “恰好 k 步”这三个字有多关键很多同学第一次做这题代码写出来总觉得哪里不对主要就是因为没把“恰好 k 步”咬死。如果把题目理解成“最多 k 步能到就行”那递归里就得额外维护“当前步数是否小于等于 k”并且一旦到达终点就要累加答案最后的结果会明显偏大。可题目要的是走完 k 步后站在终点中间哪怕第 3 步就到了 n-1只要 k 是 5你就还得继续从 n-1 往外走直到第 5 步结束才算一种方案。这里就引出一个很多人会忽略的细节如果终点存在自环也就是 relation 里有[n-1, n-1]这条边那么信息到达终点后还能反复自传传满 k 步后停在终点这些路径也是有效路径。这个逻辑很自然顺着题面走就行但平时做图论题习惯了“到终点就停”的思维你可能会在代码里提前 break导致漏解。1.3 三个容易让人“想当然”的误区第一这不是最短路问题。最短路关心的是步数最少这题关心的是恰好 k 步的方案数。所以 BFS 里常见的“第一次访问就标记 visited”的做法直接失效后面细说。第二路径允许重复经过同一个玩家。信息可以在一群人里来回传比如 0 - 1 - 0 - 2只要步数合适就是合法路径。因此 DFS 不能用一个全局 visited 数组去重去重会让答案变少。第三路线图是有向的。relation 里[a, b]只表示 a 能传给 b不代表 b 能传回 a。构建邻接矩阵或邻接表时别顺手把反向边也加上这是初学者最容易犯的错。把这三点想清楚后面所有解法都是在同一个语义下做计数不会再出现答案对不上样例的问题。2. 先用邻接矩阵把图立起来2.1 邻接矩阵到底是什么邻接矩阵是表示图最直观的方式之一。假设有 n 个节点就准备一个 n 行 n 列的矩阵 MM[i][j]表示从 i 到 j 是否存在有向边。存在就是 1不存在就是 0。用一个生活化类比把 n 个玩家排成一张点名表行表示“谁在说话”列表示“谁在听”。第 i 行第 j 列如果打了勾就说明 i 能把消息传给 j。比如 1.1 里的例子n 3矩阵长这样j0 j1 j2 i0 0 1 1 i1 0 0 1 i2 0 0 1因为边里有0-1、0-2、1-2、2-2所以对应位置是 1其余是 0。矩阵里对角线上是 1 的情况只有自环比如这里的2-2。2.2 Python 构建邻接矩阵两种可靠写法与一个巨坑在 Python 里构建邻接矩阵最推荐的写法是嵌套列表推导式def build_adjacency_matrix(n, edges): matrix [[0] * n for _ in range(n)] for a, b in edges: matrix[a][b] 1 return matrix这代码看起来稀松平常但那个[[0] * n for _ in range(n)]是有讲究的。新手特别容易写成[[0] * n] * n然后发现改matrix[0][1] 1的时候每一行的第 1 列都变成了 1。原因很简单[[0] * n] * n是先创建一个长度为 n 的列表再用乘法复制了 n 次引用实际指向的是同一个内存对象。你改的是“同一行”不是“某一行的副本”。我最早踩这个坑时 debug 了很久打印矩阵发现整整齐齐全是 1还以为是赋值逻辑写错了。如果你更习惯用邻接表那构建起来更快def build_adjacency_list(n, edges): graph [[] for _ in range(n)] for a, b in edges: graph[a].append(b) return graph两条边以上的场景邻接表会更省空间但如果后面要做矩阵乘法就必须用邻接矩阵。这道题两种都能用不过既然标题是“邻接矩阵练习”我更建议你两种都写一遍感受一下不同的遍历方式。2.3 邻接矩阵和邻接表怎么选很多读者可能刚接触图论我把这两个结构放在一起对比一下对比维度邻接矩阵邻接表空间占用O(n^2)n 大时浪费严重O(n m)边少时更省查询 u 到 v 是否有边O(1)O(出度)遍历 u 的所有出边需要扫一整行O(n)直接拿到列表O(出度)是否适合矩阵幂运算非常合适不适合代码出错风险构建时容易踩共享引用坑相对直接在这道题里 n 很小用邻接矩阵几乎零成本。但如果 n 到了几千甚至几万邻接矩阵就是灾难因为光存储就要 n^2 个格子。所以我一般建议不需要矩阵运算的题默认用邻接表需要在矩阵上做推导或乘方才用邻接矩阵。这也是面试里常见的选型考察点。3. DFS 与 BFS先把暴力解跑通3.1 DFS一条路走到底回头再数DFS 的思路非常朴素从 0 出发递归地尝试每一条边每走一步步数加一等步数等于 k 时判断当前站在哪个节点上。def numWays_dfs(n, relation, k): graph build_adjacency_list(n, relation) def dfs(node, step): if step k: return 1 if node n - 1 else 0 ans 0 for nxt in graph[node]: ans dfs(nxt, step 1) return ans return dfs(0, 0)这里有个容易写错的小细节判断条件的顺序。必须在step k时立刻返回而不是先遍历邻居再判断。如果你写成“先走下一步再判断”会导致方案数翻倍因为每个节点在最后一步会继续向外扩散。用之前的例子走一遍从 0 开始第一步去 1第二步去 2计数 1第一步去 2因为节点 2 有自环第二步还在 2计数 1。总共 2 种和手算一致。DFS 的时间复杂度是 O(出度^k)指数级但题目里 k 很小完全跑得动。作为“练习邻接矩阵”的入门这个暴力的价值在于你能非常直观地看到路径是怎么一条一条长出来的。3.2 BFS按轮次把路径铺开BFS 做这道题思路更像模拟信息传递。用一个队列存储“当前轮次站在哪些节点”每一轮把队列里所有节点往外扩散一轮扩散完 k 轮后队列里每个节点就是一条路径的终点。def numWays_bfs(n, relation, k): graph build_adjacency_list(n, relation) queue [0] for _ in range(k): nxt [] for node in queue: nxt.extend(graph[node]) queue nxt return queue.count(n - 1)这个解法最反直觉的地方在于队列里会出现重复节点而且这是正确行为。比如第 2 轮时节点 2 可能通过 0-1-2 和 0-2-2 两条路径到达那么队列里就应该有两个 2。到第 3 轮时这两个 2 都会继续向外走产生的路径是不同方案不能合并更不能去重。BFS 的时间复杂度和 DFS 一样是 O(出度^k)只是实现上从递归换成了迭代。对初学者来说BFS 版本更容易和“轮次”这个概念对上也更容易理解“计数路径”和“找最短路径”的区别。3.3 为什么这道题不能套 visited 去重这是我在评论区见过最多的疑问。平时做 BFS 最短路比如“求从 0 到 n-1 最少要传几轮”必须用 visited 数组避免重复访问因为最短路径只要确定“第一次到达就是最优”即可。但这里统计的是“所有恰好 k 步的路径”同一时刻站在同一个节点可能来自完全不同的路径前缀。举例第 2 轮站在节点 2可能是从 0 - 1 - 2 来的也可能是从 0 - 2 - 2 来的。到第 3 轮时前者继续走出的路径和后者继续走出的路径是两条不同的完整路径如果提前合并成一个节点路径信息就丢失了。这个点想通了你就真正理解了“计数”和“可达性”的区别。DFS 同理不能加 visited 回溯限制因为路径允许重复经过同一个人。4. 动态规划从“枚举路径”到“统计数量”4.1 状态设计思路暴力枚举能跑通但效率太低。观察 BFS 的过程你会发现同一层里有很多重复节点而我们真正关心的并不是“谁在第几层出现”而是“第几层时每个节点被到达过多少次”。只要次数统计正确就能推出下一层。于是 DP 状态可以这样定义dp[t][j]表示经过 t 轮传递后到达玩家 j 的方案数。初始化时dp[0][0] 1因为第 0 轮信息还在 0 号手里。转移时遍历每条边[a, b]所有到 a 的方案都能继续传到 bdp[t][b] dp[t-1][a]答案就是dp[k][n-1]。4.2 滚动数组实现与复杂度由于每一轮只依赖上一轮可以只用两个长度为 n 的数组滚动更新省掉二维 DP 的空间def numWays_dp(n, relation, k): dp [0] * n dp[0] 1 for _ in range(k): ndp [0] * n for a, b in relation: ndp[b] dp[a] dp ndp return dp[n - 1]用这个代码跑前面的例子初始dp [1, 0, 0]第 1 轮边 0-1 让 dp[1] 1边 0-2 让 dp[2] 1边 2-2 由于 dp[2] 此时是 0不加。得到 [0, 1, 1]第 2 轮1-2 让 ndp[2] 10-2 由于 dp[0] 是 0 不加2-2 让 ndp[2] 1。最终 dp[2] 2和 DFS、BFS 结果一致。时间复杂度 O(k * m)空间 O(n)。在题目约束下已经非常快。如果你用邻接矩阵来写 DP可以按节点遍历def numWays_dp_matrix(n, relation, k): matrix build_adjacency_matrix(n, relation) dp [0] * n dp[0] 1 for _ in range(k): ndp [0] * n for i in range(n): if dp[i]: for j in range(n): if matrix[i][j]: ndp[j] dp[i] dp ndp return dp[n - 1]这种写法多了一层 n 循环适合练习邻接矩阵用边列表直接转移则更高效。两种都写一遍体会“图的存储结构决定遍历方式”这句话。4.3 DP 和邻接矩阵的隐藏关系如果你把dp[t]看成一个长度为 n 的行向量那么它的转移过程其实就是行向量右乘邻接矩阵dp[t] dp[t-1] × M展开单看一个元素dp[t][j] sum(dp[t-1][i] * M[i][j])正好是“上一轮所有能到 i 的方案数乘上 i 到 j 的边是否存在再累加”。这一步很关键。它把 DP 和矩阵乘法联系到了一起既然每轮都是乘一次 M那 k 轮之后就是dp[k] dp[0] × M^k答案自然等于(M^k)[0][n-1]。这就是下一节矩阵快速幂的入口。5. 矩阵快速幂把 k 步路径变成矩阵乘方5.1 矩阵乘法的路径计数原理先单独看矩阵乘法的公式。设 C A × B那么C[i][j] A[i][0]*B[0][j] A[i][1]*B[1][j] ... A[i][n-1]*B[n-1][j]如果 A 和 B 都表示路径方案数A[i][k] 表示从 i 到 k 走若干步的方案数B[k][j] 表示从 k 到 j 走若干步的方案数那乘积 C[i][j] 就是把所有中间节点 k 的方案数相乘再累加正好是从 i 到 j 经过两步的方案数。这个性质对“恰好 k 步”来说极其契合。M 本身是走 1 步的方案数矩阵那 M^2 就是走 2 步M^3 就是走 3 步M^k 就是走 k 步。用前面的例子验证一下M [[0, 1, 1], [0, 0, 1], [0, 0, 1]]计算 M^2 的第 0 行第 2 列M[0][0]*M[0][2] M[0][1]*M[1][2] M[0][2]*M[2][2] 0*1 1*1 1*1 2结果等于 2和之前手算一致。这才是邻接矩阵最漂亮的地方矩阵乘方就是在数路径。5.2 代码实现与方向问题矩阵快速幂借用整数快速幂的思路把 k 拆成二进制。比如 k 5二进制是 101也就是 M^5 M^4 × M^1。我们只需要不断把矩阵平方遇到二进制位为 1 时乘进结果。先写矩阵乘法。n 很小直接三层循环稍微优化一下可以在 A[i][k] 为 0 时跳过省掉最内层循环def mat_mul(A, B): n len(A) C [[0] * n for _ in range(n)] for i in range(n): for k in range(n): if A[i][k]: for j in range(n): C[i][j] A[i][k] * B[k][j] return C再写快速幂。注意 res 初始化为单位矩阵 E单位矩阵表示“走 0 步”任何矩阵乘上它都保持不变。它的对角线全 1其他位置全 0def mat_pow(mat, power): n len(mat) res [[1 if i j else 0 for j in range(n)] for i in range(n)] base mat while power 0: if power 1: res mat_mul(res, base) base mat_mul(base, base) power 1 return res最后组合起来def numWays_matrix(n, relation, k): matrix build_adjacency_matrix(n, relation) if k 0: return 1 if n 1 else 0 result mat_pow(matrix, k) return result[0][n - 1]这里有一个容易混乱的方向问题。我们用的是“行向量右乘矩阵”的约定也就是dp[t] dp[t-1] * M所以答案直接取(M^k)[0][n-1]。如果你习惯用列向量状态转移会变成dp[t] M^T * dp[t-1]那就得对矩阵先转置再乘方。两种约定都能算出正确答案但代码里一定要统一别写着写着混用结果就是天书错误。另外一点矩阵乘法的乘法顺序很重要。快速幂里res mat_mul(res, base)代表res res * base。因为矩阵乘法一般不满足交换律如果写成base * res结果可能不同。虽然这里 base 始终是同一个矩阵的不同幂次和 res 之间的顺序在数学上恰好可以交换但在更复杂的工程场景里保持统一写法是基本素养。5.3 什么时候必须用它在 LCP 07 的原题约束里n 和 k 都是个位数级别DP 已经秒出结果矩阵快速幂属于典型的“高射炮打蚊子”。但你要知道如果 k 从 5 变成 1e9DP 的 O(k * m) 就直接废了只有矩阵快速幂能在 O(n^3 log k) 内搞定。更重要的是这个能力能直接迁移到其他场景比如随机游走问题图上的马尔可夫链求 k 步后落在各点的概率图的连通性判断M^k 的非零位置表示 k 步内是否可达递推优化很多线性递推式都可以写成矩阵乘法然后用快速幂加速所以我一直觉得哪怕这题用不上也应该把矩阵快速幂模板练熟。它是一个有门槛、但一旦跨过去就能一劳永逸的知识点。6. 现场排坑记录与快速自查表6.1 我在实际刷题时遇到的四个典型错误先说自己真实踩过的坑。第一次写这题时我用的是邻接表 BFS并且加上了 visited 去重。样例跑得飞快结果一交发现答案少了。当时完全没意识到路径计数不允许合并节点后来手动模拟了一遍 0-1-2 和 0-2-2 两条路径才明白队列里重复节点是信息的一部分不是冗余。第二个坑是构建邻接矩阵时的共享引用问题。前面已经说过[[0] * n] * n会复制引用我当时在笔记本上调试改一个位置整行都变心态差点崩了。从那以后我写二维矩阵只认[[0] * n for _ in range(n)]。第三个坑是 DFS 的返回位置。最早我把if step k的判断放在了遍历邻居之后导致最后一步节点还会继续展开下一层方案数越数越多。这种 bug 不报错但结果就是不对特别恶心。后来我给自己定了一条规则凡是“到达指定步数必须停止”的递归先写终止条件再写枚举逻辑。第四个坑是矩阵快速幂的边界。我第一次用矩阵快速幂解这题忘了 k 0 的情况。如果 k 为 0表示不传递信息只在 0 号手里只有在 n 1 时才满足“到达 n-1”也就是玩家 0 同时是终点。不加这个特判快速幂循环不执行res 是单位矩阵单位矩阵[0][n-1]当 n 1 时是 0看似没问题但 n 1 时答案应该是 1单位矩阵[0][0]恰好是 1其实也能蒙对。不过逻辑上还是应该显式处理否则代码经不起变式题追问。6.2 现场排查速查表症状可能原因解决办法答案比预期小用了 visited 去重删除 visited路径计数允许重复节点答案比预期大最终步数判断写错确保进入递归先检查 step k矩阵所有行一起变用[[0]*n]*n构建矩阵改用[[0]*n for _ in range(n)]矩阵快速幂结果不对行向量和列向量约定混用统一约定答案位置保持对应漏掉 k 0 场景没考虑不传信息的情况显式特判再进入快速幂边方向写反把有向边当成无向边处理只赋值matrix[a][b]别顺手matrix[b][a]这套速查表其实也能迁移到其他图论路径计数题。每次写完代码先跑一个自己口算过的微型样例再检查边界值基本能过滤掉九成低级错误。6.3 一个很多人没注意的细节自环对答案的影响再补一个容易被忽略的边界场景。如果 relation 里存在[n-1, n-1]也就是终点可以自己传给自己那么路径到终点后还能继续走。比如 n 2relation [[0, 1], [1, 1]]k 3到达 1 的路径有0 - 1 - 1 - 1没有第二条因为 0 没有其他边答案是 1。但如果再加一条[0, 1]之外的路径比如[0, 1]重复出现两次方案数还会变化。这个细节在刷题时不太常见但在系统设计类的概率传递题目里经常作为隐藏条件出现提前理解能帮你少走很多弯路。我个人刷完这道题最大的收获不是背会了几个模板而是看懂了“计数”和“寻路”是两种完全不同的目标。寻路可以剪枝、去重、贪心计数则需要忠实地展开每一种可能。邻接矩阵、DP、矩阵快速幂本质上都是在用不同的姿势做同一件事把路径的组合关系算清楚。如果你也正卡在图论入门我建议你从这道题开始把 DFS、BFS、DP、矩阵快速幂四种写法全部手写一遍。写完之后你会发现后面遇到“概率传播”“多步可达性”这类的变体题思路会通畅很多。