嵌套数据结构中的STL排序

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

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

在秩算法，我在史蒂芬·哈利姆的（竞争性的编程）的书阅读

他使用边缘的载体。

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 */)

谢谢

用适当的lambda函数替换'/ * HERE I GOT A TROUBLE * /'来比较权重。 –

http://en.cppreference.com/w/cpp/algorithm/sort有很多关于如何使用std的示例:: sort – UKMonkey

当有人向我抛出'vector >>'并告诉我'这是一个图表“，我很难理解图表如何由此构建。我觉得你需要对内部向量进行排序，但是我不知道在你的模型中哪个向量代表了什么。谨慎解释？ – grek40

你就不能排序的图形你想使用std::sort()的方式。

如果我正确理解，mygraph[u]包含{v,w}对使得存在从u重量w的v的边缘。您想按照重量为Kruskal对边缘列表进行排序。但你根本无法用所提出的结构来做到这一点！

std::sort() on mygraph将对您的邻接列表的行重新排序而不排序行内的边缘。并且没有自然的方式来排列行，因为最小的边可能在不同的行中。

例如，考虑载体的两行是这样的：

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

现在你想{2,2}边缘到有序的另外两个边之间来但这是不可能的，如果你只是排序的载体。

因此，您必须将矢量展平，以便您可以排序边缘的一维向量（形式为{w,{u,v}}，方式为Halim）。

2017-01-30 17:06:21

谢谢。我创建了一个读取第一个数据结构并将其转换为边缘列表的函数 –

好。你现在可以直接排序，对吗？ –

是的，一切工作:)谢谢 –

回答