Пройдите через MultiMap, чтобы найти путь от заданного значения к заданному ключу
Подробности:
У меня есть реализация мультикарты, которая представляет список смежности для подмножества графа.
Мне нужно найти путь через это подмножество графа, который фактически является всеми возможными путями из начального узла F до конечного узла G, полученный в результате поиска в ширину в первом графе.
Идеи реализации:
BFS выходит один раз G найден, так что вы в конечном итоге G только в значениях мультикарты. Моя идея заключается в том, что если вы начнете со значения G, получить G«ключ» (давайте назовем это H), если H == F тогда у нас есть наш путь. Иначе ты продолжаешь и ищешь H как значение, связанное с другим ключом (назовите его D), если D == F тогда у нас есть свой путь … и в этот момент наш путь начинается с F будет выглядеть F -> H -> G
Вопросы:
Будет ли этот масштаб? Поскольку карта содержит только подмножество возможных путей из F в Gостанавливаясь на G, он не должен случайно делать круговой путь или дублировать ключи. И если подмножество имеет кардинальное значение n, тогда n будет наибольшим количеством значений для любого данного ключа, и поэтому число соединяемых ребер никогда не может быть больше n.
Как бы вы это закодировали?
Я могу продумать логику и математику, но я недостаточно хорошо понимаю библиотеку карт, чтобы написать ее сам. Прочитав ссылку на c ++, я понял, что могу использовать методы map upper/lowerbound но я не могу найти пример, который поддерживает это.
Решение
Оказывается относительно тривиально:
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
Другие решения
Вы можете просто просмотреть всю карту как
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