Algorithms & Data Structures (Winter 2022) Graphs – Minimum Spanning Trees
Announcements
Copyright By PowCoder代写 加微信 powcoder
• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2. • Min-cuts
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.
Minimum Spanning Tree- Problem
• A town has a set of houses and a set of roads.
• A road connects 2 and only 2 houses.
• A road connecting houses u and v has a repair cost w(u, v).
Goal: Repair enough (and no more) roads such that:
1. everyone stays connected: can reach every house from all other houses, and
2. total repair cost is minimum.
Minimum Spanning Tree – As a graph problem
a9e 59i 33
12 c 1 f 6 h 11
• Undirected graph G = (V, E).
• Weight w(u, v) on each edge (u, v) ∈ E.
• Find T ⊆ E such that:
1. T connects all vertices (T is a spanning tree),
2. w(T ) = ∑ w(u, v) is minimized. 5 (u,v)∈T
Minimum Spanning Tree – As a graph problem
a9e 59i 33
• Ithas|V|−1edges.
• It has no cycles.
• It might not be unique.
MST– Generic Algorithm
• Initially, A has no edges.
• Add edges to A and maintain the loop
invariant: “A is a subset of some MST”.
• Initialization: The empty set trivially satisfies the loop invariant.
• Maintenance: We add only safe edges, A remains a subset of
• Termination: All edges added to A are in an MST, so when we
stop, A is a spanning tree that is also an MST.
while A is not a spanning tree do
find a edge (u, v) that is safe for A;
AßA È {(u, v)} return A
MST– Definitions
cut partitions vertices into disjoint sets, S and V – S.
A cut respects A if and only if no edge in A crosses the cut.
S a 9 e 5 9 i V-S 33
12 c 1 f 6 h 11
b 8 d 8 g 7
A light edge crossing cut (may not be unique)
(one endpoint is in S and the
This edge crosses the cut.
other is in V – S.) 8
MST– What is a safe edge?
a9e 59i 33
S 12 c 1 f 6 h 11 V-S
Intuitively: Is (c,f) safe when A=Æ?
• Let S be any set of vertices including c but not f.
• There has to be one edge (at least) that connects S with V − S.
• Why not choosing the one with the minimum weight?
MST– Safe edge
Theorem 1: Let (S, V-S) be any cut that respects A, and let (u, v) be a light edge crossing (S, V-S). Then, (u, v) is safe for A.
Let T be a MST that includes A.
Case 1: (u, v) in T. We’re done.
Case 2: (u, v) not in T. We have the following:
(x, y) crosses the cut.
LetT ́ =T-{(x,y)}È{(u,v)}. Because (u, v) is light for cut,
w(u, v) £ w(x, y). Thus,
w(T ́) = w(T)-w(x, y)+w(u, v)£w(T). Hence, T ́ is also a MST.
So, (u, v) is safe for A.
We show edges in T
MST– Safe edge
In general, A will consist of several connected components.
Corollary: If (u, v) is a light edge connecting one CC in GA=(V, A) to another CC in GA=(V, A), then (u, v) is safe for A.
while A is not a spanning tree do
find a edge (u, v) that is safe for A;
AßA È {(u, v)} return A
September 14 , 2020 McGill th
MST– Kruskal’s Algorithm
1. Starts with each vertex in its own component.
2. Repeatedly merges two components into one by choosing a light edge that connects them (i.e., a light edge crossing the cut between them).
3. Scans the set of edges in monotonically increasing order by weight.
4. Uses a disjoint-set data structure to determine whether an edge connects vertices in different components.
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Example
a9e 59i 33
Kruskal’s Algorithm – Complexity
2-3 O(v) MAKE-SETs
4 O(E lg E)
5-8 O(E) FIND-SETs and UNIONs
Kruskal’s Algorithm – Complexity
• Initialize A: O(1)
• First for loop: |V| MAKE-SETs
• Sort E: O(E lg E)
• Second for loop: O(E) FIND-SETs and UNIONs
Assuming union by rank and path compression, m find/union operations on a set with n objects is 𝑂(𝑚 & 𝛼 𝑛 ):
⟹𝑂 𝐸&𝛼 𝑉 +𝑂(𝐸&log(𝐸))
Moreover,𝛼 𝑉 =𝑂(log𝑉)=𝑂(log𝐸);(𝐸 ≥ 𝑉 −1) ⟹ 𝑂(𝐸 & log(𝐸))
Since, 𝐸 ≤ 𝑉!⟹log𝐸 =𝑂(2log𝑉)=𝑂(log𝑉) ⟹ 𝑂(𝐸 & log 𝑉)
MST– Prim’s Algorithm
1. Builds one tree, so A is always a tree.
2. Starts from an arbitrary “root” r . 3. At each step, adds a light edge
crossing cut (VA, V – VA) to A. • Where VA = vertices that A is
incident on.
Differs from Kruskal’s in that we grow a single supernode (tree) A instead of growing
multiple ones (forest) at the same time
MST– Prim’s Algorithm – Intuition
• Consider the set of vertices S currently part of the tree, and its complement (V-S). We have a cut of the graph and the current set of tree edges A is respected by this cut.
• Which edge should we add next? Light edge!
UNC Chapel Hill Lin/Foskey/Manocha
Prim’s Algorithm – Finding a light edge
1. Uses a priority queue Q to find a light edge quickly.
2. EachobjectinQisavertexinV-VA.
3. Key of v has minimum weight of any edge (u, v), where u Î VA.
4. Then the vertex returned by Extract-Min is v such that there exists u Î VA and (u, v) is light edge crossing (VA, V – VA).
5. Keyofvis¥ifvisnotadjacenttoanyvertexinVA.
Prim’s Algorithm – Basics
• It works by adding leaves one at a time to the current tree.
• Start with the root vertex r (it can be any vertex). At any time, the subset of edges A forms a single tree. S = vertices of A.
• At each step, a light edge connecting a vertex in S to a vertex in V- S is added to the tree.
• The tree grows until it spans all the vertices in V.
• Implementation Issues:
• How to update the cut efficiently?
• How to determine the light edge quickly?
Prim’s Algorithm – Implementation – Priority Queue
• Priority queue implemented using heap can support the following operations in O(lg n) time:
• Insert (Q, u, key): Insert u with the key value key in Q
• u = Extract_Min(Q): Extract the item with minimum key value in
• Decrease_Key(Q, u, new_key): Decrease the value of u’s key
value to new_key
• All the vertices that are not in S reside in a priority queue Q based on a key field. When the algorithm terminates, Q is empty.
Prim’s Algorithm
Notes: (i) r is the root.
Q := V[G];
for each u Î Q do
key[u] := ¥ p[u] := Nil;
Decrease-Key(Q,r,0); while Q 1 Æ do
u := Extract-Min(Q); for each v Î Adj[u] do
if v Î Q Ù w(u, v) < key[v] : p[v] := u;
Decrease-Key(Q,v,w(u,v));
Complexity:
Using binary heaps: O(E lg V). Building initial queue: O(V). Initialization: O(V).
V Extract-Min: O(V lgV).
E Decrease-Key: O(E lg V).
Using Fibonacci heaps: O(E + V lg V).
Prim’s Algorithm - Example
a/0 5 b/¥ 7 c/¥
d/¥ 0 e/¥ 2 f/¥
Not in tree
Q=abcdef 0¥¥¥¥¥
Prim’s Algorithm - Example
a/0 5 b/5 7 c/¥
d/11 0 e/¥ 2 f/¥
Q=bdcef 5 11 ¥ ¥ ¥
Prim’s Algorithm - Example
a/0 5 b/5 7 c/7
d/11 0 e/3 2 f/¥
Q=ecdf 3 7 11 ¥
Prim’s Algorithm - Example
a/0 5 b/5 7 c/1
d/0 0 e/3 2 f/2
Prim’s Algorithm - Example
a/0 5 b/5 7 c/1
d/0 0 e/3 2 f/2
Prim’s Algorithm - Example
a/0 5 b/5 7 c/1
d/0 0 e/3 2 f/-3
Prim’s Algorithm - Example
a/0 5 b/5 7 c/1
d/0 0 e/3 2 f/-3
Prim’s Algorithm - Example
Prim’s Algorithm - Correctness
• Again, show that every edge added is a safe edge for A • Assume (u, v) is next edge to be added to A.
• Consider the cut (A, V-A).
• This cut respects A
• and (u, v) is the light edge across the cut • Thus, by the Theorem 1, (u,v) is safe.
Prim’s Algorithm – Time complexity
• Initialization: 𝑂(𝑉)
• Extract the light edge from the queue: O(V log 𝑉)
• Relax the neighbour edges: O(𝐸 log 𝑉)
⟹ 𝑂(𝑉 log 𝑉 + 𝐸 log 𝑉) = 𝑂(𝐸 log 𝑉) // same as Kruskall Note: Using Fibonacci heaps, we can obtain 𝑂(𝐸 + 𝑉 log 𝑉).
• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2. • Min-cuts
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com