找到两个顶点之间可能的最短路径

Question

假设我有一个这样的图，我一次只能访问 6 个顶点，例如，我第一次可以访问 123654，当我再次移动时，我需要从结束顶点开始我上次访问过，所以对于给定的示例，我必须从 4 开始，然后我可以做 432567。目标是从 1 开始，到我所有移动的最后一个元素恰好在 7 结束。

有什么办法可以实现吗？我已经在这个问题上停留了几个星期了，到目前为止，我的想法是继续探索我可能找到的所有可能的路线，但我认为这不是一个正确的算法，有没有更好的主意？

Answer 1

步骤1.找出所有从顶点1(V1)开始的长度为6的路径。您可以为此使用 DFS：

123456
123654
125436
125634

我假设，您不能在同一个“运行”中访问同一个顶点两次。如果可以的话，你会得到一个更大的列表。

步骤2.从V7中找出所有长度为6的路径：

765432
765234
763452
763254

步骤 3. 从 V1 和 V7

中找到一个可以在单个 运行 中到达的顶点

它是第4个顶点。然后你可以构造两个运行让你从V1到V7：

123654
432567

步骤 4. 您可以将此算法推广到任意图形。

1. 使用 DFS 或 BFS 构建可从 V1 到达的顶点列表。
2. 对从 V1 可到达的每个顶点重复此步骤，直到到达 V7（或 V[Last]）。

你需要的是 运行 在长 DFS 中的短 DFS（6 顶点“运行s”）（每个 运行 之后的顶点可达）。