CODEWITHSUNDEEP
c++minimum-spanning-treekruskals-algorithm
user2199943
user2199943

Reputation: 25

Kruskal’s Minimum Spanning Tree Algorithm (C++)

I'm working though an assignment on the Stanford CS106B C++ course, but I'm massively stuck implementing Kruskal's algorithm to find a minimum spanning tree.

To be more specific, I can't figure out the logic to determine whether to add an arc/ vertex to the tree. These are the instructions I've been given:

"The strategy you will use is based on tracking connected sets. For each node, maintain the set of the nodes that are connected to it. At the start, each node is connected only to itself. When a new arc is added, you merge the sets of the two endpoints into one larger combined set that both nodes are now connected to. When considering an arc, if its two endpoints already belong to the same connected set, there is no point in adding that arc and thus you skip it."

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);
    }
}
}

I know the line:

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

needs to be changed. Does anyone know what it should be? :)

Upvotes: 2

Views: 1903

Answers (1)

PureW
PureW

Reputation: 5075

One simple solution would be to iterate over nodes in

connections[arc->start->name]

and see if they match 

arc->finish->name

If so, arc->start->name and arc->finish->name are connected and there's no point in merging the two sets.

Upvotes: 2

Related Questions