遍歷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中查找從給定值路徑給定鍵

回答

相關問題