LeetCode 1129题为何无法找到最短路径？我的DFS代码问题在哪？

我在解决LeetCode 1129题「最短交替颜色路径」时遇到了问题：给定有向图的红色边数组redEdges和蓝色边数组blueEdges，需要返回从节点0到各节点的最短交替颜色路径长度，不存在则返回-1。

我编写了DFS实现的代码，但针对输入：
redEdges=[[2,2],[0,1],[0,3],[0,0],[0,4],[2,1],[2,0],[1,4],[3,4]]
blueEdges=[[1,3],[0,0],[0,3],[4,2],[1,0]]

我的输出是[0,1,4,1,1]，而正确输出应为[0,1,2,1,1]——存在路径0→4（红边）→2（蓝边），但我的DFS未找到该路径。

我的代码如下：

from collections import defaultdict
from typing import List

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:

        res = [0] + [-1]*(n-1)

        Red = defaultdict(list)
        Blue = defaultdict(list)

        for x,y in redEdges:
            if x!=0 or y!=0: 
                Red[x].append(y)

        for x,y in blueEdges:
            if x!=0 or y!=0:
                Blue[x].append(y)


        def dfs(vertex,color,cost):
        
            if color == "red":
                for x in Red[vertex]:
                    if res[x] != -1:
                        res[x] = min(cost,res[x])
                    else:
                        res[x] = cost

                    if vertex in Red.keys():
                        del Red[vertex]
                    dfs(x,"blue",cost+1)


            else:
                for x in Blue[vertex]:
                    if res[x] != -1:
                        res[x] = min(cost,res[x])
                    else:
                        res[x] = cost

                    if vertex in Blue.keys():
                        del Blue[vertex]
                    dfs(x,"red",cost+1)

        dfs(0,"red",1)
        dfs(0,"blue",1)

        return res

错误原因分析 #

1. 错误删除邻接表中的顶点条目 #

在DFS遍历过程中，处理完某个顶点的一条边后立即删除该顶点在邻接表中的所有条目（del Red[vertex]或del Blue[vertex]），这会导致两个关键问题：

• 同一个顶点的多条边只能被处理第一条，后续边直接被跳过。比如Red[0]包含[1,3,4]，第一次循环处理x=1后就删除了Red[0]，剩下的3和4完全没有被遍历，这就是0→4路径没被发现的核心原因。
• 后续若有其他路径回到该顶点，无法再访问该顶点的同色边，导致可能的短路径被忽略。

2. DFS天然不适合最短路径问题 #

DFS是深度优先遍历，会优先探索深度更大的路径，可能先给节点设置较长的路径长度，即使后续发现更短路径，也可能因为邻接表已被破坏而无法到达。这类最短路径问题更适合用BFS，因为BFS按层级遍历，第一次到达节点时的路径就是最短路径。

3. 冗余的边过滤逻辑 #

代码中过滤了x=0且y=0的边，虽然这类边对结果无影响（节点0的初始距离已设为0），但属于不必要的冗余操作，不过这不是导致当前错误的直接原因。

修复建议 #

1. 删除邻接表删除操作：去掉del Red[vertex]和del Blue[vertex]两行代码，确保所有边都能被遍历到。
2. 添加访问状态记录：由于图中可能存在环，需要记录每个节点在使用某颜色边到达时的访问状态，避免无限递归。比如使用二维数组visited[vertex][color]（0代表红，1代表蓝）标记是否已以该颜色到达过该节点。
3. 改用BFS实现：如果追求正确性和效率，推荐用BFS实现，它能保证第一次到达节点时的路径是最短的。

内容的提问来源于stack exchange，提问作者Mateusz Orzeł