1

我们有一组节点{1,2,3,4,5,6} 和边（不需要在这里显示）并假设在找到两个任意节点之间的所有可能路径的过程之后，假设在(1,4). 比，我们得到了一些路径作为输出

1 2 4
1 3 4
1 2 3 4
1 3 2 4

start 和 begin 节点总是相同的。在这种情况下是（1,4）。

然后，我们希望将这些输出存储到一个合适的数据结构（可能是一棵树）中，以便从当前输出（在 (1,4) 之间）重新排序和重现新路径，而无需再次查看图表。例如，假设现在我们想要列出 (2,4) 之间的所有可能路径，但不再从图中列出，只是从我们从 (1,4) 获得的列表中列出。这将是;

2 4 (from 1st line)
2 3 4 (from 3rd line)
2 4 (from 4th line )

或在 (3,4) 之间；

3 4 (from 2nd line)
3 4  (from 3rd line)
3 2 4  (from 4th line)

问题是存储 之间的路径(1,4)，这种方式应该可以轻松地(2,4)从搜索点之间的路径中生成所需节点（即(2,4)）之间的路径(1,4)

我相信在这种情况下最合适的数据结构是树，不幸的是我没有太多的编程经验来解决这个问题。

哪种数据结构是解决方案？有没有人给我看一个实例实现？

4

2 回答 2

2

为了解决这个问题，我想你可以使用Union-Find Sets，关于如何使用这个结构你可以看这里！

你可以找到其中一条路径O(lgn)

于 2013-07-25T09:14:41.717 回答
1

我将定义一个新图，其中仅包括节点和拱门，这些节点和拱门至少被找到 (1, 4) 之间的连接的结果之一“触及”。这样，您将只有一个“例程”来进行路径搜索，并且一切都是同质的。

于 2013-07-25T08:59:55.380 回答