图路径的深度优先搜索适配
Depth First Search adaptation for Graph Path
我的问题是我的任务是设计一个有效的算法，给定任何无向加权图 G = (V,E,L) 两个节点 s, t ∈ V 和最大边长 L 作为输入答案是否可以从节点 s 到达节点 t。
困难的部分是我的算法应该 运行 及时 O(n + m)!
我已经有了一个不错的想法，我相信我需要使用深度优先搜索，它使用 O(1) 操作进行调整以保留 运行ning 时间。我的感觉是我需要将条件测试添加到标准深度优先搜索中，该搜索找到两个节点之间的路径以比较 L <= currentEdgeLength，并且只有在该条件为真时才将新节点添加到路径中。
如有任何意见，我们将不胜感激！
DFS 和 BFS 的复杂度都是 O(n + m)，因此您可以 运行 为每个查询重新搜索一次。你提出的正是我处理这个问题的方式。
我的问题是我的任务是设计一个有效的算法，给定任何无向加权图 G = (V,E,L) 两个节点 s, t ∈ V 和最大边长 L 作为输入答案是否可以从节点 s 到达节点 t。 困难的部分是我的算法应该 运行 及时 O(n + m)!
我已经有了一个不错的想法，我相信我需要使用深度优先搜索，它使用 O(1) 操作进行调整以保留 运行ning 时间。我的感觉是我需要将条件测试添加到标准深度优先搜索中，该搜索找到两个节点之间的路径以比较 L <= currentEdgeLength，并且只有在该条件为真时才将新节点添加到路径中。
如有任何意见，我们将不胜感激！
DFS 和 BFS 的复杂度都是 O(n + m)，因此您可以 运行 为每个查询重新搜索一次。你提出的正是我处理这个问题的方式。