Route Between Two Nodes in Graph

    Example

    Given graph:

    for and t = E, return

    检测图中两点是否通路，图搜索的简单问题，DFS 或者 BFS 均可，注意检查是否有环即可。这里使用哈希表记录节点是否被处理较为方便。深搜时以起点出发，递归处理其邻居节点，需要注意的是处理邻居节点的循环时不是直接 return, 而只在找到路径为真时才返回 true, 否则会过早返回 false 而忽略后续可能满足条件的路径。

    Java

    根据构造函数的实现，Java 中判断是否有邻居节点时使用，而不是null. 注意深搜前检测是否被处理过。行

    复杂度分析

    遍历所有点及边，时间复杂度为 O(V+E).

    除了深搜处理邻居节点，我们也可以采用 BFS 结合队列处理，优点是不会爆栈，缺点是空间复杂度稍高和实现复杂点。

    源码分析

    时间复杂度同题解一，也是 O(V+E), 空间复杂度最坏情况下为两层多叉树，为 O(V+E).