CS计算机代考程序代写 data structure algorithm 20_MST.pdf

20_MST.pdf

EECS 281: Data Structures & Algorithms

Lecture 20
Minimum Spanning Trees

Data Structures & Algorithms

Minimum Spanning Trees

3

The Minimum Spanning Tree Problem

Given: edge-weighted, undirected graph
G = (V, E)

Find: subgraph T = (V, E’), E’ Í E such that
§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal

§ See a cycle in T?
§ Remove edge with highest weight

§ Therefore, T must be a tree (no cycles)

4

Connect All Data-Centers

https://cdn3.vox-cdn.com/assets/4537127/USdata.png

5

Create an MST
• Minimum Spanning Tree (MST) if:

§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal

A

B

D

C

100

120

8040

20

60

Total Edge Weights:
20+40+60+100+120+80 = 420

6

Create an MST
• Minimum Spanning Tree (MST) if:

§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal

A

B

D

C

100

8040

20

60

Total Edge Weights:
20+40+60+100+80 = 300

7

Create an MST
• Minimum Spanning Tree (MST) if:

§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal

A

B

D

C

8040

20

60

Total Edge Weights:
20+40+60+80 = 200

8

Create an MST
• Minimum Spanning Tree (MST) if:

§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal

A

B

D

C

8040

20Total Edge Weights:
20+40+80 = 140

9

MST Quiz
1. Prove that a unique shortest edge must

be included in every MST

2. Prove for second shortest edge

3. What about third shortest edge?

4. Show a graph with > 1 MST

5. Show a graph and its MST

which avoids some shortest edge
6. Show a graph where every longest edge

must be in every MST

Data Structures & Algorithms

Minimum Spanning Trees

Data Structures & Algorithms

Prim’s Algorithm

13

Prim’s Algorithm
• Find an MST on edge-weighted,

connected, undirected graphs
• Greedily select edges one by one

and add to a growing sub-graph

• Grows a tree from a single vertex

14

1. Initialize a tree with a single vertex,

chosen arbitrarily from the graph

2. Grow the tree by one edge: of the edges

that connect the tree to vertices not yet in

the tree, find the minimum-weight edge,

and add that vertex to the tree

3. Repeat step 2 (until all vertices are in the

tree)

Prim’s Algorithm

15

Prim’s Algorithm
• Given graph G = (V, E)
• Start with 2 sets of vertices: ‘innies’ & ‘outies’

– ‘Innies’ are visited nodes (initially empty)
– ‘Outies’ are not yet visited (initially V)

• Select first innie arbitrarily (root of MST)
• Repeat until no more outies

– Choose outie (v’) with smallest distance
from any innie

– Move v’ from outies to innies
• Implementation issue: use linear search or PQ?

16

Prim: Data structures
• Three vectors

– Better: a vector of classes or structures!
• For each vertex v, record:

– kv: Has v been visited?
(initially false for all v Î V)

– dv: What is the minimal edge weight to v?
(initially ¥ for all v Î V, except vr = 0)

– pv: What vertex precedes (is parent of) v?
(initially unknown for all v Î V)

17

Prim’s Algorithm
Set starting point dv to 0.

Loop v times (until every kv is true):

1. From the set of vertices for which kv is
false, select the vertex v having the
smallest tentative distance dv.

2. Set kv to true.

3. For each vertex w adjacent to v for
which kw is false, test whether dw is
greater than distance(v,w). If it is,
set dw to distance(v,w) and set pw to v.

18

Implementing Prim’s
• Implement in the order listed:

– 1: Loop over all vertices: find smallest false kv
– 2: Mark kv as true
– 3: Loop over all vertices: update false

neighbors of kv
• Common Mistake: Set the first vertex to

true outside the loop

• Reordering this can result in a simple

algorithm that simply doesn’t work

19

a

b c

f

d

e

15

8 1

2

53

5

v kv dv pv

a F 0 –

b F ¥

c F ¥

d F ¥

e F ¥

f F ¥

4

13

19

20

a

b c

f

d

e

15

8 1

2

53

5

v kv dv pv

a T 0 –

b F 13 a

c F 8 a

d F 1 a

e F ¥

f F ¥

4

13

20

21

a

b c

f

d

e

15

8 1

2

53

5

v kv dv pv

a T 0 –

b F 13 a

c F 5 d

d T 1 a

e F 4 d

f F 5 d

4

13

21

22

a

b c

f

d

e

15

8 1

2

53

5

v kv dv pv

a T 0 –

b F 13 a

c F 3 e

d T 1 a

e T 4 d

f F 2 e

4

13

22

23

a

b c

f

d

e

15

8 1

2

53

5

v kv dv pv

a T 0 –

b F 13 a

c F 3 e

d T 1 a

e T 4 d

f T 2 e

4

13

23

24

v kv dv pv

a T 0 –

b F 13 a

c T 3 e

d T 1 a

e T 4 d

f T 2 e

a

b c

f

d

e

15

8 1

2

53

5

4

13

24

25

a

b c

f

d

e

15

8 1

2

53

5

v kv dv pv

a T 0

b T 13 a

c T 3 e

d T 1 a

e T 4 d

f T 2 e

4

13

25

26

MST This! (Prim’s)

B

C D E

A

5

6 7

1

3

2

4

v kv dv pv

A

B

C

D

E

Using Prim’s; start at node A

29

Complexity – Linear Search
Repeat until every kv is true:

1. From the set of vertices for which kv is
false, select the vertex v having the
smallest tentative distance dv.

2. Set kv to true.

3. For each vertex w adjacent to v for which
kw is false, test whether dw is greater
than distance(v,w). If it is, set dw to
distance(v,w) and set pw to v.

|V| times

O(|V|)O(1)

Most at this vertex: O(|V|). Cost of each: O(1).

30

Prim’s (Heap) Algorithm

Algorithm Prims_Heaps(G, s0)

//Initialize

n = |V|

create_table(n) //stores k,d,p

create_pq() //empty heap

table[s0].d = 0

insert_pq(0, s0)

O(1)
O(V)
O(1)
O(1)
O(1)

31

Prim’s (Heap) Algorithm

O(E)
O(log E)
O(1)
O(1)
O(1 + E/V)
O(1)
O(1)
O(1)
O(1)
O(log E)

while (!pq.isempty)
v0 = getMin() //heap top() & pop()
if (!table[v0].k) //not known
table[v0].k = true
for each vi Î Adj[v0]
distance = weight(v0, vi)
if (distance < table[vi].d) table[vi].d = distance table[vi].p = v0 insert_pq(distance, vi) 32 Most at this vertex: O(|V|). Cost of each: O(log(|V|). Note: Visits every edge once (over all iterations) = O(|E|). Complexity – Heaps Repeat until every kv is true: 1. From the set of vertices for which kv is false, select the vertex v having the smallest tentative distance dv. 2. Set kv to true. 3. For each vertex w adjacent to v for which kw is false, test whether dw is greater than distance(v,w). If it is, set dw to distance(v,w) and set pw to v. O(log |V|)O(1) |V| times 33 Prim’s: Complexity Summary • O(V2) for the simplest nested-loop implementation • O(E log E) with heaps – Is this always faster? – Think about the complexity of the PQ version for dense versus sparse graphs Data Structures & Algorithms Prim’s Algorithm Data Structures & Algorithms Kruskal’s Algorithm 36 Kruskal’s Algorithm • Find an MST on edge-weighted, connected, undirected graphs • Greedily select edges one by one and add to a growing sub-graph • Grows a forest of trees that eventually merges into a single tree 37 Kruskal’s Algorithm 1. Presort all edges: O(E log E) ≈ O(E log V) time 2. Try inserting in order of increasing weight 3. Some edges will be discarded so as not to create cycles • Initial edges may be disjoint – Kruskal’s grows a forest (union of disjoint trees) 38 a b c d e f 15 8 1 2 53 5 4 13 Kruskal’s Algorithm 39 a b c d e f 15 8 1 2 53 5 4 13 Kruskal’s Algorithm 40 a b c d e f 15 8 1 2 53 5 4 13 Kruskal’s Algorithm 41 a b c d e f 15 8 1 2 53 5 4 13 Kruskal’s Algorithm 42 a b c d e f 15 8 1 2 53 5 4 13 Kruskal’s Algorithm 43 a b c d e f 15 8 1 2 53 5 4 13 Kruskal’s Algorithm 44 Kruskal: Complexity Analysis • Sorting takes E log V – Happens to be the bottleneck of entire algorithm • Remaining work: a loop over E edges – Discarding an edge is trivial O(1) – Adding an edge is easy O(1) – Most time spent testing for cycles O(?) – Good news: takes less than log E ≈ log V • Key idea: if vertices vi and vj are connected, then a new edge would create a cycle – Only need to maintain disjoint sets 45 Maintaining Disjoint Sets • N locations with no connecting roads • Roads are added one by one – Distances are unimportant (for now) – Connectivity is important • Want to connect cities ASAP – Redundant roads would slow us down Q: For two cities k and j, would road (k, j) be redundant? A: Use a Union-Find data structure. 46 B C D E A 5 6 7 1 3 2 4 MST this! (Kruskal’s) Weight Edge 1 2 3 4 5 6 7 Vertex A B C D E Representative Data Structures & Algorithms Kruskal’s Algorithm 58 MST Summary • MST is lowest-cost sub-graph that – Includes all nodes in a graph – Keeps all nodes connected • Two algorithms to find MST – Prim: iteratively adds closest node to current tree – very similar to Dijkstra, O(V2) or O(E log V) – Kruskal: iteratively builds forest by adding minimal edges, O(E log V) • For dense G, use the nested-loop Prim variant • For sparse G, Kruskal is faster – Relies on the efficiency of sorting algorithms – Relies on the efficiency of union-find 59 Take-Home MST Quiz • Prove that Kruskal always finds an MST • Prove that Prim always finds an MST • Prove that Prim can start at any vertex • Hint: revisit in-class MST quiz