Search

0.4.5.1.1 Source Code

Below is an implementation of Prim's algorithm in C++. It relies on several classes and methods that are not included but should be sufficient to give you an understanding of Prim's algorithm and serve as a guide for coding your own implementation.

void prim(graph \&g, vert s) {

  int dist[g.num_nodes];
  int vert[g.num_nodes];

  for (int i = 0; i < g.num_nodes; i++) {
    dist[i] = INFINITY;

  dist[s.number()] = 0;

  for (i = 0; i < g.num_nodes; i++) {
    vert v = minvertex(g, dist);

    g.mark(v, VISITED);
    if (v != s) add_edge_to_MST(vert[v], v);
    if (dist[v] == INFINITY) return;

    for (edge w = g.first_edge; g.is_edge(w), w = g.next_edge(w)) {
      if (dist[g.first_vert(w)] = g.weight(w)) {
         dist[g.second_vert(w)] = g.weight(w);
	 vert[g.second_vert(w)] = v;
      }
    }
  }
}


int minvertex(graph \&g, int *d) {
  int v;

  for (i = 0; i < g.num_nodes; i++)
    if (g.is_marked(i, UNVISITED)) {
      v = i; break;
    }

  for (i = 0; i < g.num_nodes; i++)
    if ((g.is_marked(i, UNVISITED)) && (dist[i] < dist[v])) v = i;

  return (v);
}