0

细节：

我有一个表示图子集的邻接列表的多图实现。

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

实施思路：

BFS 退出一次G被发现，所以你最终G只在多图的值中。我的想法是，如果你从 value 开始G，得到G的“key”（我们称之为H），如果H == F我们有我们的路径。否则，您继续并寻找H与另一个键关联的值（称为它D），如果D == F我们有我们的路径......此时我们的路径开始F看起来像F -> H -> G

问题：

这会扩展吗？由于地图只包含从F到的可能路径的子集G，在 G 处停止，因此它不应该意外地生成循环路径或生成重复的键。如果子集的基数为 n，那么 n 将是任何给定键的最多值，因此您连接的边数永远不会超过 n。

你将如何编码？

我可以思考所涉及的逻辑和数学，但我对地图库的理解还不够好，无法自己写出来。在阅读了 c++ 参考之后，我知道我可以使用 map 方法upper/lowerbound，但我找不到支持它的示例。

4

2 回答 2

2

结果是相对微不足道的：

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-10T13:05:58.560 回答
0

您可以遍历整个地图

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-08T23:27:02.857 回答