遍历multimap中查找从给定值路径给定键

我有多重映射实现，代表了一个图的子集的邻接表。

我需要找到通过图形，这实际上是从一个起始节点F结束节点G，通过运行广度取得所有可能路径的这个子集的路径首先在全图搜索。

体系的构想：G被发现，所以你最终G只在多重映射值

的BFS退出一次。我的想法是，如果你从价值G开始，得到G的“钥匙”（我们称之为H），如果H == F那么我们有我们的路径。否则，你继续寻找H作为关联到其它的键的值（称之为D），如果D == F那么我们有我们的道路......在这一点上我们的道路从F开始看起来像F -> H -> G

问题：

这个比例是？由于地图仅包含从F到G的可能路径的子集，因此停在G处，它不应该无意地制作圆形路径或制作重复键。如果子集的基数为n，那么对于任何给定的键，n将是最大数量的值，因此，连接的边数永远不会超过n。

你会如何编码？

我可以通过所涉及的逻辑和数学来思考，但我不明白地图库还不够完善，但自己写出来。 ~~阅读C++参考后，我得到了一个想法，我可以使用地图方法 upper/lowerbound，但我找不到支持该示例的示例。~~

来源

2013-03-08 frankV

可谓是比较琐碎：

typedef multimap<int, int> MapType; 
typedef MapType::const_iterator MapItr; 
vector<int> path; 

path.push_back(G); 

int end = G;         // we know G, so mark it 
    while (end != F) {      // as long as mark is not F 

     // now loop through map searching for value that matches G 
     for (MapItr iter = pathMap.begin(); iter != pathMap.end(); iter++) 
     { 
      if (iter->second == end) {   // once we find our marked value/vertex 

       path.push_back(iter->first); // push it's key onto the vector 
       end = iter->first;    // and mark it's key for next iteration 
               // continue this until end reaches F 
      }         // at which point will have our path 
               // from G to F 
     } 
    } 
    // avoid this step by using a container with a push_front method 
    reverse(path.begin(), path.end());   // reverse path

来源

2013-03-10 13:05:58 frankV

你可以通过整个地图环路

C++ 11

for(const auto& key_val: the_map) 
{ 
    std::cout<<key_val.first<<":"<<key_val.second<<std::endl; 
}

非C++ 11

for(the_map_type::const_iterator itr = the_map.begin(); itr != the_map.end();++itr) 
{ 
    std::cout<<itr->first<<":"<<itr->second<<std::endl; 
}

the_map.lower_bound(key)会给你一个迭代的第一有钥匙的元素key

the_map.upper_bound(key)会给你一个迭代的元素一个过去任何元素与关键key

来源

2013-03-08 23:27:02 AxelOmega

遍历multimap中查找从给定值路径给定键

回答

相关问题