0

Possible Duplicate:
Find the paths between two given nodes?

Given a directed graph, how to find ALL the possible paths between two nodes and return those paths.

If not in Java, please recommend me with the algorithm for it. I searched and what I found is using BFS or DFS, but I'm not able to see which is better in my case. And how to keep track of all paths not only the shortest one.

For example, given the following graph:

1 -> 2

1 -> 3

2 -> 3

3 -> 4

For paths between nodes 1 and 4, the output should be:

First Path: 1 -> 2 -> 3 -> 4

Second Path: 1 -> 3 -> 4

4

1 回答 1

2

对我来说，向后遍历要容易得多。算法步骤如下：

  1. 从目的地（即您的示例中的 4）作为起点。
  2. 收集所有以第二个元素为目的地的节点，例如 (3,4)。
  3. 假设起点（3在第一次迭代中）作为新目的地并重复步骤1&2直到没有可用的匹配节点。递归的好场景。您将获得您的收藏： [(1,2), (2,3), (3,4)], [(1,3), (3,4)]
  4. 检查上面创建的集合，如果反向目标等于您的源，则保留它，否则丢弃（在您的情况下，没有什么可丢弃的）。你完成了。
于 2012-12-13T03:54:51.377 回答