C++最适合的数据结构

我们有一组节点{1,2,3,4,5,6}和边缘（不需要在这里显示），并假设在找到两个任意节点之间的所有可能路径的过程之后，让我们说在(1,4)之间。比起来，我们得到了一些路径作为输出C++最适合的数据结构

开始和开始节点总是一样的。在这种情况下是（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)之间产生间(1,4)

我搜索路径内的所需的节点（这是(2,4)）的路径相信在这种情况下最合适的数据结构将是树，但不幸的是我没有太多的编程经验来解决这个问题。

哪个数据结构会是解决方案？有没有人向我展示实例实现？

我将定义一个新图形，其中只包含由至少一个找到（1,4）之间的连接的结果“触摸”的节点和拱形。这样，你将只有一个“例程”来完成路径搜索，并且所有内容都是均匀的。

2013-07-25 08:59:55

而是定义新的图我们会消耗更多的时间和记忆。我没有在问题中提到它，但假设我们有限制。因为我们可以在图表的开始处有10.000个节点。重建另一张图可能非常困难。 – zaratushtra

@zaratushtra如果您不再需要原始图形，则可以只修剪额外的节点（5,6），然后再修剪边缘。 – HAL

特别是如果您有执行时间限制和大图，您不希望必须维护和优化两种不同的路径搜索算法。内存很可能不是问题，例如，你可以实例化一个只保存shared_ptr 的图表，这会给你一个小的空间（因为它只需要记住连接）。 –

为了解决这个问题，我想你可以使用Union-Find Sets，有关如何使用这个结构，你可以看到here!

你可以找到路径之一O(lgn)

2013-07-25 09:14:41 minicaptain

回答