c++ - 嵌套数据结构中的STL排序

Question

这是我创建的基于 STL 的数据结构，用于在 C++ 中表示图形。

typedef std::pair<int,int> ii;
typedef std::vector<ii> vii;
typedef std::vector< vii > graph;

在我在 Steven Halim 的(竞争性编程)书中读到的 Kruskal 算法中，他使用了边 vector 。

vector< pair<int, pair<int,int> > > edges;

然后他按重量排序(成对的第一个int)。我实现了这个算法并且它有效，但是我想使用以前的数据结构，并且我不知道如何按权重对边进行排序，因为它具有嵌套结构。

vector< vector< pair < int, int> > > graph - 如何通过代表权重的第二个参数对这个图进行排序？

std::sort( mygraph.begin(), mygraph.end(), /* HERE I GOT A TROUBLE */ )

谢谢

Answer 1

您无法使用 std::sort() 按您想要的方式对图表进行排序.

如果我理解正确的话，mygraph[u]包含{v,w}对使得有一条来自 u 的边至v重量w 。您想要按 Kruskal 的权重对边列表进行排序。但你根本无法使用建议的结构来做到这一点!

std::sort()上mygraph将对邻接列表的行重新排序，而不对行内的边进行排序。并且没有自然的方法来对行本身进行排序，因为最小的边缘可能位于不同的行中。

例如，考虑 vector 的两行，如下所示:

mygraph[0] = {{1,1}, {3,3}}
mygraph[1] = {{2,2}}

现在你想要 {2,2}按排序顺序位于其他两条边之间的边，但如果您只是对 vector 进行排序，这是不可能的。

因此，您被迫展平 vector ，以便获得可以排序的一维边 vector (形式为 {w,{u,v}}，就像 Halim 那样)。