После тысячи попыток Google / обхода с использованием указателей я решил сам задать этот вопрос вам, ребята.
Вот проблема: я пытаюсь создать минимальное связующее дерево из графикачто я ранее сделал.Для этого я использую алгоритм Крускала, который заключается в проверке каждой дуги от короткой до самой длинной и взятии пропущенных вершин.
Для этого я реализовал свой граф с использованием stl :: map в качествематрица соответствий.Карта составлена из следующей пары: (двойное расстояние, пара-вершина *, вершина * -).
Алгоритм требует, чтобы вы различали пару, которой у вас нет, и одну из которых вам нужна только одна вершина: первой требуется, чтобы вы создали другой набор, и вы должны постепенно соединить все эти наборы с помощьюполучение дуг, которые их соединяют (это, конечно, дуги, имеющие 1 вершину в наборе и 1 вершину в другой).
Я решил реализовать Kruscal следующим образом: мой MST (минимальное связующее дерево) являетсяstl :: map сама по себе, и поэтому каждое подмножество есть.Они организованы в виде списка карт (который я печатаю по умолчанию: map_t): каждый раз, когда я получаю узел, в котором я пропускаю 2 вершины, в список добавляется одно дерево, и этот узел помещается в него.Соединения заставят мой MST войти в первый узел списка.
Код кажется мне нормальным, но нет никакого способа, которым итераторы списка будут довольны этим.Вот код:
map_t Grafo::createKruscalMST() {
mapIterator_t iterator = adjmatrix.begin();
mapIterator_t end = adjmatrix.end()--;
list<map_t> MST;
list<map_t>::iterator listend = MST.end(); // Per puntare alla fine della lista devo fare end()-1 perché end() è il primo dopo la fine
//MST.resize(1);
bool zeromatch = true;
list<map_t>::iterator memo1 = MST.end(); // Valore che non c'è: MST.end() punta al primo elemento dopo la fine della lista
int common;
list<map_t>::iterator j = MST.begin();
MST.resize(1);
//++j;
*j = setUnion(*j, iterator); // Inserisco in automatico il primo nodo
while (iterator != adjmatrix.end() )
{
++iterator;
zeromatch = true;
memo1 = MST.end();
for (j = MST.begin(); j != MST.end(); ++j)
{
common = howManyInCommon(*j, iterator);
if (common == 2) zeromatch = false;
if (common == 1)
{
zeromatch = false;
if (memo1 == MST.end() ) memo1 = j; // Se nessun altro prima di me aveva 1 e un solo match, mi ricordo della posizione
else
{
*memo1 = treeMerge(*memo1, *j); // Se c'era un altro prima di me, lo copio tutto nel precedente e poi cancello l'altra occorrenza.
MST.erase(j); // Questo farà affiorare l'MST nel nodo di testa, alla lunga.
*memo1 = setUnion(*memo1, iterator); // Includo anche il collegamento tra i due semialberi.
memo1 = MST.end(); // Fatto ciò, provvedo a resettare l'iteratore di appoggio
}
}
}
if (memo1 != MST.end() )
*memo1 = setUnion(*memo1, iterator);
if (zeromatch == true )
{
//MST.resize(MST.size()+1);
//listend = MST.end()--;
MST.push_back( setUnion(MST.back(), iterator) );
}
}
return MST.front();
}
int howManyInCommon(map_t disjset, mapIterator_t vertexptr) {
int j = 0; // Parto da 0 e conto direttamente quanti ne ho in comune (molto meglio di una concatenazione di if)
if (vertexptr->second.first->getRepresenter() == disjset.begin()->second.first->getRepresenter() )
j++;
if (vertexptr->second.second->getRepresenter() == disjset.begin()->second.first->getRepresenter() )
j++;
return j;
}
map_t setUnion(map_t Tree, mapIterator_t i) {
if (Tree.empty() ) {
Tree.insert(*i);
Tree.begin()->second.second->setRepresenter(Tree.begin()->second.first->getRepresenter() ); // Il rappresentante del secondo nodo diventa uguale a quello del primo
}
else {
i->second.first->setRepresenter(Tree.begin()->second.first->getRepresenter() );
i->second.second->setRepresenter(Tree.begin()->second.first->getRepresenter() );
// Nodo della mappa - Nodo con pair <double, pair<Nodo*,Nodo*> - Devo lavorare sul secondo del pair esterno, dunque.
Tree.insert(*i);
}
return Tree;
}
map_t treeMerge(map_t Dest, map_t Source) {
mapIterator_t srciterator = Source.begin();
while (srciterator != Source.end() ) {
Dest = setUnion(Dest, srciterator);
++srciterator;
}
return Dest;
}