Follow
Publications: 44 | Followers: 0

Discussion #1 Finite State Machines

Publish on 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 rootis 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 proofslengthyEssential 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 nodeO(mlogm) = O(n2logn2) in the worst case.Now for each of then1 iterations, we find the edge {x,y} by looking only at the first edge of at mostnlistsO(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}, untiln1 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 n1 edges in the spanning tree.
O(n2logn)

0

Embed

Share

Upload

Make amazing presentation for free
Discussion #1 Finite State Machines