У меня есть минимальное остовное дерево, созданное с использованием алгоритма Крускала, хранящегося в карте ключ: строка и данные: набор (строка)
mst = { "A" : ["B"]
"B" : ["A", "C", "D"]
"C" : ["B"]
"D" : ["B", "E"]
"E" : ["D", "F"] }
Я пытаюсь написать алгоритм, который вернет путь между указанным начальным и конечным узлами.
$ findPath A F
> A B D E F
$ findPath F C
> F E D B C
Я думаю, что мне следует использовать какой-то модифицированный поиск в глубину, но я не уверен, как реализовать алгоритм или как сохранить узлы, формирующие путь. Я не думаю, что мне нужно беспокоиться о том, чтобы помечать узлы как «посещенные», поскольку в MST нет циклов.
Есть несколько похожих вопросов, но я не смог найти ни одного, который можно было бы применить к моему конкретному сценарию, они, кажется, имеют дело только с не-MST и возвращаются только в том случае, если путь может быть найден между двумя узлами, что в моем случае я уже знаю, что между каждым узлом есть путь, и мне также нужен список узлов на пути.
EDIT Ответ преобразован в C++, вероятно, не самый чистый код, но он работает.
vector<string> findPath(map<string, set<string>> mst, string src, string dest, vector<string> path) {
if(src == dest) {
return path;
}
set<string> possible = mst[src];
for(vector<string>::iterator it = path.begin(); it != path.end(); it++) {
if(possible.find(*it) != possible.end())
possible.erase(*it);
}
for(set<string>::iterator it = possible.begin(); it != possible.end(); it++) {
vector<string> a = path;
if(find(a.begin(), a.end(), src) == a.end())
a.push_back(src);
vector<string> p = findPath(mst, *it, dest, a);
if(p[0] != "FALSEBEGINNING") {
return p;
}
}
vector<string> p = path;
p[0] = "FALSEBEGINNING";
return p;
}