Strongly Connected Components Given directed graph G = (V, E): A strongly connected component (SCC) of G is a maximal set of vertices C ⊆ V such that for every pair of vertices u, v ∈ C, we have both u v and v u. CS 477/677 - Lecture 24 2

The Transpose of a Graph • GT = transpose of G – GT is G with all edges reversed – GT = (V, ET), ET = {(u, v) : (v, u) ∈ E} • If using adjacency lists: we can create GT in Θ(|V| + |E|) time 1 2 1 2 3 5 4 3 5 CS 477/677 - Lecture 24 4 3

Finding the SCC • Observation: G and GT have the same SCC’s – u and v are reachable from each other in G ⟺ they are reachable from each other in GT • Idea for computing the SCC of a graph G = (V, E): – Make two depth first searches: one on G and one on G1T 2 2 1 3 5 4 3 5 CS 477/677 - Lecture 24 4 4

STRONGLY-CONNECTED-COMPONENTS(G) 1. call DFS(G) to compute finishing times f[u] for each vertex u 2. compute GT 3. call DFS(GT), but in the main loop of DFS, consider vertices in order of decreasing f[u] (as computed in first DFS) 4. output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC CS 477/677 - Lecture 24 5

Example a b c d 13/14 11/ 16 1/ 10 8/ 9 12/15 3/ 4 2/ 7 5/ 6 e f g h a b c d e f g h DFS on the initial graph G b e a c d g h f 16 15 14 10 9 7 6 4 DFS on GT: • start at b: visit a, e • start at c: visit d • start at g: visit f • start at h Strongly connected components: C1 = {a, b, e}, C2 = {c, d}, C3 = {f, g}, C4 = {h} CS 477/677 - Lecture 24 6

Component Graph a b c d cd abe e f g h fg h • The component graph GSCC = (VSCC, ESCC): – VSCC = {v1, v2, …, vk}, where vi corresponds to each strongly connected component Ci – There is an edge (vi, vj) ∈ ESCC if G contains a directed edge (x, y) for some x ∈ Ci and y ∈ Cj • The component graph is a DAG CS 477/677 - Lecture 24 7

Lemma 1 Let C and C’ be distinct SCC’s in G Let u, v ∈ C, and u’, v’ ∈ C’ Suppose there is a path u u’ in G Then there cannot also be a path v’ v in G. Proof • Suppose there is a path v’ v • There exists u u’ v’ C u • There exists v’ v u • u and v’ are reachable from each other, so they are not in separate SCC’s: contradiction! CS 477/677 - Lecture 24 C’ u’ v v’ 8

Minimum Spanning Trees Problem • • • b 8 c 7 d 4 2 A town has a set of houses 14 a 11 i 4 and a set of roads 6 7 8 A road connects 2 and only h g f 2 2 houses 1 A road connecting houses u and v has a repair cost w(u, v) 9 e 10 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 CS 477/677 - Lecture 24 9

Minimum Spanning Trees • A connected, undirected graph: – Vertices = houses, Edges = roads • A weight w(u, v) on each edge (u, v) ∈ E Find T ⊆ E such that: 4 1. T connects all vertices 2. w(T) = Σ(u,v)∈T w(u, v) is 8 b 7 d 2 11 a c h CS 477/677 - Lecture 24 1 e 14 4 6 7 8 minimized i 9 10 g 2 f 10

Minimum Spanning Trees • T forms a tree = spanning tree • A spanning tree whose weight is minimum over all spanning trees is called a minimum spanning tree, or MST. 8 b 4 7 d 2 11 a c i h 1 e 14 4 6 7 8 9 10 g 2 f CS 477/677 - Lecture 24 11

Properties of MSTs • Minimum spanning trees are not unique – Can replace (b, c) with (a, h) to obtain a different spanning tree with the same cost • MST have no cycles b 4 8 c d 9 2 – We can take out an edge a 11 i 6 7 of a cycle, and still have all 8 vertices connected while reducing the cost h g 1 • 7 e 14 4 10 2 f # of edges in a MST: – |V| - 1 CS 477/677 - Lecture 24 12

Growing a MST Minimum-spanning-tree problem: find a MST for a connected, undirected graph, with a weight function associated with its edges 8 b A generic solution: 4 • Build a set A of edges (initiallya 11 7 empty) 8 • Incrementally add edges to A suchh that they would belong to a MST • An edge (u, v) is safe for A if and only if A ⋃ {(u, v)} is also a subset of some MST CS 477/677 - Lecture 24 c 7 d 9 2 i 6 1 e 14 4 10 g 2 f We will add only safe edges 13

GENERIC-MST 1. A ← ∅ 2. while A is not a spanning tree 3. do find an edge (u, v) that is safe for A 4. A ← A ⋃ {(u, v)} 5. return A 4 11 a c 7 d 9 2 i 1 e 14 4 6 7 8 h • 8 b 10 g 2 f How do we find safe edges? CS 477/677 - Lecture 24 14

Finding Safe Edges • Let’s look at edge (h, g) – Is it safe for A initially? • Later on: 8 b 4 S 7 d 2 11 a c i h 1 9 e 14 4 6 7 8 V-S 10 g 2 f – Let S ⊂ V be any set of vertices that includes h but not g (so that g is in V - S) – In any MST, there has to be one edge (at least) that connects S with V - S – Why not choose the edge with minimum weight (h,g)? CS 477/677 - Lecture 24 15

Definitions • A cut (S, V - S) b is a partition of vertices into disjoint sets S and V - S • An edge crosses the 8 4 c 7 d 2 S a 11 i 7 V- S 8 cut h 1 9 e 14 4 6 10 g 2 f S V- S (S, V - S) if one endpoint is in S and the other in V – S • A cut respects a set A of edges ⟺ no edge in A crosses the cut • An edge is a light edge crossing a cut ⟺ its weight is minimum over all edges crossing the cut – For a given cut, there can be several light edges crossing it CS 477/677 - Lecture 24 16

Discussion In GENERIC-MST: • A is a forest containing connected components – Initially, each component is a single vertex • Any safe edge merges two of these components into one – Each component is a tree • Since an MST has exactly |V| - 1 edges: after iterating |V| - 1 times, we have only one component CS 477/677 - Lecture 24 17

The Algorithm of Kruskal • Start with each vertex being its own component • Repeatedly merge two components into one by choosing the light edge that connects them 8 b 4 7 d 9 2 11 a c i 6 7 8 h 1 e 14 4 10 g 2 f We would add edge (c, f) • Scan the set of edges in monotonically increasing order by weight • Uses a disjoint-set data structure to determine whether an edge connects vertices in different components CS 477/677 - Lecture 24 18

Operations on Disjoint Data Sets • MAKE-SET(u) – creates a new set whose only member is u • FIND-SET(u) – returns a representative element from the set that contains u – May be any of the elements of the set that has a particular property – E.g.: Su = {r, s, t, u}, the property may be that the element is the first one alphabetically FIND-SET(u) = r FIND-SET(s) = r – FIND-SET has to return the same value for a given set CS 477/677 - Lecture 24 19

Operations on Disjoint Data Sets • UNION(u, v) – unites the dynamic sets that contain u and v, say Su and Sv – E.g.: Su = {r, s, t, u}, Sv = {v, x, y} UNION (u, v) = {r, s, t, u, v, x, y} CS 477/677 - Lecture 24 20

KRUSKAL(V, E, w) 1. 2. 3. 4. 5. 6. 7. 8. 9. A← ∅ for each vertex v ∈ V do MAKE-SET(v) sort E into increasing order by weight w for each (u, v) taken from the sorted list do if FIND-SET(u) ≠ FIND-SET(v) then A ← A ⋃ {(u, v)} UNION(u, v) return A Running time: O(|E| lg|V|) – dependent on the implementation of the disjoint-set data structure CS 477/677 - Lecture 24 21

The Algorithm of Prim • The edges in set A always form a single tree • Starts from an arbitrary “root”: VA = {a} • At each step: 8 – Find a light edge crossing cut (VA, V - VA) b – Add this edge to A 4 a – Repeat until the tree spans all vertices 7 d 9 2 11 i h 1 e 14 4 6 7 8 • Greedy strategy c 10 g 2 f – At each step the edge added contributes the minimum amount possible to the weight of the tree CS 477/677 - Lecture 24 23

How to Find Light Edges Quickly? Use a priority queue Q: • Contains all vertices not yet included in the tree (V – VA) – V = {a}, Q = {b, h, c, d, e, f, g, i} 8 b 4 7 d 2 11 a c i h 1 • With each vertex v we associate a key: e 14 4 6 7 8 9 10 g 2 f key[v] = minimum weight of any edge (u, v) connecting v to a vertex in the tree – Key of v is ∞ if v is not adjacent to any vertices in VA – After adding a new node to VA we update the weights of all the nodes adjacent to it – We added node a ⇒ key[b] = 4, key[h] = 8 CS 477/677 - Lecture 24 24

PRIM(V, E, w, r) 1. Q← ∅ 2. for each u ∈ V 3. ∞ b 0 4 do key[u] ← ∞ 4. π[u] ← NIL 5. INSERT(Q, u) DECREASE-KEY(Q, r, 0) 7. while Q ≠ ∅ 8. 9. 10. 11. 12. h ∞ do u ← EXTRACT-MIN(Q) 7 ∞ d 2 1 9 ∞ e 14 4 6 7 8 6. ∞ i 11 a ∞ c 8 10 g ∞ 2 f ∞ 0 ∞∞ ∞∞∞∞∞∞ Q = {a, b, c, d, e, f, g, h, i} VA = ∅ for each v ∈ Adj[u] Extract-MIN(Q) ⇒ a do if v ∈ Q and w(u, v) < key[v] then π[v] ← u DECREASE-KEY(Q, v, w(u, v)) CS 477/677 - Lecture 24 25

Example ∞ b 4 ∞ 2 i 11 a h ∞ 1 4 b h 8 g ∞ ∞ c 2 1 ∞ e 7 4 f ∞ ∞ d 9 14 10 g ∞ 2 0 ∞∞ ∞∞∞∞∞∞ Q = {a, b, c, d, e, f, g, h, i} VA = ∅ Extract-MIN(Q) ⇒ a 6 7 8 9 10 ∞ 2 i 11 ∞ d 14 4 8 4 7 6 7 8 a ∞ c 8 f ∞ ∞ e key [b] = 4� [b] = a key [h] = 8� [h] = a 4 ∞∞∞∞∞8∞ Q = {b, c, d, e, f, g, h, i} VA = {a} Extract-MIN(Q) ⇒ b CS 477/677 - Lecture 24 26

Example 4 8 b 4 h 87 8 4 h 7 14 2 f 4 7 7 d 14 4 6 7 8 c 2 2 i 11 1 9 10 8 b d 4 g ∞ 6 1 4 a 7 6 7 8 7 c 2 2 i 11 a 8 g 6 2 2 f 4 ∞ e key [h] = 7� [h] = i key [g] = 6� [g] = i 7∞ 46 7 Q = {d, e, f, g, h} VA = {a, b, c, i} Extract-MIN(Q) ⇒ f key [g] = 2� [g] = f key [d] = 7� [d] = c unchanged 9 ∞10 key [e] = 10 � [e] = f e 7 10 2 7 10 Q = {d, e, g, h} VA = {a, b, c, i, f} CS 477/677 - Lecture 24 28 Extract-MIN(Q) ⇒g

Example 8 4 8 b 4 h 7 1 4 8 4 h 1 2 1 e f 2 4 8 7 c 7 d 9 10 g 2 2 f 4 10 e 14 4 6 7 8 10 10 2 2 i 11 a 9 14 4 g 1 b d 6 7 8 7 c 2 2 i 11 a 7 key [h] = 1� [h] = g 7 10 1 Q = {d, e, h} VA = {a, b, c, i, f, g} Extract-MIN(Q) ⇒ h 7 10 Q = {d, e} VA = {a, b, c, i, f, g, h} Extract-MIN(Q) ⇒ d CS 477/677 - Lecture 24 29

Example 8 4 8 b 4 2 2 i 11 a h 1 7 d 1 9 9 10 e 14 4 6 7 8 c 7 10 g 2 2 f 4 key [e] = 9 � [e] = d 9 Q = {e} VA = {a, b, c, i, f, g, h, d} Extract-MIN(Q) ⇒ e Q = ∅ VA = {a, b, c, i, f, g, h, d, e} CS 477/677 - Lecture 24 30

PRIM(V, E, w, r) 1. Q← ∅ 2. for each u ∈ V 3. Total time: O(VlgV + ElgV) = O(ElgV) do key[u] ← ∞ O(V) if Q is implemented as a min-heap 4. π[u] ← NIL 5. INSERT(Q, u) 6. DECREASE-KEY(Q, r, 0) 7. while Q ≠ ∅ 8. 9. 10. 11. 12. ► key[r] ← 0 Executed V do u ← EXTRACT-MIN(Q) times Takes O(lgV) Min-heap operations: O(VlgV) for each v ∈ Adj[u] Executed O(E) times do if v ∈ Q and w(u, v) < key[v] Constant O(ElgV) then π[v] ← u Takes DECREASE-KEY(Q, v,O(lgV) w(u, v)) CS 477/677 - Lecture 24 31

Theorem • Let A be a subset of some MST, (S, V - S) be a cut that respects A, and (u, v) be a light edge crossing (S, V - S). Then (u, v) is safe for A. S Proof: • Let T be a MST that includes A – Edges in A are shaded • Assume T does not include u the edge (u, v) • Idea: construct another MST T’v that includes A ⋃ {(u, v)} CS 477/677 - Lecture 24 V-S 32

Theorem – Proof • T contains a unique path p between u and v • (u, v) forms a cycle with edges on p S • (u, v) crosses the cut ⇒ path p x must cross the cut (S, V - S) at least once: let (x, y) be that edge u y p • Let’s remove (x, y) ⇒ breaks T into v two components. V-S • Adding (u, v) reconnects the components T’ = T - {(x, y)} ⋃ {(u, v)} CS 477/677 - Lecture 24 33

Theorem – Proof (cont.) T’ = T - {(x, y)} ⋃ {(u, v)} Have to show that T’ is a MST: S • (u, v) is a light edge ⇒ w(u, v) ≤ w(x, y) x u y • w(T ’) = w(T) - w(x, y) + w(u, v) p ≤ w(T) v V-S • Since T is a minimum spanning tree: w(T) ≤ w(T ’) ⇒ T’ must be an MST as well CS 477/677 - Lecture 24 34

Theorem – Proof (cont.) Need to show that (u, v) is safe for A: i.e., (u, v) can be a part of a MST S • A ⊆ T and (x, y) ∉ A ⇒ A ⊆T’ x • A ⋃ {(u, v)} ⊆ T’ • Since T’ is an MST ⇒ (u, v) is safe for A u y p v V-S CS 477/677 - Lecture 24 35