Publish on 05th November 2019
Category: Birds
0

Spanning Trees

Spanning Trees

A spanning tree for a connected, undirected graphGis a graphSconsisting of the nodes ofGtogether with enough edges ofGsuch that:1.Sis connected, and2.Sis acyclic.Example:

E

A

D

B

C

F

E

A

D

B

C

F

One of many Spanning Trees

Why“tree”? Pick any node as the rootis a tree.Why“spanning”? Every node is (still) connected to every other node.

Algorithm for Generating a Spanning Tree

A DFS algorithm works.Just keep the tree edges.

E

A

D

B

C

F

O(m)= O(n2)(worse case)

C

A

D

B

E

F

E

A

D

B

C

F

6

1

4

5

2

Spanning Trees for Weighted Graphs

(Only) two minimal spanning trees

Weighted Graph

E

A

D

B

C

F

7

6

5

8

1

4

5

2

E

A

D

B

C

F

6

5

1

4

2

Aminimalspanning tree for aweighted, connected, undirected graphGis a graphSconsisting of the nodes ofGtogether with enough edges ofGsuch that:1.Sis connected, and2.Sis acyclic, and3.Shas minimal weight.Examples:

Note: all weights positive.

1

6

5

4

Kruskal’s Algorithm

Sort edges by weight (smallest first)For each edgee= {x,y} (in order) if nodesxandyare not in the same connected component, then adde

E

A

D

B

C

F

7

6

5

8

1

4

5

2

{A,B} 1{D,F} 2{B,C} 4{A,D} 5{C,D} 5{E,D} 6{A,E} 7{B,D} 8

2

E

C

A

B

D

F

Kruskal’s Examples

City connectivity$35 Atlanta Chicago$70 Atlanta Denver$40 Atlanta New York$65 Chicago Denver$50 Chicago New York$60 Chicago San Francisco$45 Denver San FranciscoV = {a, b, c, d, e, f}, E = {{a,b}, {a,d}, {b,c}, {b,d}, {b,f}, {c,f}, {d,e}, {e,f}}{a,b}=8 {a,d}=11 {b,c}=7 {b,d}=6 {b,f}=4 {c,f}=14 {d,e}=1 {e,f}=2

S ------ C ------ N\ / \ /\ / \ /D ------ A

F

2

(4)

E

6

(5)

D

5

(3)

C

4

(2)

Prim’s Algorithm

Initialize a spanning treeScontaining a single vertex, chosen arbitrarily from the graphUntiln-1 edges have been addedfind the edgee= {x,y} such thatxis inSandyis not inSeis the smallest weighted edge leftAddeandytoS

E

A

D

B

C

F

7

6

5

8

1

4

5

2

B

1

(1)

A

Correctness Proofs& Complexity Analysis

CorrectnessDetailed proofslengthyEssential idea:Prove connected: add edges until all nodes connectedProve acyclic: don’t add an edge that would create a cycleProve minimal weight: only add overall or local minimal-weight edgesComplexityStraightforward implementations are easy to analyze.Both algorithms have clever implementations that make them run faster.

Correctness of Prim’s Algorithm

Prim’s algorithm produces a minimal spanning treeSfrom a connected, weighted, undirected graphG.Proof (sketch)Connected: Assume not, then there are at least two disconnected components,C1andC2inS. But sinceGis connected, there is a smallest weight edge {x,y} withxinC1andyinC2that would have been found. Thus, after running Prim’s algorithm,C1andC2must be connected.Acyclic: Assume not, then there was a first edge {x, y} added to make a cycle. But to have been added,xmust have been inSandymust not have been inS. Sinceymust not have been inS, there was no path fromxtoyat the time {x,y} was added, and thus no cycle was created when {x,y} was added.Minimal weight: By induction with loop invariant: Afterkiterations the growing spanning treeShas minimal weight.Basis: 0 iterations: The initialization step selects a single node and the weight of S is 0, the minimum possible since all weights are assumed to be positive.Induction: By the induction hypothesis, afterkiterationsShas minimal weight. Then, afterk+1 iterationsShas minimal weight. For suppose not, then the chosen edgeemust not have been the smallest-weight edge left.

Complexity of Prim’s Algorithm

Initialize a spanning treeScontaining a single vertex, chosen arbitrarily from the graphUntiln-1 edges have been addedfind the edgee= {x,y} such thatxis inSandyis not inSeis the smallest weighted edge leftAddeandytoSO(1) + O(n(m+1)) = O(nm) = O(n3) in the worst case

A Faster Prim’s Algorithm

To make Prim’s Algorithm faster, we need a way to find the edgeefaster.Can we avoid looking through all edges in each iteration?We can if we sort them first and then make a sorted list of incident edges for each node.In the initialization step this takes O(mlogm) to sort and O(m) to make lists for each nodeO(mlogm) = O(n2logn2) in the worst case.Now for each of then1 iterations, we find the edge {x,y} by looking only at the first edge of at mostnlistsO(n2) over all iterations. We must, of course, discard edges on these lists as we buildS, so that the edge we want will be first, but with appropriate links, this is O(1).Thus, the sort in the initialization dominates, which makes the algorithm O(mlogm) = O(n2logn2) in the worst case.To make the algorithm even faster, we must somehow avoid the sort. Can we?

An Even Faster Prim’s Algorithm

Start with the smallest-weight edgee= {x,y} inSdiscard x and y from the list of nodes to considerfor both x and y, find the closest node, if any (among the non-discarded nodes), and keep them and their edge weightsUntiln-1 edges have been addedfind the edgee= {x,y} such thatxis inSandyis not inSeis the smallest weighted edge leftaddeandytoSdiscard y from the list of nodes to consider, and for both x and y, find the closest node, if any (among the non-discarded nodes), and keep them and their edge weightsO(m) + O(n(n+1+n)) = O(n2) in the worst case

Correctness of Kruskal’s Algorithm

Kruskal’s algorithm produces a minimal spanning treeSfrom a connected, weighted, undirected graphG.Proof (sketch)Connected: Assume not, then there are at least two disconnected components,C1andC2inS. But sinceGis connected, there is a smallest weight edge {x,y} withxinC1andyinC2that would have been added. Thus, after running Kruskal’s algorithmC1andC2must be connected.Acyclic: Assume not, then there was a first edge {x, y} added to make a cycle. But to have been added,xandymust have not been connected inS. Sincexandymust not have been connected inS, there was no path fromxtoyat the time {x,y} was added, and thus no cycle was created when {x,y} was added.Minimal weight: …

Complexity of Kruskal’s Algorithm

Sort edges by weight (smallest first)For each edgee={x,y}, untiln1 edges addedif nodesxandyare not in the same connected component, addeO(mlogm) + O(nm) = O(n2logn2) + O(n3) = O(n3)Can Kruskal’s algorithm be improved?Often already sorted (omit first step)Faster way to check“in same connected component”

*O(n) not O(m) because the edges for the DFS check are the edges added to the spanning tree so far, and there can never be more than n1 edges in the spanning tree.

O(n2logn)

0

Embed

Upload

Discussion #1 Finite State Machines