c++ - STL 列表迭代器的问题

Question

在使用指针谷歌/绕过一千次尝试后，我决定自己将这个问题发布给你们。

这就是问题所在:我正在尝试根据我之前制作的图表创建最小生成树。为此，我正在使用 Kruscal 算法，该算法是关于检查从短到长的每条弧并选取我错过的顶点。

为此，我使用 STL::map 作为邻接矩阵来实现我的图形。该 map 由以下对组成:(double distance, pair-Vertex*, Vertex*- )。

该算法要求您区分未完全区分的一对，其中一个您只需要一个顶点:前者需要您创建另一个集合，您必须通过获取弧线逐渐连接所有这些集合连接它们的弧线(这些弧线当然是那些在一组中有 1 个顶点而在另一组中有 1 个顶点的弧)。

我决定以这种方式实现 Kruscal:我的 MST(最小生成树)本身就是一个 STL::map，所以每个子集都是。它们被组织在一个 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;
}

Answer 1

您定义了一个问题，但问题在哪里？

我不明白你为什么要用艰难的方式来做这件事。通常你使用弧的排序列表和 Union-Find在实现 Kruskal 时表示树的结构。