c++ - Kruskal 的最小生成树算法 (C++)

Question

虽然我在工作an assignment在 Stanford CS106B C++ 类(class)上，但我大量坚持实现 Kruskal 算法以找到最小生成树。

更具体地说，我无法弄清楚确定是否向树添加弧/顶点的逻辑。这些是我得到的指示:

“您将使用的策略基于跟踪连接集。对于每个节点，维护与其连接的节点集。在一开始，每个节点只连接到它自己。当一个新的电弧添加后，您将两个端点的集合合并为一个更大的组合集合，两个节点现在都连接到该集合。当考虑一个arc，如果它的两个端点已经属于同一个连通集，添加该弧线没有意义，因此您可以跳过它。”

void getMinSpanTree(graphT *&graph)
{
Map<Set <nodeT *> > connections;

// Create set of arcs in decreasing order
Set<arcT *> arcs(costCmp);
Set<arcT *>::Iterator gItr = graph->arcs.iterator();
while (gItr.hasNext()) {
    arcT *arc = gItr.next();
    arcs.add(arc);
}

// Initialise map with initial node connections
Set<nodeT *>::Iterator nItr = graph->nodes.iterator();
while (nItr.hasNext()) {
    nodeT *node = nItr.next();
    Set<nodeT *> nodes;
    nodes.add(node);
    connections.add(node->name, nodes);
}

// Iterate through arcs
Set<arcT *>::Iterator aItr = arcs.iterator();
while (aItr.hasNext()) {
    arcT *arc = aItr.next();

    if (connections[arc->start->name].equals(connections[arc->finish->name])) {
        Set<nodeT *> nodes = connections[arc->start->name];
        nodes.unionWith(connections[arc->finish->name]);
        connections[arc->start->name] = nodes;
        connections[arc->finish->name] = nodes;

        // Update display with arc
        coordT start = {arc->start->x, arc->start->y};
        coordT finish = {arc->finish->x, arc->finish->y};
        DrawLineBetween(start, finish, HIGHLIGHT_COLOR);
    }
}
}

我知道这行:

if (connections[arc->start->name].equals(connections[arc->finish->name])) { 

需要改变。有谁知道它应该是什么？ :)

Answer 1

一个简单的解决方案是迭代节点

connections[arc->start->name]

看看他们是否匹配

arc->finish->name

如果是这样，arc->start->name 和 arc->finish->name 是相连的，合并这两个集合就没有意义了。