2

我正在完成斯坦福 CS106B C++ 课程的作业，但我在很大程度上坚持实施 Kruskal 的算法来找到最小生成树。

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

“您将使用的策略基于跟踪连接集。对于每个节点，维护与其连接的节点集。在开始时，每个节点仅连接到自身。添加新弧时，您合并两个端点的集合成一个更大的组合集合，两个节点现在都连接到。考虑弧时，如果它的两个端点已经属于同一个连接集，则添加该弧没有意义，因此您跳过它。 "

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])) {

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

4

1 回答 1

2

一种简单的解决方案是遍历节点

connections[arc->start->name]

看看他们是否匹配

arc->finish->name

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

于 2013-05-23T14:49:34.673 回答