algorithm - 对知道邻居的节点进行排序，但不知道他们在哪一边

Question

取 N 个节点(其中 N >= 3)排列成一条直线。每个节点都知道自己的唯一标识符和离它最近的两个节点的标识符，但不知道最近的两个节点在哪一边。

如果我得到一组代表节点的对象，我该如何对它们进行排序以使它们按正确的顺序排列？

例如，如果我们有四个节点排列为 1,2,3,4，它们可以由具有属性 (1,2,3) (2,1,3) (3,2,4) & 的四个对象表示(4,2,3) 其中三元组是 (node, neighbor1, neighbor2)。

我要在这里稍微强调一点，但重要的是节点不知道哪个邻居是哪个。例如，节点 3 知道节点 2 和 4 是它最近的邻居，但不知道每个节点在哪一侧。因此，上面显示的四个对象等同于 (1,3,2) (2,3,1) (3,4,2) & (4,3,2) 和任何其他有效排列。

线尾的节点显然是有问题的，因为它们的两个最近的邻居都在同一侧——尽管节点本身并没有意识到这一点。

因此，给定代表节点的 N 个随机排序的对象，我使用一种算法对对象进行排序，使它们处于正确的顺序:即从左到右或从右到左等同于方向节点未知。

欢迎提出任何建议。谢谢!

顺便说一句 - 如果这是一个“众所周知”的数据结构/算法问题，我会 (a) 为无法在网上找到它而自责并且 (b) 很高兴有(大概) 和同样众所周知的解决方案。

Answer 1

您可以从识别成对的两个端点开始。您可以通过识别具有相同元素的点对来做到这一点。

对于 N > 4

例如 (1,2,3) 和 (2,1,3) 是同一端的相邻点，因为它们具有相同的元素。现在哪一个是终点，哪一个是邻居？

为此，您会注意到端点(此处为 1)不应作为任何其他节点的邻居出现，而另一个节点(此处为 2)将作为另一个节点(此处为 3)的邻居出现如果 N > 4。事实上，另一个节点应该紧挨着这个节点。

然后您可以相应地进行。

如果 N == 3，那么您可以按任何顺序对元素进行排序，实际上有 6 种方式是可能的，因为所有元素都是彼此的邻居。

对于 N == 4，只要您确定端点对，您的问题就会得到解决。

操作复杂度:O(N^2)