c++ - 什么是对图进行排序的有效方法？

Question

例如，假设有 3 个节点 A、B、C，A 链接到 B 和 C，B 链接到 A 和 C，C 链接到 B 和 A。在视觉形式上是这样的

C <- A -> B //A links to B & C
A <- B -> C //B links to A & C
B <- C -> A //C links to B & A

假设 A、B、C 保存在一个索引从 0 开始的数组 [A,B,C] 中。我如何根据保存的值有效地对数组 [A,B,C] 进行排序每个节点。

例如，如果 A 为 4，B 为 -2，C 为 -1，则 sortGraph([A,B,C]) 应返回 [B,C,A]。希望它清楚。如果我能以某种方式利用 std::sort 是否可能？

编辑:不是基本的排序算法。让我再澄清一点。假设我有一个节点列表 [n0,n1...nm]。每个 ni 都有一个左右邻居索引。例如，n1 的左邻居是 n0，它的右邻居是 n2。我用索引来表示邻居。如果 n1 位于索引 1，则其左邻居位于索引 0，其右邻居位于索引 2。如果我对数组进行排序，则还需要更新邻居索引。我不想真正实现自己的排序算法，关于如何进行有什么建议吗？

Answer 1

如果我正确理解编辑后的问题，你的图是一个循环链表:每个节点指向前一个和下一个节点，“最后”节点指向“第一个”节点作为它的下一个节点。

没有什么特别特别的，你需要做你想做的事。以下是我会使用的基本步骤。

1. 将所有节点放入一个数组中。
2. 使用任何排序算法(例如 qsort)对数组进行排序。
3. 遍历结果并为每个节点重置 prev/next 指针，同时考虑第一个和最后一个节点的特殊情况。