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

Question

我有一个由节点组成的图,我需要一个快速算法,在两个节点之间生成一个随机路径.我从头开始设计了几种算法,但似乎无法做到这一点.

要么算法陷入循环,要么当我保留受访节点的记录时,它有时会卡在被访问节点之间.我遇到的另一个问题是我的算法性能太不稳定了.

所以我的问题是; 有没有人知道一个快速稳定的算法,用于无向图中两个可达节点之间的随机路径？

Answer 1

让您的图表成为G=(V,E)。创建一个子集U的V这样U = { u | there is a path from u to the target }。

• 请注意，找到此子集U很容易-可以在线性时间内使用DFS或BFS在与目标相反的边缘上进行。

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

运行随机化（选择下一步随机探索的顶点）DFS，G'直到达到目标为止。

• 注意-想法是找到一条路径-并非一定很简单，因此您不应该维护visited集合。
• 您可能会添加一个“破坏规则”，即如果达到一定深度，您将寻找目标-非随机的，以避免无限循环。
• 磁导率会有所变化，因为它在找到的路径的长度中是线性的，可能很长也可能很短。