1 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 ∞ -

2 ∞ -

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(0: 0), (1: ∞), (2: ∞), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

0

∞

∞

∞

∞

∞

∞

1

datastructur.es

2 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 ∞ -

2 ∞ -

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

3

1

1

4

0

∞

∞

∞

∞

∞

∞

1

Fringe: [(1: ∞), (2: ∞), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

datastructur.es

3 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 1 0

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(2: 1), (1: 2), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

∞

∞

∞

∞

∞

∞

1

2

1

datastructur.es

4 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(2: 1), (1: 2), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

∞

∞

∞

∞

1

2

1

datastructur.es

5 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(1: 2), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

∞

∞

∞

∞

1

2

Note: Vertex removal in this implementation of Prim’s is equivalent to edge addition in the conceptual version of Prim’s.

datastructur.es

6 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 ∞ -

4 1 2

5 15 2

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(4: 1), (1: 2), (5: 15), (3: ∞), (6: ∞)]

4

∞

∞

∞

∞

1

2

1

15

datastructur.es

7 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 ∞ -

4 1 2

5 15 2

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(4: 1), (1: 2), (5: 15), (3: ∞), (6: ∞)]

4

∞

∞

1

2

1

15

datastructur.es

8 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

  • Show distTo, edgeTo, and fringe after next relaxation.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 ∞ -

4 1 2

5 15 2

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(4: 1), (1: 2), (5: 15), (3: ∞), (6: ∞)]

4

∞

∞

1

2

1

15

datastructur.es

9 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 ∞ -

4 2

5 15 2

6 ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(1: 2), (5: 15), (3: ∞), (6: ∞)]

4

∞

∞

1

2

15

datastructur.es

10 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 2 4

4 2

5 4 4

6 3 4

5

2

1

15

3

2

11

3

1

1

Fringe: [(1: 2), (3: 2), (6: 3), (5: 4)]

4

∞

∞

1

2

15

2

3

4

datastructur.es

11 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 2 0

2 0

3 2 4

4 2

5 4 4

6 3 4

5

2

1

15

3

2

11

3

1

1

Fringe: [(1: 2), (3: 2), (6: 3), (5: 4)]

4

1

2

2

3

4

datastructur.es

12 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 2 4

4 2

5 4 4

6 3 4

5

2

1

15

3

2

11

3

1

1

Fringe: [(3: 2), (6: 3), (5: 4)]

4

1

2

3

4

No need to consider edges with weight 5 and 3 since other side is already marked!

datastructur.es

13 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 2 4

4 2

5 4 4

6 3 4

5

2

1

15

3

2

11

3

1

1

Fringe: [(3: 2), (6: 3), (5: 4)]

4

1

2

3

4

datastructur.es

14 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 4

4 2

5 4 4

6 3 4

5

2

1

15

3

2

11

3

1

1

Fringe: [(6: 3), (5: 4)]

4

1

3

4

datastructur.es

15 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 4

4 2

5 4 4

6 1 3

5

2

1

15

3

2

11

3

1

1

Fringe: [(6: 1), (5: 4)]

4

1

3

4

1

datastructur.es

16 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 4

4 2

5 4 4

6 1 3

5

2

1

15

3

2

11

3

1

1

Fringe: [(6: 1), (5: 4)]

4

1

4

1

datastructur.es

17 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 4

4 2

5 1 6

6 3

5

2

1

15

3

2

11

3

1

1

Fringe: [(5: 1)]

4

1

4

1

datastructur.es

18 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 4

4 2

5 1 6

6 3

5

2

1

15

3

2

11

3

1

1

Fringe: [(5: 1)]

4

1

1

datastructur.es

19 of 19

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 -

1 0

2 0

3 4

4 2

5 6

6 3

5

2

1

15

3

2

11

3

1

1

Fringe: []

4

1

datastructur.es