1129. 颜色交替的最短路径

题目描述

在一个有向图中，节点编号从 0 到 n - 1。

图中每条边要么是红色，要么是蓝色。

给你两个数组：

redEdges，其中 redEdges[i] = [ai, bi] 表示有一条从 ai 到 bi 的红色有向边
blueEdges，其中 blueEdges[i] = [ui, vi] 表示有一条从 ui 到 vi 的蓝色有向边

请你返回一个长度为 n 的数组 answer，其中：

answer[x] 表示从节点 0 到节点 x 的最短路径长度
并且这条路径上的边颜色必须 交替出现
如果不存在这样的路径，则 answer[x] = -1

示例 1

text

输入：n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
输出：[0,1,-1]

示例 2

text

输入：n = 3, redEdges = [0,1](<0,1.md>), blueEdges = [2,1](<2,1.md>)
输出：[0,1,-1]

约束

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= ai, bi, ui, vi < n

核心思路

这题一眼看上去像普通最短路，但比普通最短路多了一个限制：

路径上的边颜色必须交替

所以这题的关键不是只记录“到某个节点最短要几步”，而是还要记录：

到这个节点时，上一条边是什么颜色

因为：

如果你是通过红边到达当前节点的
那下一步就只能走蓝边

反过来：

如果你是通过蓝边到达当前节点的
那下一步就只能走红边

所以这题的状态应该是：

text

(当前节点, 上一条边颜色)

只要状态里带上颜色，这题就又回到了：

无权图最短路
最少步数

因此最自然的做法依然是：

BFS

这题至少有两种常见做法：

解法一：BFS + 扩展状态 (node, color)（推荐）
解法二：分层 BFS + 邻接表分类存边

这两种本质上都属于 BFS，只是实现组织方式略有不同。

先理解：为什么不能只访问“节点”本身？

假设有这样一个点：

你第一次通过红边到达它
第二次通过蓝边到达它

虽然“节点编号”一样，但这两种状态的意义不同：

红边到达后，下一步只能接蓝边
蓝边到达后，下一步只能接红边

所以：

(node, red)
(node, blue)

必须看成两个不同状态。

这也是这题最容易想错的地方。

解法一：BFS + 扩展状态 `(node, color)`

这是这题最标准、最推荐掌握的做法。

思路拆解

我们先分别建两张邻接表：

redGraph[node]：从这个点出发的所有红边终点
blueGraph[node]：从这个点出发的所有蓝边终点

然后做 BFS。

队列中的状态写成：

text

(node, color, distance)

其中：

node：当前所在节点
color：上一条边的颜色
distance：从 0 到这里的步数

这样从当前状态扩展时：

如果上一条边是红色，那下一步只能走蓝边
如果上一条边是蓝色，那下一步只能走红边

对于起点 0，因为它还没走过任何边，所以我们可以把它当成两种起点同时入队：

(0, red)
(0, blue)

意思是：

假装“上一步是红”，下一步就能走蓝
假装“上一步是蓝”，下一步就能走红

这样可以统一处理起点逻辑。

一步一步写出算法

第一步：建图

const redGraph: number[][] = Array.from({ length: n }, () => [])
const blueGraph: number[][] = Array.from({ length: n }, () => [])

for (const [from, to] of redEdges) {
    redGraph[from].push(to)
}
for (const [from, to] of blueEdges) {
    blueGraph[from].push(to)
}

第二步：定义答案数组

一开始都记成 -1，表示暂时不可达。

const answer = new Array(n).fill(-1)
answer[0] = 0

第三步：定义颜色状态

我们可以约定：

0 表示红色
1 表示蓝色

然后访问标记用：

visited[node][color]

表示：

是否已经以“上一条边颜色为 color”的状态访问过这个节点

第四步：初始化队列

const queue: [number, number, number][] = [
    [0, 0, 0],
    [0, 1, 0],
]

分别表示：

当前在 0，上一条边看作红色，距离是 0
当前在 0，上一条边看作蓝色，距离是 0

第五步：从当前状态扩展“相反颜色”的边

如果上一条边颜色是红：

下一步走蓝边

如果上一条边颜色是蓝：

下一步走红边

const nextColor = 1 - color
const nextNodes = nextColor === 0 ? redGraph[node] : blueGraph[node]

第六步：更新答案

某个节点第一次被到达时，当前步数一定是最短的。

所以：

if (answer[nextNode] === -1) {
    answer[nextNode] = distance + 1
}

代码实现（TypeScript）

function shortestAlternatingPaths(
    n: number,
    redEdges: number[][],
    blueEdges: number[][],
): number[] {
    const redGraph: number[][] = Array.from({ length: n }, () => [])
    const blueGraph: number[][] = Array.from({ length: n }, () => [])

    for (const [from, to] of redEdges) {
        redGraph[from].push(to)
    }
    for (const [from, to] of blueEdges) {
        blueGraph[from].push(to)
    }

    const answer = new Array(n).fill(-1)
    answer[0] = 0

    const visited = Array.from({ length: n }, () => [false, false])
    visited[0][0] = true
    visited[0][1] = true

    const queue: [number, number, number][] = [
        [0, 0, 0],
        [0, 1, 0],
    ]

    while (queue.length > 0) {
        const [node, color, distance] = queue.shift()!
        const nextColor = 1 - color
        const nextNodes = nextColor === 0 ? redGraph[node] : blueGraph[node]

        for (const nextNode of nextNodes) {
            if (visited[nextNode][nextColor]) {
                continue
            }

            visited[nextNode][nextColor] = true
            if (answer[nextNode] === -1) {
                answer[nextNode] = distance + 1
            }
            queue.push([nextNode, nextColor, distance + 1])
        }
    }

    return answer
}

复杂度分析

时间复杂度：O(n + redEdges.length + blueEdges.length)
空间复杂度：O(n + redEdges.length + blueEdges.length)

因为每个状态 (node, color) 最多访问一次。

这一解法的优缺点

优点：

思路标准
容易看清“状态里必须带颜色”
是这题最推荐的解法

缺点：

需要先接受“同一个节点可以被访问两次”的思想

解法二：分层 BFS + 邻接表分类存边

这个做法本质还是 BFS，只是更强调“按层推进”。

思路拆解

我们也可以不用在队列里显式存 distance，而是：

每轮 BFS 处理一整层状态
当前层结束后，步数 step++

同时队列里的状态只存：

text

(node, color)

意思依然是：

当前在 node
上一条边颜色是 color

这一层扩展完后，所有新加入的状态都属于下一层。

这样同样能得到最短距离。

一步一步写出算法

第一步：建图

和第一种做法一样，分别建红边和蓝边邻接表。

第二步：初始化队列

还是把起点作为两种颜色状态一起入队：

const queue: [number, number][] = [
    [0, 0],
    [0, 1],
]

第三步：分层处理

每轮处理当前队列长度个状态：

let step = 0
while (queue.length > 0) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
        ...
    }
    step++
}

第四步：更新答案

如果某个节点第一次出现在某层里，那这一层的 step 就是它的最短交替路径长度。

代码实现（TypeScript）

function shortestAlternatingPaths(
    n: number,
    redEdges: number[][],
    blueEdges: number[][],
): number[] {
    const graph = Array.from({ length: n }, () => [[], []] as number[][])

    for (const [from, to] of redEdges) {
        graph[from][0].push(to)
    }
    for (const [from, to] of blueEdges) {
        graph[from][1].push(to)
    }

    const answer = new Array(n).fill(-1)
    answer[0] = 0

    const visited = Array.from({ length: n }, () => [false, false])
    visited[0][0] = true
    visited[0][1] = true

    const queue: [number, number][] = [
        [0, 0],
        [0, 1],
    ]

    let step = 0

    while (queue.length > 0) {
        const size = queue.length

        for (let i = 0; i < size; i++) {
            const [node, color] = queue.shift()!
            const nextColor = 1 - color

            for (const nextNode of graph[node][nextColor]) {
                if (visited[nextNode][nextColor]) {
                    continue
                }

                visited[nextNode][nextColor] = true
                if (answer[nextNode] === -1) {
                    answer[nextNode] = step + 1
                }
                queue.push([nextNode, nextColor])
            }
        }

        step++
    }

    return answer
}

复杂度分析

时间复杂度：O(n + redEdges.length + blueEdges.length)
空间复杂度：O(n + redEdges.length + blueEdges.length)

和第一种写法本质相同。

这一解法的优缺点

优点：

层数概念更强
更贴近 BFS “一层一层扩展”的原始写法

缺点：

本质没有比第一种更简单
只是写法风格不同

两种解法对比

解法	时间复杂度	空间复杂度	特点
BFS + `(node, color, distance)`	`O(n + m)`	`O(n + m)`	状态最直观，最推荐
分层 BFS + `(node, color)`	`O(n + m)`	`O(n + m)`	更突出层次感

这里的 m 表示红边数和蓝边数之和。

如果你是第一次做这题，建议优先写第一种状态更完整的版本。

手动模拟一遍

以：

text

n = 3
redEdges = [[0,1],[1,2]]
blueEdges = []

为例。

起点

从 0 出发，答案数组初始：

text

[0, -1, -1]

第一步

从 0 出发，可以走红边到：

text

所以：

text

answer[1] = 1

现在到达 1 的最后一条边是红色。

第二步

接下来如果还想继续走，必须走蓝边。

但图里没有蓝边。

所以无法继续走到 2。

最终答案就是：

text

[0, 1, -1]

这正好对应题目示例。

面试时最容易错的点

1. 同一个节点要按“颜色状态”分别访问

不能只写：

visited[node]

而应该写：

visited[node][color]

因为到达同一个节点时，如果最后一条边颜色不同，后续可走的边也不同。

2. 起点要视作两种颜色状态都能出发

这是一个很常见的小技巧。

否则你会在第一步到底能走红边还是蓝边上写出很多特殊判断。

3. 这题是无权图最短路，优先想到 BFS

不是 DFS，也不是 Dijkstra。

4. 路径必须是“边颜色交替”，不是“节点颜色交替”

这里交替的是边的颜色。

不要理解错对象。

一句话总结

这题的本质是：

在无权图最短路中，把“上一条边颜色”也纳入状态。

想写标准解：用 BFS + (node, color) 状态
想更强调层次感：用 分层 BFS

1129. 颜色交替的最短路径

题目描述

示例 1

示例 2

约束

核心思路

先理解：为什么不能只访问“节点”本身？

解法一：BFS + 扩展状态 (node, color)

思路拆解

一步一步写出算法

第一步：建图

第二步：定义答案数组

第三步：定义颜色状态

第四步：初始化队列

第五步：从当前状态扩展“相反颜色”的边

第六步：更新答案

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：分层 BFS + 邻接表分类存边

思路拆解

一步一步写出算法

第一步：建图

第二步：初始化队列

第三步：分层处理

第四步：更新答案

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍

起点

第一步

第二步

面试时最容易错的点

1. 同一个节点要按“颜色状态”分别访问

2. 起点要视作两种颜色状态都能出发

3. 这题是无权图最短路，优先想到 BFS

4. 路径必须是“边颜色交替”，不是“节点颜色交替”

一句话总结

推荐你最后记住的标准写法

解法一：BFS + 扩展状态 `(node, color)`