题目描述
思路解析动画文字版
记牢一句话:状态带上颜色,每走一步翻一次色,第一次够到一个点的层数就是它的最短交替路径长度。
总览 · 一张红蓝混色的有向图：先把图看懂。五个圆圈是节点 0 到 4,箭头是有向边,每条边旁边标了颜色:红或蓝。题目要的是从节点 0 出发,走一条红蓝交替的路,也就是这一步红、下一步必须蓝,再下一步又得红,这样交替着走,问到每个点最少要几步。走不到的记成 -1。先把答案亮出来,最后会是 0、1、1、2、-1,其中 4 号谁也送不到。下面一步步把它跑出来。
起点 · 给 0 号两个开局：这里有个关键设计:我们记的状态不是单纯「在哪个点」,而是「在哪个点,上一步走的是什么颜色」,因为下一步颜色由它决定。0 号是起点还没走过边,为了红蓝两种开局都能展开,就放两个起点状态进队列:一个当作刚用红边到的 0 号,下一步就该走蓝;一个当作刚用蓝边到的 0 号,下一步走红。当前层数 d 记为 0。注意一个细节:这两个起点状态放进队列的同一刻,就一并记进了已访问,所以右边已访问那栏现在已经列着「0号·红」「0号·蓝」两条;入队就标记,是为了同一个状态绝不会被重复入队。
出队 · 节点0·红到：从队头取出状态「0号·红到」,它是这一层 d=0 的。0 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 0,这就是最短交替路径长度,记 answer[0] = 0。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
翻色 · (0号,红) 出队展开：「0号·红到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 0 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 红 边,按交替规矩,下一步只能走 蓝 边,于是去看从 0 号出发的 蓝 色边有哪些。
沿 蓝 边 0→2 · 入队即标记：从 0 号顺着这条 蓝 色边走到 2 号。状态「2号·蓝到」之前没访问过,就在放进队列的同一刻把它记进已访问,右边已访问那栏立刻多出这一条,排到队尾等下一层 d=1 再处理。入队就标记,哪怕图里有平行边,同一个状态也只会入队一次。2 号先点亮成待探索。继续看 0 号还有没有别的 蓝 边。
出队 · 节点0·蓝到：取出「0号·蓝到」。0 号在更早的层里已经拿到过答案 0 了,后到的只会更长,所以这里不更新它的答案,只把这个状态当作继续往外扩的跳板。
翻色 · (0号,蓝) 出队展开：「0号·蓝到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 0 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 蓝 边,按交替规矩,下一步只能走 红 边,于是去看从 0 号出发的 红 色边有哪些。
沿 红 边 0→1 · 入队即标记：从 0 号顺着这条 红 色边走到 1 号。状态「1号·红到」之前没访问过,就在放进队列的同一刻把它记进已访问,右边已访问那栏立刻多出这一条,排到队尾等下一层 d=1 再处理。入队就标记,哪怕图里有平行边,同一个状态也只会入队一次。1 号先点亮成待探索。继续看 0 号还有没有别的 红 边。
出队 · 节点2·蓝到：从队头取出状态「2号·蓝到」,它是这一层 d=1 的。2 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 1,这就是最短交替路径长度,记 answer[2] = 1。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
翻色 · (2号,蓝) 出队展开：「2号·蓝到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 2 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 蓝 边,按交替规矩,下一步只能走 红 边,于是去看从 2 号出发的 红 色边有哪些。
沿 红 边 2→3 · 入队即标记：从 2 号顺着这条 红 色边走到 3 号。状态「3号·红到」之前没访问过,就在放进队列的同一刻把它记进已访问,右边已访问那栏立刻多出这一条,排到队尾等下一层 d=2 再处理。入队就标记,哪怕图里有平行边,同一个状态也只会入队一次。3 号先点亮成待探索。继续看 2 号还有没有别的 红 边。
出队 · 节点1·红到：从队头取出状态「1号·红到」,它是这一层 d=1 的。1 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 1,这就是最短交替路径长度,记 answer[1] = 1。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
翻色 · (1号,红) 出队展开：「1号·红到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 1 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 红 边,按交替规矩,下一步只能走 蓝 边,于是去看从 1 号出发的 蓝 色边有哪些。
1号 没有 蓝 色出边：从 1 号出发,蓝 色的边一条也没有。交替的链子在这里断了,这个状态没法再往外送任何新点,1 号这一支到此为止。回到队列继续处理别的状态。
出队 · 节点3·红到：从队头取出状态「3号·红到」,它是这一层 d=2 的。3 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 2,这就是最短交替路径长度,记 answer[3] = 2。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
翻色 · (3号,红) 出队展开：「3号·红到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 3 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 红 边,按交替规矩,下一步只能走 蓝 边,于是去看从 3 号出发的 蓝 色边有哪些。
3号 没有 蓝 色出边：从 3 号出发,蓝 色的边一条也没有。交替的链子在这里断了,这个状态没法再往外送任何新点,3 号这一支到此为止。回到队列继续处理别的状态。
为什么 4 号是 -1：队列空了,可 4 号始终没拿到答案。看清原因:唯一能进 4 号的是蓝边 2→4,要走这条蓝边,就得先「用红边到达 2 号」,这样下一步才轮到蓝。可整趟里,2 号只被「蓝色到」过,从没被「红色到」过。所以红色到 2 这个状态压根没出现,蓝边 2→4 永远迈不出去。
两层记账的胜负手：顺带说清 visited 为什么按节点加颜色两层记,先纠一个误读:4 号是 -1,根子在状态自带的到达颜色。正因为状态带着颜色,我们才确认 2 号只蓝到、没红到,蓝边 2→4 的前一步红色到 2 没出现,4 号才到不了,这跟去重怎么记无关。两层记账真正的用武之地是另一张图:某个点既被红色到、又得以蓝色到的身份再进一次队,才能够到后面的点;只按节点去重就会把这第二次当重复挡掉,把那些点冤枉成不可达。本节没触发这种重进队的情形,但记法照两层来,换张图就靠它兜底。
完成 · 对照答案：全部跑完,答案凑齐:0 号 0 步,1 号和 2 号各 1 步,3 号 2 步,4 号到不了记 -1。回放一下 3 号怎么来的:0 号先走蓝边到 2 号(第 1 步),再从 2 号走红边到 3 号(第 2 步),红蓝交替成立,正好 2 步。整道题一句话:状态带上颜色做 BFS,每步翻色,第一次够到就是最短。
边界都靠交替这把尺子:连两条同色边断链;起点答案恒为 0;够不到就老实记 -1。
面试重点:两层访问区分「红到」「蓝到」两种续走可能;BFS 按层扩散,第一次够到即最短。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def shortestAlternatingPaths( self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]] ) -> List[int]: g = [defaultdict(list), defaultdict(list)] for i, j in redEdges: g[0][i].append(j) for i, j in blueEdges: g[1][i].append(j) ans = [-1] * n vis = {(0, 0), (0, 1)} # 起点两个状态先标记已访问 q = deque([(0, 0), (0, 1)]) d = 0 while q: for _ in range(len(q)): i, c = q.popleft() if ans[i] == -1: ans[i] = d c ^= 1 for j in g[c][i]: if (j, c) not in vis: vis.add((j, c)) # 先标记 q.append((j, c)) # 再入队:同一状态只入队一次 d += 1 return ans复杂度
- 时间：O(n + m)，n 是节点数,m 是红蓝边总数。状态总共最多 2n 个(每个点配红、蓝两种到达颜色),因为入队前就打上已访问标记,每个状态只入队、出队各一次;每条边在它对应颜色那侧也只被走一次,合计线性
- 空间：O(n + m)，两张邻接表存全部边是 O(n + m);因为入队前先去重,队列和已访问集合最多装下全部 2n 个状态,是 O(n);answer 数组 O(n)。按峰值算整体 O(n + m)
易错点
面试追问把动画讲成自己的话
追问已访问为什么必须按(节点,颜色)两层记,只记节点会怎样?
追问为什么第一次用 BFS 够到某个点,就一定是最短的?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
交换字符串中的元素
LeetCode 1202 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题