Scribd
Upload
18 views

Lecture9-Prim Fheap

lecture9-prim_fheap

Uploaded by

long97832
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views

Lecture9-Prim Fheap

lecture9-prim_fheap

Uploaded by

long97832
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 20

Lecture 9.

2: Prim’s Algorithm

MST-Prim(G, w, r) 6 4
5 9
Q = V[G];
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15

p[r] = NULL;
3 8
while (Q not empty)
u = ExtractMin(Q); Run on example graph
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; ∞ ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
∞ ∞ ∞
p[r] = NULL;
3 ∞ 8
while (Q not empty)
u = ExtractMin(Q); Run on example graph
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; ∞ ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
r 0 ∞ ∞
p[r] = NULL;
3 ∞ 8
while (Q not empty)
u = ExtractMin(Q); Pick a start vertex r
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; ∞ ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
u 0 ∞ ∞
p[r] = NULL;
3 ∞ 8
while (Q not empty)
u = ExtractMin(Q); Black vertices have been removed from Q
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; ∞ ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
u 0 ∞ ∞
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q); Black arrows indicate parent pointers
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 14 ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
u 0 ∞ ∞
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 14 ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 ∞ ∞
p[r] = NULL;
3 3 8
while (Q not empty) u
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 14 ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 ∞
p[r] = NULL;
3 3 8
while (Q not empty) u
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 10 ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 ∞
p[r] = NULL;
3 3 8
while (Q not empty) u
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 10 ∞ ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 ∞
p[r] = NULL;
3 3 8
while (Q not empty) u
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 10 2 ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 ∞
p[r] = NULL;
3 3 8
while (Q not empty) u
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
5 9
Q = V[G]; 10 2 ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty) u
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
u
5 9
Q = V[G]; 10 2 ∞
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 ∞ 4
u
5 9
Q = V[G]; 10 2 9
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
4 u
MST-Prim(G, w, r) 6 4
5 9
Q = V[G]; 10 2 9
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
4 u
MST-Prim(G, w, r) 6 4
5 9
Q = V[G]; 5 2 9
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
u
MST-Prim(G, w, r) 6 4 4
5 9
Q = V[G]; 5 2 9
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
u 4
MST-Prim(G, w, r) 6 4
5 9
Q = V[G]; 5 2 9
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
u
MST-Prim(G, w, r) 6 4 4
5 9
Q = V[G]; 5 2 9
for each u ∈ Q
key[u] = ∞; 14 2
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);
Prim’s Algorithm
MST-Prim(G, w, r) 6 4 4
5 9
Q = V[G]; 5 2 9
for each u ∈ Q
key[u] = ∞; 14 2 u
10
key[r] = 0; 15
0 8 15
p[r] = NULL;
3 3 8
while (Q not empty)
u = ExtractMin(Q);
for each v ∈ Adj[u]
if (v ∈ Q and w(u,v) < key[v])
p[v] = u;
key[v] = w(u,v);

You might also like