c++ - 用端点形成路线

Question

假设我们有端点 (A, B), (B, C), (C, D)，那么我们可以形成路径 A -> B -> C。

请注意，端点的顺序是随机的。所以 (A, B), (C, D), (B, C) 也会产生路径 A -> B -> C。

但一般来说，如果给定有序的端点对，如何构建路由？

我不确定哪种数据结构在这里最有用。我正在考虑在读入输入时将每个坐标 (x,y) 存储到一个列表中。

所以 (A, B), (C, D) 将被存储为 {A, B, C, D}。每个元素是 x 还是 y 坐标可以通过其在列表中的位置的奇偶性来确定(因此列表中的第一个条目是 x，第二个条目是 y，第三个是 x，等等)。然后当每个有序对被读入时，我们查找列表以查看 x 或 y 坐标是否已经在列表中。如果是这样，我们连接。

为了演示，假设我们正在读取 (A, B)、(C, D)、(B, C)，我们的列表将是 {A, B, C, D} 在 (C, D) 只是读。当读取 (B, C) 时，我们看到 B 已经在列表中。所以我们知道 A -> B -> C。C 在列表中，我们有 A-> B -> C -> D，然后我们将 (B, C) 添加到列表中以形成 {A, B , C, D, B, C}.

我的困难是:我们如何存储 A -> B -> C？我应该使用什么数据结构？我们如何跟踪我们在行进过程中形成的部分路线？

谢谢!

Answer 1

用 adjacency 构建有向边图列表表示。然后使用 DFS从起点到终点，将之前访问过的节点存储在缓冲区中，一旦到达目的地，缓冲区中的值就是路径。