[go: up one dir, main page]

0% found this document useful (0 votes)
5 views33 pages

6 MST Prim

The document discusses the concept of Minimum Spanning Trees (MST) in the context of connecting vertices in a graph with minimal total edge weight. It introduces algorithms such as Prim's and Kruskal's for constructing MSTs and outlines their operational steps and complexities. The document also provides examples and visual representations to illustrate the process of building an MST.

Uploaded by

fapeli4129
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
5 views33 pages

6 MST Prim

The document discusses the concept of Minimum Spanning Trees (MST) in the context of connecting vertices in a graph with minimal total edge weight. It introduces algorithms such as Prim's and Kruskal's for constructing MSTs and outlines their operational steps and complexities. The document also provides examples and visual representations to illustrate the process of building an MST.

Uploaded by

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

CS 246

Algorithms

Minimum Spanning Tree


Problem: Laying Telephone Wire

Central office

2
Wiring: Naïve Approach

Central office

Expensive!

3
Wiring: Better Approach

Central office

Minimize the total length of wire connecting the customers

4
A Networking Problem

Problem: The vertices represent 8 regional data centers which


need to be connected with high-speed data lines. Feasibility
studies show that the links illustrated above are possible, and the
cost in millions of dollars is shown next to the link. Which links
should be constructed to enable full communication (with relays
allowed) and keep the total cost minimal.

5
Links Will Form a Spanning Tree

Cost (T) = 47 + 23 + 75 + 74 + 55 + 74 + 79
= 427

6
Minimum Spanning Trees
• Undirected, connected graph
G = (V,E)
• Weight function W: E  R
(assigning cost or length or
other values to edges)

 Spanning tree: tree that connects all the vertices


(above?)
 Minimum spanning tree: tree that connects all
the vertices and minimizes
w(T )   w(u , v)
( u , v )T

7
Minimum Spanning Tree (MST)

A minimum spanning tree is a subgraph of an


undirected weighted graph G, such that

• it is a tree (i.e., it is acyclic)


• it covers all the vertices V
– contains |V| - 1 edges
• the total cost associated with tree edges is the
minimum among all possible spanning trees
• not necessarily unique

8
How Can We Generate a MST?

9 b 9 b
a 2 6 a 2 6
d d
4 5 4 5
5 4 5 4
5 e 5 e
c c

9
Greedy Choice
We will show two ways to build a minimum
spanning tree.
• A MST can be grown from the current spanning
tree by adding the nearest vertex and the edge
connecting the nearest vertex to the MST.
(Prim's algorithm)

• A MST can be grown from a forest of spanning


trees by adding the smallest edge connecting
two spanning trees. (Kruskal's algorithm)

10
Notation

• Tree-vertices: in the tree constructed so far


• Non-tree vertices: rest of vertices

Prim’s Selection rule


• Select the minimum weight edge between a tree-
node and a non-tree node and add to the tree

11
The Prim algorithm Main Idea
Select a vertex to be a tree-node

while (there are non-tree vertices) { a


6 4
if there is no edge connecting a tree node
with a non-tree node 5
b u
return “no spanning tree”
14 2
select an edge of minimum weight 10
between a tree node and a non-tree node c v

3
add the selected edge and its new vertex 8 15
to the tree d
} f
return tree

12
Prim’s Algorithm
• Vertex based algorithm
• Grows one tree T, one vertex at a time

13
Prim – Step 1

14
Prim – Step 2

15
Prim – Step 3

16
Prim – Step 4

17
Prim – Step 5

18
Prim – Step 6

19
Prim – Step 7 Done!!

Weight (T) = 23 + 29 + 31 + 32 + 47 + 54 + 66 = 282

20
Prim Algorithm (2)
MST-Prim(G,w,r)
01 Q  V[G] // Q – vertices out of T
02 for each u  Q
03 key[u]  
04 key[r]  0 // r is the first tree node, let r=1
05 [r]  NIL
06 while Q   do
07 u  ExtractMin(Q) // making u part of T
08 for each v  Adj[u] do
09 if v  Q and w(u,v) < key[v] then
10 [v]  u
11 key[v]  w(u,v)

21
Prim Algorithm:Variables
• r:
– Grow the minimum spanning tree from the root vertex “r”.
• Q:
– is a priority queue, holding all vertices that are not in the tree
now.
• key[v]:
– is the minimum weight of any edge connecting v to a vertex
in the tree.
•  [v]:
– names the parent of v in the tree.
• T[v] –
– Vertex v is already included in MST if T[v]==1, otherwise, it
is not included yet.

22
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 0 0 0 0 0 0 0 0
Key 0 - - - - - - - -
 -1 - - - - - - - -

23
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 0 0 0 0 0 0 0 0
Key 0 4 - - - - - 8 -
 -1 a - - - - - a -

24
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2
Important: Update Key[v] only if T[v]==0

V a b c d e f g h i
T 1 1 0 0 0 0 0 0 0
Key 0 4 8 - - - - 8 -
 -1 a b - - - - a -

25
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 0 0 0 0 0 0
Key 0 4 8 7 - 4 - 8 2
 -1 a b c - c - a c

26
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 0 0 0 0 0 1
Key 0 4 8 7 - 4 6 7 2
 -1 a b c - c i i c

27
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 0 0 1 0 0 1
Key 0 4 8 7 10 4 2 7 2
 -1 a b c f c f i c

28
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 0 0 1 1 0 1
Key 0 4 8 7 10 4 2 1 2
 -1 a b c f c f g c

29
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 0 0 1 1 1 1
Key 0 4 8 7 10 4 2 1 2
 -1 a b c f c f g c

30
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 1 0 1 1 1 1
Key 0 4 8 7 9 4 2 1 2
 -1 a b c d c f g c

31
The execution of Prim's algorithm(moderate
part)
8 7
the root b c d 9
vertex 4
2
a 11 14 e
i 4
7 6
10
8
h g f
1 2

V a b c d e f g h i
T 1 1 1 1 1 1 1 1 1
Key 0 4 8 7 9 4 2 1 2
 -1 a b c d c f g c

32
Complexity: Prim Algorithm
MST-Prim(G,w,r)
01 Q  V[G] // Q – vertices out of T
02 for each u  Q
03 key[u]   O(V)
04 key[r]  0
05 [r]  NIL
06 while Q   do O(V)
07 u  ExtractMin(Q) // making u part of T Heap: O(lgV)
08 for each v  Adj[u] do
Overall: O(E)
09 if v  Q and w(u,v) < key[v] then
10 [v]  u
11 key[v]  w(u,v)
Decrease Key: O(lgV)

Overall complexity: O(V)+O(V lg V+E lg V) = O(E lg V)

33

You might also like