Prim's Minimum Spanning Tree

From VT.Prog

The algorithm is for finding a minimum spanning tree.

Contents 1 Basic Steps 2 Cases 3 Samples 3.1 Sample 1 - Midatl Regional 2004 - Problem F 4 More Information

Basic Steps

Take a single arbitrary point in the graph.  Add it to set C.
Take all posible edges from that point, add them to a list, L

while not all connected (while not all in set C)
  Take a lowest cost edge in L that connects a vertex in set C with a vertex that is not in set C.
  Add the cost
  Add the vertex to set C
  Add any possible edges from the new vertex to L

It makes sense to implement L as a sorted list of some sort. C as a set or TreeSet.

Cases

1. Normal - graph is connected
2. Tree cannot be built, graph is not connected. This will be seen be the algorithm as the list of edges (L) being emptied before the graph is fully connected.

Samples

Sample 1 - Midatl Regional 2004 - Problem F

This is a simple problem involving finding the minimum amount of cable to connect a group of houses.

#include <iostream>
#include <map>
#include <set>
#include <string>

using namespace std;

//Maps house strings to integers
map<string,int> StringToNumber;

//House number -> housenumbers -> cost
map<int,map<int,double> > Edges;

int NumberOfHouses;

void enqueue(multimap<double,int> &L, int house)
{
        for(map<int,double>::iterator I=Edges[house].begin(); I!=Edges[house].end(); I++)
        {
                int nexthouse=I->first;
                double cost=I->second;
                L.insert(pair<double,int>(cost,nexthouse));
        }
}

double prim()
{
        double cost=0.0;

        //Queue of potential edges
        //cost -> house_number
        multimap<double,int> L;

        //Arbitrary first vertex
        int first=0;

        set<int> C; //set of connected houses
        C.insert(first);
        enqueue(L,first);

        while(C.size()<NumberOfHouses)
        {
                //Means that graph cannot be connected
                assert(L.size()!=0);

                //Get edge cost and next house
                double c=L.begin()->first;
                int h=L.begin()->second;

                //Remove edge from list
                L.erase(L.begin());

                //If not connected to h already
                if (C.count(h)==0)
                {
                        C.insert(h);
                        enqueue(L,h);
                        cost+=c;
                }

        }


        return cost;
}

int main()
{
        double maxcable; cin >> maxcable;
        int N; cin >> N;
        NumberOfHouses=N;
        for(int n=0; n<N; n++)
        {
                string s;
                cin >> s;
                StringToNumber[s]=n;
        }
        cin >> N;
        for(int n=0; n<N; n++)
        {
                string a,b;
                double d;
                cin >> a >> b >> d;
                int ai=StringToNumber[a];
                int bi=StringToNumber[b];
                Edges[ai][bi]=d;
                Edges[bi][ai]=d;

        }

        double cost=prim();
        if (cost <= maxcable)
        {
                printf("Need %.1lf miles of cable",cost);
        }
        else
        {
                printf("Not enough cable");
        }

}

More Information

For more information Wikipedia Prim's