javascript - 找到两个节点之间的所有可行路径

Question

我有一组连接节点的路径，需要能够进入两个节点以查看是否有任何可行的路径(如果超过一个，则计数)。最重要的是，我需要跟踪路线。可以在下图中找到一个简化的示例。

图像本质上是这个数组:

mappings = [
        [1,3],
        [3,6],
        [6,11],
        [11,12],
        [3,7],
        [7,10],
        [2,4],
        [4,5],
        [4,8],
        [5,9],
        [9,10]
    ];

我目前有一个 demo我可以在其中输入 2 和 10，它会告诉我正确的路径 (2 > 4 > 5 > 9 > 10)。但是，输入 1 和 10 不会生成路径，因为我的基本算法不够智能。有任何关于修改我的技巧或我可以用来解决这个问题的现有算法的提示吗？

理想情况下，我会有以下输入/输出:

Input: 1,10 
Output: 1 > 3 > 7 > 10

Input: 1,11
Output: 1 > 3 > 6 > 11

Answer 1

您可以使用以下循环:从 A 到 B 的路径集与从 A 到它所有的邻居 N，后面是从 N 到 B 的所有路径。

为避免循环，您必须检查 N 是否已在路径上。您可以通过在访问节点时标记节点并在回溯时取消标记来执行此操作。

在您的示例中，从 2 到 10 的所有路径都是从 2 到 N 的边，后跟从 N 到 10 的所有路径，即 2 > 4 后跟所有从 4 到 10 的路径。

从 4 到 10 的路径是 4 > 8 之后是从 8 到 10 的所有路径，以及 4 > 5 之后是从 5 到 10 的所有路径； 4 > 2 被禁止，因为 2 已经在来自 2 的路径中。

从 8 到 10 的路径形成一个空集，因为 8 的唯一邻居，即 4，已经在从 2 的路径中。

从 5 到 10 的路径是 5 > 9 其次是从 9 到 10 的所有路径； 5 > 4 被禁止。

从 9 到 10 的路径是 9 > 10 后接空路径(目标到达)； 9 > 5 被禁止。

该算法可以递归地写成

Visit(A, B, Path)::=
    if A == B:
        # Target reached
        Output(Path)
        return

    # Mark the node
    Mark(A)

    # Try all unmarked neighbors
    for all neighbors N of A:
        if not Marked(A):
            # Recurse
            Visit(N, B, Path + N)

    # Backtrack
    Unmark(A)

Visit(A, B, Empty)