Search
Next: 0.4.5.2 Kruskal's Algorithm Up: 0.4.5.1 Prim's Algorithm Previous: 0.4.5.1 Prim's Algorithm

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

Scott Gasch
1999-07-09