难度: Medium
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:
输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2 输出：true
示例2:
输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4 输出 true
提示：
运行时间: 89 ms
内存: 53.4 MB
class Solution:
def findWhetherExistsPath(self, n: int, graph, start: int, target: int) -> bool:
flag=[0]*n
next=[[] for _ in range(n)]
for l,r in graph:
next[l].append(r)
flag[start]=1
stack=[start]
while stack:
node=stack.pop()
for r in next[node]:
if r==target:
return True
elif flag[r]==0:
stack.append(r)
flag[r]=1
return False
该题解采用了深度优先搜索（DFS）的算法来解决有向图中两个节点之间是否存在路径的问题。首先，构建邻接表来表示图，这由列表 `next` 表示，其中 `next[i]` 包含所有从节点 i 可以直接到达的节点。使用一个标志数组 `flag` 来记录每个节点是否已被访问过，以避免循环访问和重复工作。从起始节点 `start` 开始，使用栈（这里的实现使用列表的 pop 方法模拟栈）来进行深度优先搜索。每次从栈中取出一个节点，检查其所有邻接节点；如果邻接节点是目标节点 `target`，则立即返回 true 表示路径存在。如果不是目标节点且未被访问过，则将其加入栈中并标记为已访问。如果所有可能的路径都检查完毕，栈为空，则返回 false 表示没有路径。
时间复杂度: O(n + m)
空间复杂度: O(n + m)
class Solution:
def findWhetherExistsPath(self, n: int, graph, start: int, target: int) -> bool:
flag = [0] * n # 记录节点访问状态，0表示未访问，1表示已访问
next = [[] for _ in range(n)] # 邻接表
for l, r in graph:
next[l].append(r) # 构造邻接表
flag[start] = 1 # 标记起始节点为已访问
stack = [start] # 使用栈进行深度优先搜索
while stack:
node = stack.pop() # 取出一个节点进行探索
for r in next[node]: # 遍历该节点的所有邻接节点
if r == target:
return True # 如果邻接节点是目标节点，则路径存在
elif flag[r] == 0:
stack.append(r) # 如果邻接节点未被访问，加入栈中
flag[r] = 1 # 标记为已访问
return False # 如果所有节点都访问完毕，未找到路径，则返回False
DFS和BFS都可以用来解决找出图中两个节点是否存在路径的问题。选择DFS主要是因为其实现简单且在许多情况下能够更快地找到解决方案。DFS通过栈的使用，能够迅速深入探索图中的路径，尤其是在目标节点可能位于图的深层部分时，DFS可能更快地找到路径。此外，DFS在递归形式中编码更为直观。然而，BFS也有其优势，特别是在需要找到最短路径或者图比较宽时，BFS可能会更加高效。总之，本题解选择DFS主要是出于对场景的假设和简化实现的考虑。
在构建邻接表时，如果存在重复的边，这可能导致算法在遍历时重复访问同一条边，从而增加执行时间。在DFS中，虽然可以通过访问标记防止重复访问同一节点，但处理重复边仍然会造成不必要的性能负担。因此，在实际应用中，建议在构建图时去除重复的边。这不仅可以减少存储空间的消耗，还能提高算法的运行效率。
在DFS中使用颜色标记法是一种常见的技术，特别是在需要检测图中是否存在环的场景下。通过三种颜色（通常是白色、灰色和黑色）来表示节点的访问状态：白色代表未访问，灰色代表节点正在被访问（即节点已经进入递归栈中），黑色则表示节点的所有邻接节点都被访问完成，即出栈。这种方法不仅可以帮助检测环，还可以帮助理解递归过程中节点的状态。在本题的场景中，尽管主要目标是确定两个节点间是否存在路径，如果问题扩展到需要确保路径不存在环，那么颜色标记法将非常有用。