algorithm - 什么是节点图中随机路径的快速稳定算法？

Question

我有一个由节点组成的图，我需要一个快速算法来生成两个节点之间的随机路径。为此，我从头开始设计了几种算法，但似乎都做不好。

要么算法陷入循环，要么当我记录访问过的节点时，它有时会卡在访问过的节点之间。我遇到的另一个问题是我的算法性能太不稳定。

所以我的问题是；有谁知道无向图中两个可达节点之间的随机路径的快速稳定算法？

Answer 1

让你的图为 G=(V,E)。创建 V 的子集 U 使得 U = { u |有一条从你到目标的路径。

• 请注意，找到此子集 U 很容易 - 并且可以线性完成使用时间 DFS或 BFS在从相反的边缘目标。

使用此子集，创建一个图 G'=(U,E')，其中 U 在上面定义并且 E' = E [intersection] UxU [相同的边，但仅应用于 U 中的顶点]。

随机运行(随机选择下一个要探索的顶点)DFS在 G' 上，直到您到达目标。

• 注意 - 这个想法是找到一条路径 - 不一定很简单，因此你不应该维护一个 visited 集合。
• 您可以添加一个“突破规则”，如果您到达某个深度，您将寻找目标 - 非随机的，以避免无限循环。
• 预计性能会有所不同，因为它与找到的路径的长度成线性关系，可能很长或很短...