Algorithm Prim (double G[][], int n) {
//local data structures
double dist[n];
int parent[n];
boolean V[n]; //visited
double
S = 0; //length of MST – only
needed in Prim’s algorithm
//initialize
for
(int i = 0; i < n; i++) {
dist[i] =¥;
parent[i] = i;
V[i] = false;
}
//start at vertex 0 – arbitrary but
irrelevant
int v = 0;
V[v] = TRUE;
unvisited = TRUE;
while
(unvisited) {
//Prim segment inserted here
for (i = 0; i < n; i++)
{
if ((G[v][i] < dist[i]) &&
!V[i]) {
dist[i] =
G[v][i];
parent[i]
= v;
}
} //end of Prim segment
double best =¥;
for (i = 0; i < n; i++)
if ((dist[i] <
best) && !V[i]) {
best =
dist[i];
v = i;
}
V[v] = TRUE;
S += dist[v]; //only used with
Prim
unvisited = FALSE;
for (i = 0; i < n; i++)
unvisited =
unvisited || !V[i];
} //while
}
// Prim
Prim &
Dijkstra
The algorithm has the same structure, but uses two different component segments
/* Prim’s segment
for (i = 0; i < n; i++)
{
if ((G[v][i] < dist[i]) &&
!V[i]) {
dist[i] =
G[v][i];
parent[i]
= v;
}
} //end of Prim segment
*/
/*
Dijkstra’s segment
// let s = the source vertex (s = 0 in our previous example)
// initialize dist [s] = 0;
for (i = 0; i < n; i++)
{
double
cost = dist[v] + G[v][i];
if ((cost < dist[i]) &&
!V[i]) {
dist[i] =
cost;
parent[i]
= v;
}
} //end of Dijkstra segment
*/
Given, the directed graph
(implemented as an array)
|
Vertex |
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
¥ |
2.3 |
7.9 |
¥ |
¥ |
¥ |
|
1 |
¥ |
¥ |
¥ |
3.1 |
7.1 |
¥ |
|
2 |
¥ |
6.2 |
¥ |
7.9 |
2.9 |
5.2 |
|
3 |
8.2 |
¥ |
¥ |
¥ |
5.6 |
¥ |
|
4 |
¥ |
¥ |
¥ |
¥ |
¥ |
2.0 |
|
5 |
¥ |
¥ |
6.7 |
¥ |
¥ |
¥ |
dist
0 1 2 3 4 5
|
|
|
|
|
|
|
parent
0 1 2 3 4 5
|
|
|
|
|
|
|
V
0 1 2 3 4 5
|
|
|
|
|
|
|
dist
0 1 2 3 4 5
|
|
|
|
|
|
|
parent
0 1 2 3 4 5
|
|
|
|
|
|
|
V
0 1 2 3 4 5
|
|
|
|
|
|
|
Algorithm Prim (vertex * G[], int n) {
//local data structures
double dist[n];
int parent[n];
boolean V[n]; //visited
double
S = 0; //length of MST – only
needed in Prim’s algorithm
//initialize
for
(int i = 0; i < n; i++)
V[i] =FALSE;
//choose start
V[0] = TRUE;
//place all neighbors in heap
vertex * p = G[0];
while
(p != NULL) {
H.insert(*p);
p = p -> next;
}
while
(!H.empty()) {
w = H.deletemin();
if (!V[w.label]) {
//add to MST
MST += w.cost;
V[w.label] = TRUE;
parent [w.label] =
w.parent;
p = G[w.label];
while (p != NULL) {
if (!V[*p.label])
H.insert(*p);
p
= p-> next;
}
}
}
}
Data Structures
·
Graph -- Adjacency
list
·
vertex * G[n]
·
vertex
struct vertex {
double cost;
int label,
v1, v2;
vertex
* next;
}