What is the best algorithm for solving the Shortest Path with Alternating Colors problem?

The best approach is to use Breadth-First Search (BFS), where each state represents a node and the last edge color used. This ensures the path alternates between red and blue edges.

How can I optimize the space complexity of the solution?

You can optimize space usage by carefully managing the adjacency lists and using a single queue to store BFS states while maintaining only two distance arrays for each edge color.

What are common mistakes when implementing BFS for alternating edge colors?

Common mistakes include not alternating between red and blue edges properly, mishandling edge cases like no valid paths, and incorrectly transitioning between node states in BFS.

Can this problem be solved using Depth-First Search (DFS)?

DFS is not ideal for this problem because it may not efficiently handle the alternating edge constraint. BFS is better suited for finding the shortest path with alternating colors.

What is the time complexity of solving this problem?

The time complexity is O(n + E), where n is the number of nodes and E is the total number of edges (red and blue). This is due to the BFS traversal that processes each node and edge at most once.

#1129

Medium

auto_awesome图·搜索

LeetCode 题解工作台

颜色交替的最短路径

给定一个整数 n ，即有向图中的节点数，其中节点标记为 0 到 n - 1 。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。给定两个数组 redEdges 和 blueEdges ，其中： redEdges[i] = [a i , b i ] 表示图中存在一条从节点 a i 到节点 b i…

广度优先搜索图

题目描述

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

redEdges[i] = [a_i, b_i] 表示图中存在一条从节点 a_i 到节点 b_i 的红色有向边，
blueEdges[j] = [u_j, v_j] 表示图中存在一条从节点 u_j 到节点 v_j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

提示：

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= a_i, b_i, u_j, v_j < n

lightbulb

解题思路

方法一：BFS

题目实际上是最短路问题，我们可以考虑使用 BFS 来解决。

首先，我们对所有的边进行预处理，将所有的边按照颜色分类，存储到多维数组 $g$ 中。其中 $g[0]$ 存储所有红色边，而 $g[1]$ 存储所有蓝色边。

接着，我们定义以下数据结构或变量：

队列 $q$ ：用来存储当前搜索到的节点，以及当前边的颜色；
集合 $vis$ ：用来存储已经搜索过的节点，以及当前边的颜色；
变量 $d$ ：用来表示当前搜索的层数，即当前搜索到的节点到起点的距离；
数组 $ans$ ：用来存储每个节点到起点的最短距离。初始时，我们将 $ans$ 数组中的所有元素初始化为 $-1$ ，表示所有节点到起点的距离都未知。

我们首先将起点 $0$ 和起点边的颜色 $0$ 或 $1$ 入队，表示从起点出发，且当前是红色或蓝色边。

接下来，我们开始进行 BFS 搜索。我们每次从队列中取出一个节点 $(i, c)$ ，如果当前节点的答案还未更新，则将当前节点的答案更新为当前层数 $d$ ，即 $ans[i] = d$ 。然后，我们将当前边的颜色 $c$ 取反，即如果当前边为红色，则将其变为蓝色，反之亦然。我们取出颜色对应的所有边，如果边的另一端节点 $j$ 未被搜索过，则将其入队。

搜索结束后，返回答案数组即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别为节点数和边数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class 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 = set()
        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
                vis.add((i, c))
                c ^= 1
                for j in g[c][i]:
                    if (j, c) not in vis:
                        q.append((j, c))
            d += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate understanding of BFS and how it applies to graph traversal with color alternation.
question_mark
Look for clarity in representing the problem as a graph and alternating edge colors during BFS.
question_mark
Candidates should be able to efficiently manage the BFS state transitions between red and blue edges.

warning

常见陷阱

外企场景

error
Not alternating between red and blue edges properly, causing incorrect paths or infinite loops.
error
Not handling the case where no valid path exists, leading to incorrect answers.
error
Mismanaging the state transitions between nodes and edge colors during BFS, causing missed nodes or incorrect distances.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to find paths with a specific number of alternating edges.
arrow_right_alt
Modify the graph to include weighted edges and ask for the shortest path with alternating edge colors.
arrow_right_alt
Allow multiple starting nodes and find the shortest alternating path from each starting point.

help

常见问题

外企场景

继续练习

#1203 项目管理 #1042 不邻接植花 #1298 你能从盒子里获得的最大糖果数