0

詳細：

グラフのサブセットの隣接リストを表すマルチマップ実装があります。

グラフのこのサブセットを通るパスを見つける必要があります。これは、実際には開始ノードFから終了ノードまでのすべての可能なパスGであり、完全なグラフで幅優先検索を実行することによって取得されます。

実装のアイデア:

BFSGはいったん見つかると終了するためG、マルチマップの値のみで終了します。私の考えでは、 value から始めて、の「キー」Gを取得しG(これを と呼びましょうH)、H == Fパスがあれば取​​得します。それ以外の場合は、続行して、別のキーに関連付けられた値として探しHます (それを と呼びますD)。D == Fパスがある場合...この時点で、から始まるパスは次FのようになりますF -> H -> G

問題：

これはスケールしますか？マップには G で停止する からFまでの可能なパスのサブセットのみが含まれている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)キーを持つ要素の1つ後ろの要素へのイテレータを提供しますkey

于 2013-03-08T23:27:02.857 に答える