企业官网建设流程全解析

如果你最近在补图论的基础题，大概率会在 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 列的矩阵 M，M[i][j]表示从 i 到 j 是否存在有向边。存在就是 1，不存在就是 0。

用一个生活化类比：把 n 个玩家排成一张点名表，行表示“谁在说话”，列表示“谁在听”。第 i 行第 j 列如果打了勾，就说明 i 能把消息传给 j。

比如 1.1 里的例子，n = 3，矩阵长这样：

j=0 j=1 j=2 i=0 0 1 1 i=1 0 0 1 i=2 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 邻接矩阵和邻接表怎么选

很多读者可能刚接触图论，我把这两个结构放在一起对比一下：

在这道题里 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 的方案都能继续传到 b：

dp[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] += 1，0->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，其他位置全 0：

def 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 变成 1e9，DP 的 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 现场排查速查表

这套速查表其实也能迁移到其他图论路径计数题。每次写完代码，先跑一个自己口算过的微型样例，再检查边界值，基本能过滤掉九成低级错误。

6.3 一个很多人没注意的细节：自环对答案的影响

再补一个容易被忽略的边界场景。如果 relation 里存在[n-1, n-1]，也就是终点可以自己传给自己，那么路径到终点后还能继续走。比如 n = 2，relation =[[0, 1], [1, 1]]，k = 3，到达 1 的路径有：

• 0 -> 1 -> 1 -> 1
• 没有第二条，因为 0 没有其他边

答案是 1。但如果再加一条[0, 1]之外的路径，比如[0, 1]重复出现两次，方案数还会变化。这个细节在刷题时不太常见，但在系统设计类的概率传递题目里经常作为隐藏条件出现，提前理解能帮你少走很多弯路。

我个人刷完这道题最大的收获，不是背会了几个模板，而是看懂了“计数”和“寻路”是两种完全不同的目标。寻路可以剪枝、去重、贪心；计数则需要忠实地展开每一种可能。邻接矩阵、DP、矩阵快速幂，本质上都是在用不同的姿势做同一件事：把路径的组合关系算清楚。如果你也正卡在图论入门，我建议你从这道题开始，把 DFS、BFS、DP、矩阵快速幂四种写法全部手写一遍。写完之后你会发现，后面遇到“概率传播”“多步可达性”这类的变体题，思路会通畅很多。