LeetCode 1059 全路径必须终止于终点用三色标记 DFS 判断有向图路径收敛性【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读All Paths from Source Lead to DestinationLeetCode 1059是一道考验有向图路径收敛性与环检测的经典面试题给定有向图、起点source与终点destination需要判断「从起点出发的每一条路径是否都能最终终止于终点」。本文以 DFS 三色标记white/gray/black为核心给出完整算法推演、9 种主流语言的仓库级实现、复杂度证明与常见陷阱对照帮你同时掌握「DFS 环检测」与「叶子节点收束判断」两大图论技能。本文对应的完整题解文档位于 articles/all-paths-from-source-lead-to-destination.md读者可对照阅读。一、前置知识Prerequisites在动手解这道题之前建议先熟练掌握以下三项基本功它们也是本仓库大量图论题解如 course-schedule.md、valid-tree.md、redundant-connection.md反复使用的核心技能图的表示Graph Representation能够根据边列表edges构建邻接表adjacency list并完成建图与遍历深度优先搜索DFS递归式图遍历与回溯backtracking能理解递归栈在遍历过程中的推进与回退环检测Cycle Detection使用三色标记法white / gray / black在有向图中识别回边back edge这是本解法的灵魂所在。小提示有向图的环检测与无向图不同。无向图中一条「跨边」即可定义环参见 valid-tree.md 的 parent 参数技巧而有向图必须区分「当前递归路径中的节点」与「已完成遍历的节点」这正是三色标记的价值。二、问题定义与解题直觉2.1 问题本质题目要求验证两个条件从source出发的每一条路径都必须最终到达destination图中不能存在环——否则某些路径将无限循环永远无法终止于终点。换句话说destination必须是图中唯一的「合法终点」它是一个没有任何出边outgoing edge的叶子节点且所有从source可达的路径都收敛到它。2.2 直觉DFS 一把梭一次带环检测的 DFS 可以同时完成上述两项验证遍历过程中若再次遇到当前递归路径上的节点即 gray 节点说明存在回边 → 有环 → 返回false遇到叶子节点无出边时它必然是一条路径的终点因此它必须恰好等于destination否则返回false若某条路径中途走到了「死胡同」却并非终点同样返回false。2.3 三色标记法Three-Color MarkingDFS 过程中为每个节点维护三种状态颜色含义说明White未访问节点尚未被处理在实现中用null/0等「初始值」代替Gray正在处理节点在当前 DFS 递归路径上其子孙尚未完全探索一旦遇到 gray 节点即发现回边 → 环Black处理完毕节点及其所有子孙都已完全探索结果已知且安全再次遇到 black 节点可直接复用结果记忆化关键区别再次访问 black 节点是合法的说明存在另一条路径汇入已确认安全的子图而再次访问 gray 节点则意味着环。普通 visited 集合无法区分这两种情况这正是三色标记存在的意义。三、算法步骤根据n和edges构建邻接表graph初始化states数组长度n每个节点初始为未访问null/0即 white从source开始运行 DFS若节点状态已非 white返回states[node] BLACKgray 时返回false表示有环black 时返回true复用结果若节点是叶子graph[node]为空返回node destination将节点标记为gray递归访问所有邻居一旦某个邻居返回false立即短路返回false全部邻居确认安全后将节点标记为black返回true返回dfs(source)的结果。四、多语言实现仓库级完整代码以下实现直接取自题解文档覆盖 9 种语言方便在不同技术栈下对照理解。所有实现共享同一套算法骨架null/0代表 whiteGRAY代表正在处理BLACK代表已安全。4.1 Pythonclass Solution: # We dont use the state WHITE as such anywhere. Instead, the null value in the states array below is a substitute for WHITE. GRAY 1 BLACK 2 def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) - bool: graph self.buildDigraph(n, edges) return self.leadsToDest(graph, source, destination, [None] * n) def leadsToDest(self, graph, node, dest, states): # If the state is GRAY, this is a backward edge and hence, it creates a Loop. if states[node] ! None: return states[node] Solution.BLACK # If this is a leaf node, it should be equal to the destination. if len(graph[node]) 0: return node dest # Now, we are processing this node. So we mark it as GRAY. states[node] Solution.GRAY for next_node in graph[node]: # If we get a false from any recursive call on the neighbors, we short circuit and return from there. if not self.leadsToDest(graph, next_node, dest, states): return False # Recursive processing done for the node. We mark it BLACK. states[node] Solution.BLACK return True def buildDigraph(self, n, edges): graph [[] for _ in range(n)] for edge in edges: graph[edge[0]].append(edge[1]) return graph4.2 Javaclass Solution { // We dont use the state WHITE as such anywhere. Instead, the null value in the states array below is a substitute for WHITE. enum Color { GRAY, BLACK }; public boolean leadsToDestination(int n, int[][] edges, int source, int destination) { ListInteger[] graph buildDigraph(n, edges); return leadsToDest(graph, source, destination, new Color[n]); } private boolean leadsToDest(ListInteger[] graph, int node, int dest, Color[] states) { // If the state is GRAY, this is a backward edge and hence, it creates a loop. if (states[node] ! null) { return states[node] Color.BLACK; } // If this is a leaf node, it should be equal to the destination. if (graph[node].isEmpty()) { return node dest; } // Now, we are processing this node. So we mark it as GRAY states[node] Color.GRAY; for (int next : graph[node]) { // If we get a false from any recursive call on the neighbors, we short circuit and return from there. if (!leadsToDest(graph, next, dest, states)) { return false; } } // Recursive processing done for the node. We mark it BLACK states[node] Color.BLACK; return true; } private ListInteger[] buildDigraph(int n, int[][] edges) { ListInteger[] graph new List[n]; for (int i 0; i n; i) { graph[i] new ArrayList(); } for (int[] edge : edges) { graph[edge[0]].add(edge[1]); } return graph; } }4.3 Cclass Solution { public: static const int GRAY 1; static const int BLACK 2; bool leadsToDestination(int n, vectorvectorint edges, int source, int destination) { vectorvectorint graph buildDigraph(n, edges); vectorint states(n, 0); return leadsToDest(graph, source, destination, states); } private: bool leadsToDest(vectorvectorint graph, int node, int dest, vectorint states) { if (states[node] ! 0) { return states[node] BLACK; } if (graph[node].size() 0) { return node dest; } states[node] GRAY; for (int next_node : graph[node]) { if (!leadsToDest(graph, next_node, dest, states)) { return false; } } states[node] BLACK; return true; } vectorvectorint buildDigraph(int n, vectorvectorint edges) { vectorvectorint graph(n); for (auto edge : edges) { graph[edge[0]].push_back(edge[1]); } return graph; } };4.4 JavaScriptclass Solution { static GRAY 1; static BLACK 2; /** * param {number} n * param {number[][]} edges * param {number} source * param {number} destination * return {boolean} */ leadsToDestination(n, edges, source, destination) { const graph this.buildDigraph(n, edges); const states new Array(n).fill(null); return this.leadsToDest(graph, source, destination, states); } /** * param {number[][]} graph * param {number} node * param {number} dest * param {(number|null)[]} states * return {boolean} */ leadsToDest(graph, node, dest, states) { if (states[node] ! null) { return states[node] Solution.BLACK; } if (graph[node].length 0) { return node dest; } states[node] Solution.GRAY; for (const next_node of graph[node]) { if (!this.leadsToDest(graph, next_node, dest, states)) { return false; } } states[node] Solution.BLACK; return true; } /** * param {number} n * param {number[][]} edges * return {number[][]} */ buildDigraph(n, edges) { const graph Array.from({ length: n }, () []); for (const edge of edges) { graph[edge[0]].push(edge[1]); } return graph; } }4.5 C#public class Solution { private const int GRAY 1; private const int BLACK 2; public bool LeadsToDestination(int n, int[][] edges, int source, int destination) { Listint[] graph BuildDigraph(n, edges); int?[] states new int?[n]; return LeadsToDest(graph, source, destination, states); } private bool LeadsToDest(Listint[] graph, int node, int dest, int?[] states) { if (states[node] ! null) { return states[node] BLACK; } if (graph[node].Count 0) { return node dest; } states[node] GRAY; foreach (int nextNode in graph[node]) { if (!LeadsToDest(graph, nextNode, dest, states)) { return false; } } states[node] BLACK; return true; } private Listint[] BuildDigraph(int n, int[][] edges) { Listint[] graph new Listint[n]; for (int i 0; i n; i) { graph[i] new Listint(); } foreach (int[] edge in edges) { graph[edge[0]].Add(edge[1]); } return graph; } }4.6 Gofunc leadsToDestination(n int, edges [][]int, source int, destination int) bool { const GRAY, BLACK 1, 2 graph : make([][]int, n) for i : range graph { graph[i] []int{} } for _, edge : range edges { graph[edge[0]] append(graph[edge[0]], edge[1]) } states : make([]int, n) var leadsToDest func(node int) bool leadsToDest func(node int) bool { if states[node] ! 0 { return states[node] BLACK } if len(graph[node]) 0 { return node destination } states[node] GRAY for _, nextNode : range graph[node] { if !leadsToDest(nextNode) { return false } } states[node] BLACK return true } return leadsToDest(source) }4.7 Kotlinclass Solution { companion object { private const val GRAY 1 private const val BLACK 2 } fun leadsToDestination(n: Int, edges: ArrayIntArray, source: Int, destination: Int): Boolean { val graph Array(n) { mutableListOfInt() } for (edge in edges) { graph[edge[0]].add(edge[1]) } val states IntArray(n) fun leadsToDest(node: Int): Boolean { if (states[node] ! 0) { return states[node] BLACK } if (graph[node].isEmpty()) { return node destination } states[node] GRAY for (nextNode in graph[node]) { if (!leadsToDest(nextNode)) { return false } } states[node] BLACK return true } return leadsToDest(source) } }4.8 Swiftclass Solution { private let GRAY 1 private let BLACK 2 func leadsToDestination(_ n: Int, _ edges: [[Int]], _ source: Int, _ destination: Int) - Bool { var graph [[Int]](repeating: [], count: n) for edge in edges { graph[edge[0]].append(edge[1]) } var states Int func leadsToDest(_ node: Int) - Bool { if states[node] ! 0 { return states[node] BLACK } if graph[node].isEmpty { return node destination } states[node] GRAY for nextNode in graph[node] { if !leadsToDest(nextNode) { return false } } states[node] BLACK return true } return leadsToDest(source) } }4.9 Rustimpl Solution { pub fn leads_to_destination( n: i32, edges: VecVeci32, source: i32, destination: i32, ) - bool { let n n as usize; let source source as usize; let destination destination as usize; let mut graph vec![vec![]; n]; for edge in edges { graph[edge[0] as usize].push(edge[1] as usize); } // 0 unvisited, 1 GRAY, 2 BLACK let mut states vec![0u8; n]; fn leads_to_dest( graph: VecVecusize, node: usize, dest: usize, states: mut Vecu8, ) - bool { if states[node] ! 0 { return states[node] 2; } if graph[node].is_empty() { return node dest; } states[node] 1; for next_node in graph[node] { if !leads_to_dest(graph, next_node, dest, states) { return false; } } states[node] 2; true } leads_to_dest(graph, source, destination, mut states) } }4.10 实现要点速查语言White 表示Gray 值Black 值建图方式PythonNone12列表推导[[] for _ in range(n)]Javanull枚举数组Color.GRAYColor.BLACK泛型数组ListInteger[]C012vectorvectorintJavaScriptnull12Array.from({length: n}, () [])C#nullint?[]12Listint[]Go012make([][]int, n)Kotlin012Array(n) { mutableListOfInt() }Swift012[[Int]](repeating: [], count: n)Rust0u812vec![vec![]; n]不难发现虽然语言不同但算法骨架完全一致先判状态gray→false / black→true、再判叶子必须等于终点、标 gray、递归邻居、标 black。五、时间复杂度与空间复杂度5.1 时间复杂度对整张图执行一次完整 DFS 的常规代价是O(V E)其中V为顶点数、E为边数最坏情况下边数E可达O(V²)例如每个顶点都与其他所有顶点相连的稠密图。然而即便在稠密图中环也会被很早发现并立即剪枝短路返回false从而截断递归树若必须遍历完整张图则复杂度退化为 O(V²)O(E) 部分占主导但由于环检测带来的剪枝与回溯本题最终的整体时间复杂度为O(V)。小结得益于「遇到 gray 立即返回」的剪枝策略算法在实践中远快于朴素的全图遍历这正是三色标记 短路返回的价值所在。5.2 空间复杂度O(V E)O(E)邻接表存储所有边O(V)递归栈深度 states三色状态数组。六、为什么不用 BFSWhy not Breadth-First Search?有读者会问环检测是否可以用 BFS 完成答案在有向图中是否定的。原因如下引用自 Stack Overflow 关于「为什么有向图找环用 DFS 而非 BFS」的经典回答BFS 在无向图中或许是合理的——无向图中每条 cross edge 都定义了一个环若 cross edge 为{v1, v2}包含这两个节点的 BFS 树根为r则环为r ~ v1 - v2 ~ r~表示路径-表示单条边报告环几乎和 DFS 一样容易。只有当你知道你的无向图会有很长的路径和很小的路径覆盖即又深又窄时才值得使用 BFS——此时 BFS 的队列比 DFS 的栈占用更少内存当然两者仍都是线性的。在所有其他情况下DFS 显然是赢家。核心原因可以概括为BFS 按层扩展无法天然区分「当前路径上的节点」与「已完成的节点」因此在有向图中识别回边需要额外的祖先信息维护复杂度与正确性都不如 DFS 的递归栈直观。本题要求「从 source 出发的所有路径收敛于终点」本质上是沿路径深挖验证与 DFS 的递归模型天然契合。七、常见陷阱Common Pitfalls7.1 使用普通 visited 集合代替三色标记普通的 visited 集合无法区分「正在处理当前 DFS 路径上」与「已完全处理」的节点导致环检测失效重复访问已完成节点是合法的而重复访问当前路径上的节点才表示环。# Wrong: simple visited set if node in visited: return True # Doesnt distinguish cycle from valid revisit visited.add(node)正确做法状态数组必须区分 gray当前路径上与 black已安全见上文三色标记法。7.2 忘记检查叶子节点必须等于终点叶子节点无出边代表一条路径的终结。若某个叶子不是destination说明存在「提前终止」的路径答案应为false。漏掉此检查会错误接受终止于其他节点的路径。# Wrong: missing leaf node check if len(graph[node]) 0: return True # Should be: return node destination7.3 把「带出边的终点」当作合法终点destination必须是真正的端点无任何出边。如果destination仍有出边路径可以越过它继续延伸违反「所有路径必须终止于 destination」的要求。# Wrong: not checking destination has no outgoing edges # If graph[destination] is non-empty, paths continue past destination从算法角度这一点由「叶子节点判断」自动保证destination若存在出边它在 DFS 中就不会被当作叶子处理其子树中的叶子必然不等于destination或产生环最终返回false。7.4 忽略不可达节点与不可达终点的场景如果source根本无法到达destination或某些路径通向非终点的死胡同答案应为false。务必从source出发探索全部可达路径而不是只验证局部连通性。虽然三色标记的states只记录从 source 可达的子图状态但由于 DFS 是从 source 发起的完整遍历所有可达路径都会被检查到天然覆盖该场景。八、扩展思考与仓库中其他图论题的关联掌握了本题的三色标记 DFS 后可以顺藤摸瓜复习仓库中一系列同源问题course-schedule.md同样是「DFS 当前递归路径标记」做有向图环检测但用「visiting 集合 完成后清空」的变体实现可对比两种风格course-schedule-ii.md环检测 拓扑序输出考察 DFS 后序与入度两种思路valid-tree.md无向图的环检测parent 参数 visited与有向图三色标记形成鲜明对照count-connected-components.md连通分量计数体会「遍历所有节点」与「从指定 source 出发」两种 DFS 入口的区别。通过横向对比这些题解你会更深刻地理解三色标记的本质是把「递归路径」显式编码进状态从而让环检测与结果记忆化memoization在一次 DFS 中同时完成——这正是本题乃至整个图论 DFS 系列最值得掌握的思维模型。本文核心算法、多语言实现与陷阱分析均源自 articles/all-paths-from-source-lead-to-destination.md仓库中的完整解题代码库见 python/、java/、cpp/、javascript/、typescript/、go/、rust/、kotlin/、swift/、csharp/、dart/、scala/、ruby/、c/ 等目录可作为多语言实现的对照参考。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 1059 全路径必须终止于终点：用三色标记 DFS 判断有向图路径收敛性
LeetCode 1059 全路径必须终止于终点用三色标记 DFS 判断有向图路径收敛性【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读All Paths from Source Lead to DestinationLeetCode 1059是一道考验有向图路径收敛性与环检测的经典面试题给定有向图、起点source与终点destination需要判断「从起点出发的每一条路径是否都能最终终止于终点」。本文以 DFS 三色标记white/gray/black为核心给出完整算法推演、9 种主流语言的仓库级实现、复杂度证明与常见陷阱对照帮你同时掌握「DFS 环检测」与「叶子节点收束判断」两大图论技能。本文对应的完整题解文档位于 articles/all-paths-from-source-lead-to-destination.md读者可对照阅读。一、前置知识Prerequisites在动手解这道题之前建议先熟练掌握以下三项基本功它们也是本仓库大量图论题解如 course-schedule.md、valid-tree.md、redundant-connection.md反复使用的核心技能图的表示Graph Representation能够根据边列表edges构建邻接表adjacency list并完成建图与遍历深度优先搜索DFS递归式图遍历与回溯backtracking能理解递归栈在遍历过程中的推进与回退环检测Cycle Detection使用三色标记法white / gray / black在有向图中识别回边back edge这是本解法的灵魂所在。小提示有向图的环检测与无向图不同。无向图中一条「跨边」即可定义环参见 valid-tree.md 的 parent 参数技巧而有向图必须区分「当前递归路径中的节点」与「已完成遍历的节点」这正是三色标记的价值。二、问题定义与解题直觉2.1 问题本质题目要求验证两个条件从source出发的每一条路径都必须最终到达destination图中不能存在环——否则某些路径将无限循环永远无法终止于终点。换句话说destination必须是图中唯一的「合法终点」它是一个没有任何出边outgoing edge的叶子节点且所有从source可达的路径都收敛到它。2.2 直觉DFS 一把梭一次带环检测的 DFS 可以同时完成上述两项验证遍历过程中若再次遇到当前递归路径上的节点即 gray 节点说明存在回边 → 有环 → 返回false遇到叶子节点无出边时它必然是一条路径的终点因此它必须恰好等于destination否则返回false若某条路径中途走到了「死胡同」却并非终点同样返回false。2.3 三色标记法Three-Color MarkingDFS 过程中为每个节点维护三种状态颜色含义说明White未访问节点尚未被处理在实现中用null/0等「初始值」代替Gray正在处理节点在当前 DFS 递归路径上其子孙尚未完全探索一旦遇到 gray 节点即发现回边 → 环Black处理完毕节点及其所有子孙都已完全探索结果已知且安全再次遇到 black 节点可直接复用结果记忆化关键区别再次访问 black 节点是合法的说明存在另一条路径汇入已确认安全的子图而再次访问 gray 节点则意味着环。普通 visited 集合无法区分这两种情况这正是三色标记存在的意义。三、算法步骤根据n和edges构建邻接表graph初始化states数组长度n每个节点初始为未访问null/0即 white从source开始运行 DFS若节点状态已非 white返回states[node] BLACKgray 时返回false表示有环black 时返回true复用结果若节点是叶子graph[node]为空返回node destination将节点标记为gray递归访问所有邻居一旦某个邻居返回false立即短路返回false全部邻居确认安全后将节点标记为black返回true返回dfs(source)的结果。四、多语言实现仓库级完整代码以下实现直接取自题解文档覆盖 9 种语言方便在不同技术栈下对照理解。所有实现共享同一套算法骨架null/0代表 whiteGRAY代表正在处理BLACK代表已安全。4.1 Pythonclass Solution: # We dont use the state WHITE as such anywhere. Instead, the null value in the states array below is a substitute for WHITE. GRAY 1 BLACK 2 def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) - bool: graph self.buildDigraph(n, edges) return self.leadsToDest(graph, source, destination, [None] * n) def leadsToDest(self, graph, node, dest, states): # If the state is GRAY, this is a backward edge and hence, it creates a Loop. if states[node] ! None: return states[node] Solution.BLACK # If this is a leaf node, it should be equal to the destination. if len(graph[node]) 0: return node dest # Now, we are processing this node. So we mark it as GRAY. states[node] Solution.GRAY for next_node in graph[node]: # If we get a false from any recursive call on the neighbors, we short circuit and return from there. if not self.leadsToDest(graph, next_node, dest, states): return False # Recursive processing done for the node. We mark it BLACK. states[node] Solution.BLACK return True def buildDigraph(self, n, edges): graph [[] for _ in range(n)] for edge in edges: graph[edge[0]].append(edge[1]) return graph4.2 Javaclass Solution { // We dont use the state WHITE as such anywhere. Instead, the null value in the states array below is a substitute for WHITE. enum Color { GRAY, BLACK }; public boolean leadsToDestination(int n, int[][] edges, int source, int destination) { ListInteger[] graph buildDigraph(n, edges); return leadsToDest(graph, source, destination, new Color[n]); } private boolean leadsToDest(ListInteger[] graph, int node, int dest, Color[] states) { // If the state is GRAY, this is a backward edge and hence, it creates a loop. if (states[node] ! null) { return states[node] Color.BLACK; } // If this is a leaf node, it should be equal to the destination. if (graph[node].isEmpty()) { return node dest; } // Now, we are processing this node. So we mark it as GRAY states[node] Color.GRAY; for (int next : graph[node]) { // If we get a false from any recursive call on the neighbors, we short circuit and return from there. if (!leadsToDest(graph, next, dest, states)) { return false; } } // Recursive processing done for the node. We mark it BLACK states[node] Color.BLACK; return true; } private ListInteger[] buildDigraph(int n, int[][] edges) { ListInteger[] graph new List[n]; for (int i 0; i n; i) { graph[i] new ArrayList(); } for (int[] edge : edges) { graph[edge[0]].add(edge[1]); } return graph; } }4.3 Cclass Solution { public: static const int GRAY 1; static const int BLACK 2; bool leadsToDestination(int n, vectorvectorint edges, int source, int destination) { vectorvectorint graph buildDigraph(n, edges); vectorint states(n, 0); return leadsToDest(graph, source, destination, states); } private: bool leadsToDest(vectorvectorint graph, int node, int dest, vectorint states) { if (states[node] ! 0) { return states[node] BLACK; } if (graph[node].size() 0) { return node dest; } states[node] GRAY; for (int next_node : graph[node]) { if (!leadsToDest(graph, next_node, dest, states)) { return false; } } states[node] BLACK; return true; } vectorvectorint buildDigraph(int n, vectorvectorint edges) { vectorvectorint graph(n); for (auto edge : edges) { graph[edge[0]].push_back(edge[1]); } return graph; } };4.4 JavaScriptclass Solution { static GRAY 1; static BLACK 2; /** * param {number} n * param {number[][]} edges * param {number} source * param {number} destination * return {boolean} */ leadsToDestination(n, edges, source, destination) { const graph this.buildDigraph(n, edges); const states new Array(n).fill(null); return this.leadsToDest(graph, source, destination, states); } /** * param {number[][]} graph * param {number} node * param {number} dest * param {(number|null)[]} states * return {boolean} */ leadsToDest(graph, node, dest, states) { if (states[node] ! null) { return states[node] Solution.BLACK; } if (graph[node].length 0) { return node dest; } states[node] Solution.GRAY; for (const next_node of graph[node]) { if (!this.leadsToDest(graph, next_node, dest, states)) { return false; } } states[node] Solution.BLACK; return true; } /** * param {number} n * param {number[][]} edges * return {number[][]} */ buildDigraph(n, edges) { const graph Array.from({ length: n }, () []); for (const edge of edges) { graph[edge[0]].push(edge[1]); } return graph; } }4.5 C#public class Solution { private const int GRAY 1; private const int BLACK 2; public bool LeadsToDestination(int n, int[][] edges, int source, int destination) { Listint[] graph BuildDigraph(n, edges); int?[] states new int?[n]; return LeadsToDest(graph, source, destination, states); } private bool LeadsToDest(Listint[] graph, int node, int dest, int?[] states) { if (states[node] ! null) { return states[node] BLACK; } if (graph[node].Count 0) { return node dest; } states[node] GRAY; foreach (int nextNode in graph[node]) { if (!LeadsToDest(graph, nextNode, dest, states)) { return false; } } states[node] BLACK; return true; } private Listint[] BuildDigraph(int n, int[][] edges) { Listint[] graph new Listint[n]; for (int i 0; i n; i) { graph[i] new Listint(); } foreach (int[] edge in edges) { graph[edge[0]].Add(edge[1]); } return graph; } }4.6 Gofunc leadsToDestination(n int, edges [][]int, source int, destination int) bool { const GRAY, BLACK 1, 2 graph : make([][]int, n) for i : range graph { graph[i] []int{} } for _, edge : range edges { graph[edge[0]] append(graph[edge[0]], edge[1]) } states : make([]int, n) var leadsToDest func(node int) bool leadsToDest func(node int) bool { if states[node] ! 0 { return states[node] BLACK } if len(graph[node]) 0 { return node destination } states[node] GRAY for _, nextNode : range graph[node] { if !leadsToDest(nextNode) { return false } } states[node] BLACK return true } return leadsToDest(source) }4.7 Kotlinclass Solution { companion object { private const val GRAY 1 private const val BLACK 2 } fun leadsToDestination(n: Int, edges: ArrayIntArray, source: Int, destination: Int): Boolean { val graph Array(n) { mutableListOfInt() } for (edge in edges) { graph[edge[0]].add(edge[1]) } val states IntArray(n) fun leadsToDest(node: Int): Boolean { if (states[node] ! 0) { return states[node] BLACK } if (graph[node].isEmpty()) { return node destination } states[node] GRAY for (nextNode in graph[node]) { if (!leadsToDest(nextNode)) { return false } } states[node] BLACK return true } return leadsToDest(source) } }4.8 Swiftclass Solution { private let GRAY 1 private let BLACK 2 func leadsToDestination(_ n: Int, _ edges: [[Int]], _ source: Int, _ destination: Int) - Bool { var graph [[Int]](repeating: [], count: n) for edge in edges { graph[edge[0]].append(edge[1]) } var states Int func leadsToDest(_ node: Int) - Bool { if states[node] ! 0 { return states[node] BLACK } if graph[node].isEmpty { return node destination } states[node] GRAY for nextNode in graph[node] { if !leadsToDest(nextNode) { return false } } states[node] BLACK return true } return leadsToDest(source) } }4.9 Rustimpl Solution { pub fn leads_to_destination( n: i32, edges: VecVeci32, source: i32, destination: i32, ) - bool { let n n as usize; let source source as usize; let destination destination as usize; let mut graph vec![vec![]; n]; for edge in edges { graph[edge[0] as usize].push(edge[1] as usize); } // 0 unvisited, 1 GRAY, 2 BLACK let mut states vec![0u8; n]; fn leads_to_dest( graph: VecVecusize, node: usize, dest: usize, states: mut Vecu8, ) - bool { if states[node] ! 0 { return states[node] 2; } if graph[node].is_empty() { return node dest; } states[node] 1; for next_node in graph[node] { if !leads_to_dest(graph, next_node, dest, states) { return false; } } states[node] 2; true } leads_to_dest(graph, source, destination, mut states) } }4.10 实现要点速查语言White 表示Gray 值Black 值建图方式PythonNone12列表推导[[] for _ in range(n)]Javanull枚举数组Color.GRAYColor.BLACK泛型数组ListInteger[]C012vectorvectorintJavaScriptnull12Array.from({length: n}, () [])C#nullint?[]12Listint[]Go012make([][]int, n)Kotlin012Array(n) { mutableListOfInt() }Swift012[[Int]](repeating: [], count: n)Rust0u812vec![vec![]; n]不难发现虽然语言不同但算法骨架完全一致先判状态gray→false / black→true、再判叶子必须等于终点、标 gray、递归邻居、标 black。五、时间复杂度与空间复杂度5.1 时间复杂度对整张图执行一次完整 DFS 的常规代价是O(V E)其中V为顶点数、E为边数最坏情况下边数E可达O(V²)例如每个顶点都与其他所有顶点相连的稠密图。然而即便在稠密图中环也会被很早发现并立即剪枝短路返回false从而截断递归树若必须遍历完整张图则复杂度退化为 O(V²)O(E) 部分占主导但由于环检测带来的剪枝与回溯本题最终的整体时间复杂度为O(V)。小结得益于「遇到 gray 立即返回」的剪枝策略算法在实践中远快于朴素的全图遍历这正是三色标记 短路返回的价值所在。5.2 空间复杂度O(V E)O(E)邻接表存储所有边O(V)递归栈深度 states三色状态数组。六、为什么不用 BFSWhy not Breadth-First Search?有读者会问环检测是否可以用 BFS 完成答案在有向图中是否定的。原因如下引用自 Stack Overflow 关于「为什么有向图找环用 DFS 而非 BFS」的经典回答BFS 在无向图中或许是合理的——无向图中每条 cross edge 都定义了一个环若 cross edge 为{v1, v2}包含这两个节点的 BFS 树根为r则环为r ~ v1 - v2 ~ r~表示路径-表示单条边报告环几乎和 DFS 一样容易。只有当你知道你的无向图会有很长的路径和很小的路径覆盖即又深又窄时才值得使用 BFS——此时 BFS 的队列比 DFS 的栈占用更少内存当然两者仍都是线性的。在所有其他情况下DFS 显然是赢家。核心原因可以概括为BFS 按层扩展无法天然区分「当前路径上的节点」与「已完成的节点」因此在有向图中识别回边需要额外的祖先信息维护复杂度与正确性都不如 DFS 的递归栈直观。本题要求「从 source 出发的所有路径收敛于终点」本质上是沿路径深挖验证与 DFS 的递归模型天然契合。七、常见陷阱Common Pitfalls7.1 使用普通 visited 集合代替三色标记普通的 visited 集合无法区分「正在处理当前 DFS 路径上」与「已完全处理」的节点导致环检测失效重复访问已完成节点是合法的而重复访问当前路径上的节点才表示环。# Wrong: simple visited set if node in visited: return True # Doesnt distinguish cycle from valid revisit visited.add(node)正确做法状态数组必须区分 gray当前路径上与 black已安全见上文三色标记法。7.2 忘记检查叶子节点必须等于终点叶子节点无出边代表一条路径的终结。若某个叶子不是destination说明存在「提前终止」的路径答案应为false。漏掉此检查会错误接受终止于其他节点的路径。# Wrong: missing leaf node check if len(graph[node]) 0: return True # Should be: return node destination7.3 把「带出边的终点」当作合法终点destination必须是真正的端点无任何出边。如果destination仍有出边路径可以越过它继续延伸违反「所有路径必须终止于 destination」的要求。# Wrong: not checking destination has no outgoing edges # If graph[destination] is non-empty, paths continue past destination从算法角度这一点由「叶子节点判断」自动保证destination若存在出边它在 DFS 中就不会被当作叶子处理其子树中的叶子必然不等于destination或产生环最终返回false。7.4 忽略不可达节点与不可达终点的场景如果source根本无法到达destination或某些路径通向非终点的死胡同答案应为false。务必从source出发探索全部可达路径而不是只验证局部连通性。虽然三色标记的states只记录从 source 可达的子图状态但由于 DFS 是从 source 发起的完整遍历所有可达路径都会被检查到天然覆盖该场景。八、扩展思考与仓库中其他图论题的关联掌握了本题的三色标记 DFS 后可以顺藤摸瓜复习仓库中一系列同源问题course-schedule.md同样是「DFS 当前递归路径标记」做有向图环检测但用「visiting 集合 完成后清空」的变体实现可对比两种风格course-schedule-ii.md环检测 拓扑序输出考察 DFS 后序与入度两种思路valid-tree.md无向图的环检测parent 参数 visited与有向图三色标记形成鲜明对照count-connected-components.md连通分量计数体会「遍历所有节点」与「从指定 source 出发」两种 DFS 入口的区别。通过横向对比这些题解你会更深刻地理解三色标记的本质是把「递归路径」显式编码进状态从而让环检测与结果记忆化memoization在一次 DFS 中同时完成——这正是本题乃至整个图论 DFS 系列最值得掌握的思维模型。本文核心算法、多语言实现与陷阱分析均源自 articles/all-paths-from-source-lead-to-destination.md仓库中的完整解题代码库见 python/、java/、cpp/、javascript/、typescript/、go/、rust/、kotlin/、swift/、csharp/、dart/、scala/、ruby/、c/ 等目录可作为多语言实现的对照参考。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
