c++ - 基于它们的值的自定义排序 vector 对

Question

我有以下 vector :

std::vector< std::pair<int, int> > vectorOfPairs

带有以下元素:

0, 1
0, 2
1, 4
2, 3
3, 4
4, 5
5, 6

我想对它们进行排序，使每对的第二个分量等于 vector 中最近对的第一个分量，如下所示:

0, 1
1, 4
4, 5
5, 6
0, 2
2, 3
3, 4

我不知道这是否足够清楚，我将附加一张图片来显示我正在尝试做的事情:

我觉得我应该将 sort 与某种比较器一起使用，但我在这里迷路了:

std::sort(vectorOfPairs.begin(), vectorOfPairs.end(), MyComparator);

---

bool MyComparator(pair<int, int> a, pair<int, int> b) {
    if(some_kind_of_comparison){
        return true;
    } 
    return false;
}

我是 C++ 的新手，如果有人可以帮助我提供如何执行此操作的伪代码，我将不胜感激。

Answer 1

您可以将此问题视为图形问题。你的每一对都代表有向图中的一条边。例如，对 (0, 2) 表示“从节点 0 到节点 2 有一条边”，而对 (2, 5) 表示“从节点 2 到节点 5 有一条边”。

如果你这样想的话，每对的第二个元素与下一对的第一个元素匹配的一系列边对应于图中的一条路径。例如，您给出的排序顺序中有两条路径:0 -> 1 -> 4 -> 5 -> 6 和 0 -> 2 -> 3 -> 4。因此，您尝试解决的问题解决如下:你如何将图中的边分成最少数量的边不相交路径？一旦你解决了这个问题，你就可以按照你的任何顺序输出这些路径'想按照您正在尝试做的事情进行排序。

std::sort 无法解决这个问题。例如，假设您有边 (0, 1)、(0, 2)、(2, 3) 和 (1, 3)。在这种情况下，这两个顺序都是有效的:

(0, 1)          (0, 2)
(1, 3)          (2, 3)
(0, 2)          (0, 1)
(2, 3)          (1, 3)

这是个问题。因为 (0, 1) 在第一个排序中在 (0, 2) 之前，并且 (0, 2) 在第二个排序中在 (0, 1) 之前，所以比较器可能是严格弱排序的唯一方法是 if (0, 1 ) 和 (0, 2) 是不可比的。这意味着在任何排序中，(0, 1) 和 (0, 2)(包括)之间的所有元素也必须是不可比较的，因为 transitivity of incomparability .换句话说，我们应该能够接受任何排序，置换 (0, 1) 和 (0, 2) (包括)之间的元素，并获得新的排序。这意味着这应该是一个有效的排序，即使它不是因为有一个更好的解决方案:

(0, 1)          (0, 1)
(1, 3)   -->    (0, 2)
(0, 2)          (1, 3)
(2, 3)          (2, 3)

所以没有办法使用 std::sort 来解决这个问题。

我不确定解决此问题的最佳方法是什么。这似乎与流量问题有关，但我不确定如何设置。如果我想到什么，我会更新这个答案。感谢您发布如此有趣的内容!