遍历MultiMap以从给定值到给定键查找路径 [英] Traverse MultiMap to Find Path from a Given Value to a Given Key

问题描述

详细信息：

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

I have a multimap implementation that represents the adjacency list for the subset of a graph.

我需要找到一个路径通过这个图的子集，这实际上是从开始节点 F 到结束的所有可能的路径

I need to find a path through this subset of the graph, which is actually all the possible paths from a start node F to an end node G, acquired by running a breadth first search on the full graph.

实现想法： G / strong>

Implementation Ideas:

发现BFS退出一次 G ，因此结果是 G 仅在多重映射的值中。我的想法是，如果你从值 G 开始，得到 G 的 code> H ），如果 H == F 那么我们有我们的路径。否则继续，并查找 H 作为与另一个键相关联的值（调用 D ），如果 D == F 那么我们有我们的路径...在这一点上，从 F 开始的路径看起来像 F - > H - G

The BFS quits once G is found, so you end up with G only in the values of the multimap. My idea is that if you start at the value G, get G's "key" (let's call it H), if H == F then we have our path. Else you continue and look for H as a value associated to another key (call it D), if D == F then we have our path... and at this point our path starting from F would look like F -> H -> G

问题：

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

Will this scale? Since the map only contains the subset of possible paths from F to G, stopping at G, it shouldn't accidentally make a circular path or make duplicate keys. And if the subset is of cardinality n, then n would be the most amount of values for any given key, and therfore the number of edges you connect can never be more than n.

您将如何编码此

我可以考虑逻辑和数学，但我不明白地图图书馆够好，但还没有自己写出来。 在阅读c ++参考之后，我得到了一个想法，我可以使用地图方法 upper / lowerbound ，但是我找不到支持这个方法的例子。

I can think through the logic and the math involved but I don't understand the map library well enough yet to write it out myself. After reading the c++ reference I get the idea I may use the map methods upper/lowerbound but I can't find an example that supports that.

推荐答案

结果相对琐碎：

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

这篇关于遍历MultiMap以从给定值到给定键查找路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！