AlgoNote 算法通关手册：0913 猫和老鼠（Cat and Mouse）博弈论与拓扑排序解法深度解析-平芜编程栈

教程
文档
知识库

【免费下载链接】AlgoNote

⛽️「算法通关手册」：从零开始的「算法与数据结构」学习教程，200 道「算法面试热门题目」，1000+ 道「LeetCode 题目解析」，持续更新中！

项目地址：https://gitcode.com/gh_mirrors/le/AlgoNote

导读

本文围绕《算法通关手册》题库中的困难题 0913. 猫和老鼠展开，完整讲解"猫鼠博弈"这一经典零和博弈 + 图论综合题的题面建模、状态设计，以及如何用逆向思维 + 拓扑排序在 $O(n^3)$ 时间内判定在双方均采用最优策略时的胜负结果。读完本文，你将掌握一套可迁移的"从终局状态反推初始状态"的博弈求解框架，并能在 LeetCode 上直接运行给出的 Python 实现，同时理解它与仓库中 Kahn 拓扑排序、DFS 拓扑排序的底层联系。

一、题目总览：猫和老鼠的无向图追逐游戏

1.1 题目大意

两位玩家分别扮演猫和老鼠，在一张无向图上进行追逐游戏，两人轮流行动：

图以邻接表形式给出，graph[a]是由所有满足「$ab$ 是一条边」的节点 $b$ 组成的列表；
老鼠从节点1出发并先手行动，猫从节点2出发后手行动，节点0是老鼠的洞；
每个玩家每次行动必须沿一条边移动到相邻节点（如老鼠在节点 1，就必须移动到graph[1]中的某个节点）；
特殊限制：猫不能进入洞（节点 0）。

游戏在以下三种情形之一出现时结束：

猫与老鼠出现在同一节点→ 猫获胜；
老鼠到达洞（节点 0）→ 老鼠获胜；
某一位置重复出现（玩家的位置与移动顺序和上一次行动完全相同）→ 平局。

要求：在双方都采取最优策略的前提下，返回游戏结果——老鼠获胜返回1，猫获胜返回2，平局返回0。

1.2 数据范围

$3 \le graph.length \le 50$（节点数 $n$ 至多 50）；
$1 \le graph[i].length < graph.length$（每个节点至少有一条出边，游戏总能进行）；
$0 \le graph[i][j] < graph.length$，且 $graph[i][j] \ne i$（无自环）；
各节点的邻接列表互不相同。

1.3 示例

示例 1

输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] 输出：0

猫和老鼠在这张图上各自有多个策略分支，双方都可以通过最优走法回避对方的"必胜陷阱"，最终进入重复局面，判定为平局。

示例 2

输入：graph = [[1,3],[0],[3],[0,2]] 输出：1

此时老鼠可以凭借更优的走位率先抵达节点 0（洞），从而获得胜利。

提示：示例配图为官方题面示意图，重点在于理解邻接表结构与"洞 0 / 起点 1 / 起点 2"的位置关系，本仓库文档仅以文本方式复述，读者可直接在力扣题面查看原图。

二、解题思路：博弈论 + 拓扑排序

2.1 为什么不能直接模拟

猫鼠双方轮流行动、目标相互对立，属于典型的零和博弈。若直接按"当前局面谁优"进行贪心或暴力搜索，会陷入两个困难：

状态空间大：$mouse \in [0, n)$、$cat \in [0, n)$、行动方 $turn \in {1, 2}$，共 $2n^2$ 个状态；
存在平局（循环）：某些状态既不是任何一方的必胜态，也不会通向终结局面，而是会陷入重复循环。

因此需要一种能够同时处理"必胜 / 必败 / 平局"三类结果的确定性算法——**逆向拓扑排序（Retrograde Analysis）**恰好满足需求。

2.2 状态与结果定义

定义三元组状态：

$(mouse, cat, turn)$：老鼠在节点 $mouse$，猫在节点 $cat$，当前轮到 $turn$ 行动（$1$ 表示老鼠，$2$ 表示猫）。

状态结果取值：

$0$：平局（DRAW）；
$1$：老鼠获胜（MOUSE_WIN）；
$2$：猫获胜（CAT_WIN）。

2.3 逆向思维：从终局反推初始状态

与正向模拟不同，拓扑排序解法从已知结果的终结状态出发，反向推导前驱状态。其正确性依据是博弈论的经典递推规则：

若某一状态存在一个后继状态对当前行动方有利，则当前状态对当前行动方有利（当前玩家会主动选择这条最优路线）；
若某一状态的所有后继状态都对对手有利（即对当前行动方全部不利），则当前状态对当前行动方不利。

具体分三步：

初始化终结状态：
- 老鼠到达洞口（$mouse = 0$）→ 老鼠获胜，结果置为1；
- 猫抓到老鼠（$mouse = cat$，且 $cat \ne 0$）→ 猫获胜，结果置为2。
按"逆拓扑序"传播结果：从已知结果的状态出队，考察所有可能的前驱状态。前驱状态若存在通往"己方获胜"的后继，直接判胜；否则将其剩余"未定后继数"（出度）减一，当出度归零时说明所有后继都对己方不利，判负。
返回初始状态结果：$(1, 2, 1)$，即老鼠在 1、猫在 2、老鼠先手时的最终胜负值。

这一"从终局反推"的技巧在仓库 06_05_graph_topological_sorting.md 讲解的拓扑排序思想上一脉相承——只不过经典拓扑排序通过"入度归零"确定依赖顺序，这里通过"出度归零"确定所有分支均不利的必败状态。

三、完整代码实现

3.1 Python 实现（可直接提交）

class Solution: def catMouseGame(self, graph: List[List[int]]) -> int: n = len(graph) DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2 # 状态：(mouse, cat, turn)，turn=1 表示老鼠，turn=2 表示猫 # 结果：0=平局，1=老鼠赢，2=猫赢 result = [[[DRAW] * 3 for _ in range(n)] for _ in range(n)] degree = [[[0] * 3 for _ in range(n)] for _ in range(n)] # 计算每个状态的出度（后继状态数） for mouse in range(n): for cat in range(n): degree[mouse][cat][1] = len(graph[mouse]) # 猫不能移动到洞（节点 0），因此出度要去掉 0 degree[mouse][cat][2] = len([node for node in graph[cat] if node != 0]) # 初始化队列：已知结果的状态 from collections import deque queue = deque() for cat in range(n): for turn in [1, 2]: # 老鼠到达洞口，老鼠赢 result[0][cat][turn] = MOUSE_WIN queue.append((0, cat, turn)) # 猫抓到老鼠（但猫不能在洞口），猫赢 if cat > 0: result[cat][cat][turn] = CAT_WIN queue.append((cat, cat, turn)) # 拓扑排序（逆向传播） while queue: mouse, cat, turn = queue.popleft() current_result = result[mouse][cat][turn] if turn == 1: # 当前是老鼠的回合，推导上一步猫的状态 for prev_cat in graph[cat]: if prev_cat == 0: # 猫不能进洞 continue if result[mouse][prev_cat][2] != DRAW: continue if current_result == CAT_WIN: # 如果老鼠这步后猫赢，说明猫的上一步可以导致猫赢 result[mouse][prev_cat][2] = CAT_WIN queue.append((mouse, prev_cat, 2)) else: # 否则，减少出度 degree[mouse][prev_cat][2] -= 1 if degree[mouse][prev_cat][2] == 0: # 所有后继状态都对猫不利，猫输 result[mouse][prev_cat][2] = MOUSE_WIN queue.append((mouse, prev_cat, 2)) else: # 当前是猫的回合，推导上一步老鼠的状态 for prev_mouse in graph[mouse]: if result[prev_mouse][cat][1] != DRAW: continue if current_result == MOUSE_WIN: # 如果猫这步后老鼠赢，说明老鼠的上一步可以导致老鼠赢 result[prev_mouse][cat][1] = MOUSE_WIN queue.append((prev_mouse, cat, 1)) else: # 否则，减少出度 degree[prev_mouse][cat][1] -= 1 if degree[prev_mouse][cat][1] == 0: # 所有后继状态都对老鼠不利，老鼠输 result[prev_mouse][cat][1] = CAT_WIN queue.append((prev_mouse, cat, 1)) return result[1][2][1]

3.2 关键实现细节逐行解读

出度计算（第 14～18 行）：$turn=1$（老鼠回合）的出度是len(graph[mouse])；$turn=2$（猫回合）的出度必须过滤掉节点 0，因为猫不能进洞，这与题面约束严格对应。
终结状态初始化（第 23～31 行）：对任意 $cat$ 与任意 $turn$，$(0, cat, turn)$ 都是老鼠必胜；$(cat, cat, turn)$（$cat>0$ 时）都是猫必胜。它们作为拓扑排序的"源点"入队。
回合反向传播（第 33～62 行）：
- 当前结果对上一步行动方不利时（如当前老鼠回合得到CAT_WIN，说明猫的上一步 $(mouse, prev_cat, 2)$ 存在一个导致猫赢的后继），直接给前驱状态判胜；
- 否则将前驱状态的degree减一，代表"这个前驱状态的一个后继分支已确定对己方不利"，当degree归零时，说明其所有后继都对己方不利，从而判定前驱状态必败。
返回初始局面：result[1][2][1]即"老鼠在 1、猫在 2、老鼠先手"的最终结果。

3.3 复杂度分析

时间复杂度：$O(n^3)$，其中 $n$ 是图中节点数（$n \le 50$）。每个状态至多入队一次，每次出队需要遍历前驱边，总边数为 $O(n^2)$ 量级，状态总数为 $O(n^2)$，综合为 $O(n^3)$。
空间复杂度：$O(n^2)$，需要存储全部状态的result与degree数组（各为 $n \times n \times 3$）。

在 $n=50$ 的规模下，$O(n^3)$ 完全可接受，这也是该解法能在力扣通过全部测试用例的原因。

四、与仓库源码的联动：拓扑排序在 AlgoNote 中的完整脉络

4.1 算法分类归属

在《算法通关手册》的分类体系中，本题被归入图、拓扑排序、记忆化搜索、数学、动态规划、博弈复合标签，可见于 00_06_categories_list.md 的题解总表；同时被收录进 00_05_solutions_list.md 的完整题解清单。

4.2 底层的拓扑排序实现对照

本解法本质上是在博弈状态图上做逆向拓扑排序，其队列驱动的核心结构与仓库中 Graph-Topological-Sorting-Kahn.py 一脉相承：

Kahn 算法维护indegrees（入度）字典，将入度为 0 的节点入队，出队时将其所有后继节点的入度减一，入度归零者继续入队，直至队列为空；若最终拓扑序列长度不等于节点总数，则说明图中存在环。
本题的逆向版本则维护degree（剩余未定后继数），将结果已定的终结状态入队，出队时将其前驱状态的剩余后继数减一，归零者判定为必败并入队。

可以对照观察：

# 来自 codes/python/06_graph/Graph-Topological-Sorting-Kahn.py while S: u = S.pop() # 从集合中选择一个没有前驱的顶点 order.append(u) # 将其输出到拓扑序列 order 中 for v in graph[u]: # 遍历顶点 u 的邻接顶点 v indegrees[v] -= 1 # 删除从顶点 u 出发的有向边 if indegrees[v] == 0: # 如果删除该边后顶点 v 的入度变为 0 S.append(v) # 将其放入集合 S 中

同样的"度归零 → 入队 → 扩散"模式，前者用于判断有向无环图中的依赖顺序，后者用于在博弈状态图中扩散必胜 / 必败结论。仓库还提供 DFS 版本 Graph-Topological-Sorting-DFS.py，可作为理解"拓扑序两种实现方式"的补充阅读材料。

4.3 从题库到手册的延伸学习

本题的逆向博弈思想与以下仓库资源相互印证，适合按序进阶：

06_05_graph_topological_sorting.md：拓扑排序完整理论（Kahn 与 DFS 两种实现、环检测、典型应用）；
07_04_backtracking_algorithm.md：博弈类问题另一常用手段——带记忆化搜索的回溯（配合turn轮换与结果缓存，可处理较小规模的类似博弈题）；
题库中的其他"两人最优博弈"类题目（如 0292 Nim 游戏、0486 预测赢家等）可分别从 nims 相关文档与 predict-the-winner.md 入手对照练习。