我必须实现 MST。我想成对添加值。我的问题是如何迭代具有值对的 map 以及如何访问 map 。
void addedge(multimap<int, pair<int, int> > dirgraph, int source, int dest, int weight) // graph, source, dest, weight
{
dirgraph.insert(make_pair(weight, make_pair(source, dest)));
}
multimap<int, pair<int,int> > dirgraph;
addedge(dirgraph, 0, 1, 5);
addedge(dirgraph, 0, 4, 3);
addedge(dirgraph, 1, 2, 1);
addedge(dirgraph, 1, 4, 4);
addedge(dirgraph, 4, 3, 3);
addedge(dirgraph, 2, 3, 2);
multimap<int, pair<int, int> >::iterator it = dirgraph.begin();
multimap<int, pair<int, int> >::iterator itend = dirgraph.end();
for (; it != itend; it++)
cout << (*it).first << " from " << (*it).second.first << " to " << (*it).second.second << endl; // This dosen't work.
最佳答案
由于您的问题没有另外标记,我假设是 C++11。这是代码的注释和改进版本。
using edge = std::pair<int,int>; // for clarity
using directional_graph = std::multimap<int,edge>; // not std::map<edge,weight> ?
void add_edge(directional_graph &dirgraph, // pass by reference
int source, int dest, int weight)
{
dirgraph.insert(std::make_pair(weight, std::make_pair(source, dest)));
}
directional_graph dirgraph;
add_edge(dirgraph, 0, 1, 5);
add_edge(dirgraph, 0, 4, 3);
add_edge(dirgraph, 1, 2, 1);
add_edge(dirgraph, 1, 4, 4);
add_edge(dirgraph, 4, 3, 3);
add_edge(dirgraph, 2, 3, 2);
for(const auto&x : dirgraph)
std::cout << x.first << " from " << x.second.first << " to "
<< x.second.second << std::endl;
请注意,这段代码更加清晰明了。我使用 std::
来避免糟糕的 using namespace std;
。最重要的是,这段代码是正确的,因为 add_edge()
实际上改变了第一个参数。在您的代码中,您创建了图形的本地拷贝,对其进行了修改,但对实际图形没有任何影响。
请注意:我发现您使用图的权重作为键很奇怪:您真的想通过权重来识别边吗?我本以为 edge
类型更适合作为键。在这种情况下,如果边是唯一的,则不需要 multimap
,而只需要普通的 map
。
关于c++ - 如何遍历以值为对的 map ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44526392/