Instructor: Lilian de Greef Quarter: Summer 2017

Instructor: Lilian de Greef Quarter: Summer 2017

CSE 373: Data Structures and Algorithms Lecture 18: Minimum Spanning Trees (Graphs) Instructor: Lilian de Greef Quarter: Summer 2017 Today Spanning Trees Approach #1: DFS Approach #2: Add acyclic edges Minimum Spanning Trees Prims Algorithm Kruskals Algorithm Announcements Midterms I brought midterms with me, can get them after class Next week, will only have them at CSE220 office hours

Reminder: hw4 due on Friday! Spanning Trees & Minimum Spanning Trees For undirected graphs Introductory Example All the roads in Seattle are covered in snow. You were asked to shovel or plow snow from roads so that Seattle drivers can travel. Because you dont want to shovel/plow that many roads, what is the smallest set of roads to clear in order to reconnect Seattle? ! e e r T

g n i n n a p S Spanning Trees Goal: Given a connected undirected graph G=(V,E), find a minimal subset of edges such that G is still connected A graph G2 = (V,E2) such that G2 is connected and removing any edge from E2 makes G2 disconnected Observations 1. Any solution to this problem is a tree

Recall a tree does not need a root; just means acyclic For any cycle, could remove an edge and still be connected 2. Solution not unique unless original graph was already a tree 3. Problem ill-defined if original graph not connected So |E| >= |V|-1 4. A tree with |V| nodes has edges So every solution to the spanning tree problem has

edges Two Approaches Different algorithmic approaches to the spanning-tree problem: 1. Do a graph traversal (e.g., depth-first search, but any traversal will do), keeping track of edges that form a tree 2. Iterate through edges; add to output any edge that does not create a cycle Approach #1: Using DFS (Example) Do a graph traversal, keeping track of edges that form a tree Stack: 2 1 3

7 4 6 5 Output: Approach #1: Spanning Tree via DFS spanning_tree(Graph G) { for each node i: i.marked = false for some node i: f(i) } f(Node i) { i.marked = true for each j adjacent to i: if(!j.marked) {

add(i,j) to output f(j) // DFS } } Correctness: DFS reaches each node. We add one edge to connect it to the already visited nodes. Order affects result, not correctness. Time: Approach #2: Add Acyclic Edges (Example) Iterate through edges; add to output any edge that does not create a cycle Edges in some arbitrary order:

(1,2), (3,4), (5,6), (5,7), (1,5), (1,6), (2,7), (2,3), (4,5), (4,7) 2 1 3 7 4 6 5 Output: Approach #2: Add Acyclic Edges Iterate through edges; output any edge that does not create a cycle. Correctness (hand-wavy): Goal is to build an acyclic connected graph

When we add an edge, it adds a vertex to the tree Else it would have created a cycle The graph is connected, so we reach all vertices Efficiency: Depends on how quickly you can detect cycles ( Not covered: there is a way to detect these cycles at almost average O(1) ) Summary So Far The spanning-tree problem two approaches: Add nodes to partial tree approach Add acyclic edges approach More compelling: we have a weighted undirected graph and we want a spanning tree with minimum total weight a.k.a. the

spanning-tree problem Introductory Example: version 2 All the roads in Seattle are covered in snow. You were asked to shovel or plow snow from roads so that Seattle drivers can travel. Because you dont want to shovel/plow that many roads, what is the smallest set of roads to clear in order to reconnect Seattle? Because you want to do the minimum amount of effort, what is the shortest total distance to clear in order to reconnect Seattle? 2 A B 1 2

Minim 1 5 E 1 D 1 C 3

5 6 2 10 F G um Sp annin g Tree ! Minimum Spanning Tree: Example Uses

How to most efficiently lay out Telephone lines Electrical power lines Hydraulic pipes TV cables Computer networks (like the Internet!) Minimum Spanning Tree Algorithms The minimum-spanning-tree problem Given a weighted undirected graph, give a spanning tree of minimum weight Same two approaches, with minor modifications, will work Algorithm for Unweighted Graph Similar Algorithm for Weighted Graph Algorithm BFS for shortest path

(shortest path) DFS for spanning tree Algorithm (minimum spanning tree) Adding acyclic edges approach for spanning tree Algorithm (minimum spanning tree) Prims Algorithm: Idea Idea: Grow a tree by adding an edge from the known vertices to the unknown vertices. Pick the edge with the smallest weight that connects known to unknown.

Recall Dijkstra picked edge with closest known distance to source That is not what we want here Otherwise identical (!) Prims Algorithm: Pseudocode 1. For each node v, set v.cost = and v.known = false 2. Choose any node v a) Mark v as known b) For each edge (v,u) with weight w, set u.cost=w and u.prev=v 3. While there are unknown nodes in the graph a) Select the unknown node v with lowest cost b) Mark v as known and add (v, v.prev) to output c) For each edge (v,u) with weight w, if(w < u.cost) { u.cost = w; u.prev = v; }

Practice Time! Using Prims Algorithm starting at vertex A, whats the minimum spanning tree? a rt t s s t Le here A 2 B 1

2 1 vertex known? 5 1 D 1 C 5 6

2 10 E A 3 B G F A) (A,B), (A,C), (A,D), (D,E), (C,F), (E,G) B) (B,E), (C,D), (D,A), (E,D), (F, C), (G,E)

C) (B,A), (C,A), (D,A), (E,D), (F, C), (G,E) D) (B,A), (C,D), (D,A), (E,D), (F, C), (G,D) C D E F G cost prev (extra space for scratch-work) Prims Algorithm: Example tart Let s s

here vertex known? 2 A B 1 2 A 1

5 E 1 D 1 C 3 5 6 2

10 F G B C D E F G cost prev (extra space for scratch-work)

Analysis Correctness ?? A bit tricky Intuitively similar to Dijkstra Run-time Same as Dijkstra O(|E| log |V|) using a priority queue Costs/priorities are just edge-costs, not path-costs Kruskals Algorithm: Idea Idea: Grow a forest out of edges that do not grow a cycle, just like for the spanning tree problem. But now consider the edges in order by Kruskals Algorithm: Pseudocode 1. Sort edges by weight (better: put in min-heap)

2. Each node in its own set 3. While output size < |V|-1 Consider next smallest edge (u,v) If adding edge(u,v) doesnt introduce cycles, output (u,v) Example 2 A Edges in sorted order: 1: (A,D), (C,D), (B,E), (D,E) 2: (A,B), (C,F), (A,C) 3: (E,G) 5: (D,G), (B,D)

6: (D,F) 10: (F,G) Output: B 1 2 5 D 1 C 6

2 F 1 1 E 3 5 10 G (extra space for scratch-work) Kruskals Algorithm: Correctness

It clearly generates a spanning tree. Call it TK. Suppose TK is not minimum: Pick another spanning tree Tmin with lower cost than TK Pick the smallest edge e1=(u,v) in TK that is not in Tmin Tmin already has a path p in Tmin from u to v Adding e1 to Tmin will create a cycle in Tmin Pick an edge e2 in p that Kruskals algorithm considered after adding e1 (must exist: u and v unconnected when e1 considered) cost(e2) cost(e1) can replace e2 with e1 in Tmin without increasing cost! Keep doing this until Tmin is identical to TK TK must also be minimal contradiction!

Recently Viewed Presentations

  • Title in Arial bold Subhead in Arial - Saint Mary&#x27;s University

    Title in Arial bold Subhead in Arial - Saint Mary's University

    June 2009 Investment Performance Report at March 31, 2009 Saint Mary's University Pension Plan Yvan Breton, Montreal * * Agenda Market review - what happened in 2008 Performance review of SMU funds Active manager issues Managing risk Market Review What...
  • HMI Magnetic Field Products jsoc.stanford.edu

    HMI Magnetic Field Products jsoc.stanford.edu

    HMI Magnetic Field Products jsoc.stanford.edu Line-of-sight magnetic field will be computed from Doppler Velocity in two polarizations, as is done for MDI. Vector Field will be computed from Stokes parameters derived from an independent set of polarized filtergrams. After launch...
  • Epic / Epic Hero Notes - senff.weebly.com

    Epic / Epic Hero Notes - senff.weebly.com

    The Odyssey Epic / Epic Hero Notes * * * * * * * * * * * * * * * * * * * * * * Epic Definition An Epic is a long narrative poem that relates...
  • The Pearl by John Steinbeck

    The Pearl by John Steinbeck

    The Pearl by John Steinbeck Vocabulary Chapter 1 parable-short story that illustrates a moral attitude or religious principle pulque-thick fermented beverage made from the agave plant avarice - extreme greed indigent - poor; needy; impoverished Chapter 2 estuary - the...
  • Osmoregulation and Excretion - Bio Resource Site

    Osmoregulation and Excretion - Bio Resource Site

    Porocytes and flagella. Excretory Systems. Dispose of metabolic wastes. Regulate solute concentrations in the body. Transport epithelia arranged in tubes. 4 major processes. Filtration, pressure-filtering of body fluids producing a filtrate (water, salts, sugars, amino acids, N-wastes)
  • Changing Units in the Customary System - Gateway School District

    Changing Units in the Customary System - Gateway School District

    Changing Units in the Customary System COURSE 2 LESSON 4-8 A carpenter cuts a 4 ft 10 in. piece from an 8-ft board. What is the length in feet of the remaining piece? You need to subtract 4 ft 10...
  • &#x27;&#x27; L&#x27;arte di saper amare: viaggio terapeutico per guardare ...

    '' L'arte di saper amare: viaggio terapeutico per guardare ...

    "Se una persona mi ama, ci deve essere in lei qualcosa che non va" [Paul Watzlawick]; ... ma può essere considerata in connessione con l'esperienza di una carenza esistenziale propria dell'essere umano: la mancanza di sicurezza in questo mondo.
  • Anscombe&#x27;s Quartet

    Anscombe's Quartet

    Post-hoc Test. All post hoc tests use the same basic principle: They allow you to compare each group mean to each other group mean and determine if they are significantly different while controlling for the number of group comparisons being...