Prim's algorithm for minimum spanning tree.

Prim.cpp

#include "Graph.h"

#define MAXINT 1000

int findTotalWeight(int start, int end, vector<int> &parents, vector<int> &distance) {
  int a = start;
  int b = end;
  int totalWeight = 0;

  while (a != b) {
    totalWeight += distance[b];
    b = parents[b];
  }

  return totalWeight;
}

void Prim(Graph &g, int start) {
  Node *tmp;
  int n = g.vertices.size();
  vector<bool> inTree(n);
  vector<int>  distance(n);
  vector<int>  parent(n);
  int v;
  int w;
  int weight;
  int dist;

  for (int i = 0; i <= g.vertexIndices.size(); i++) {
    v = g.vertexIndices[i];
    inTree[v] = false;
    distance[v] = MAXINT;
    parent[v] = -1;
  }

  v = start;
  distance[v] = 0;

  while (!inTree[v]) {
    inTree[v] = true;
    tmp = g.vertices[v];
    for (int i = 0; i < tmp->adjacencies.size(); i++) {
      w = tmp->adjacencies[i]->y;
      weight = tmp->adjacencies[i]->weight;
      if (distance[w] > weight && !inTree[w]) {
        distance[w] = weight;
        parent[w] = v;
      }
    }

    v = 1;
    dist = MAXINT;
    for (int i = 0; i < g.vertexIndices.size(); i++) {
      w = g.vertexIndices[i];
      if (!inTree[w] && dist > distance[w]) {
        dist = distance[w];
        v = w;
      }
    }
  }

  // Print results.
  for (int i = 0; i < g.vertexIndices.size(); i++) {
    w = g.vertexIndices[i];
    cout << w << ": " << findTotalWeight(start, w, parent, distance) << endl;
  }
}

int main(int argc, char **argv) {
  Graph g(true);
  g.InsertEdge(0, 1, 6);
  g.InsertEdge(1, 4, 11);
  g.InsertEdge(0, 2, 8);
  g.InsertEdge(0, 3, 18);
  g.InsertEdge(4, 5, 3);
  g.InsertEdge(5, 2, 7);
  g.InsertEdge(5, 3, 4);
  g.InsertEdge(2, 3, 9);
  g.Print();
  cout << endl << "Prim:" << endl;
  
  Prim(g, 0);

  return 0;
}