Understanding Minimum Spanning Trees in Graph Theory

Minimum Spanning Trees CSE 332 Sp25 Lecture 25

Announcements Monday Monday Veteran s Day Wed Wed Ex 13 (MST,prog) out Thursday Thursday Friday Friday TODAY TODAY Ex 12 (concurrency, GS) due final conflict form due final conflict form due Ex 14 due Tuesday Tuesday Ex 11 (prefix prog)due This Week Ex 14 (P/NP, GS) out Ex 13 due Next Week Final Exam information page is up. If you are requesting a conflict exam, please fill out form today!

Minimum Spanning Trees It s the 1920 s. Your friend at the electric company needs to choose where to build wires to connect all these cities to the plant. B 6 3 E 2 1 C 10 A 9 5 7 4 D 8 She knows how much it would cost to lay electric wires between any pair of locations, and wants the cheapest way to make sure electricity from the plant to every city.

Minimum Spanning Trees It s the 1920 s. Your friend at the electric company needs to choose where to build wires to connect all these cities to the plant. B 6 phone 1950 s boss phones to each other. 3 E 2 1 C 10 A 9 5 7 4 D F 8 phone She knows how much it would cost to lay electric wires between any pair of locations, and wants the cheapest way to make sure electricity from the plant to every city. Everyone can call everyone else.

Minimum Spanning Trees today It s the 1920 s. Your friend at the electric company needs to choose where to build wires to connect all these cities to the plant. B 6 ISP the Internet. 3 E 2 1 C 10 A 9 5 7 4 D 8 She knows how much it would cost to lay electric wires between any pair of locations, and wants the cheapest way to make sure Everyone can reach the server cable

Minimum Spanning Trees What do we need? A set of edges such that: -Every vertex touches at least one of the edges. (the edges span graph) -The graph on just those edges is connected -i.e. the edges are all in the same connected component. -A connected component is a vertex and everything you can reach from it. -The minimum weight set of edges that meet those conditions Claim: The set of edges we pick never has a cycle. Why? span the connected. connected component.

Aside: Trees On graphs our tees: -Don t need a root (the vertices aren t ordered, and we can start BFS from anywhere) -Varying numbers of children neighbors -Connected and no cycles Tree Tree (when talking about undirected graphs) (when talking about undirected graphs) An undirected, connected acyclic graph.

MST Problem What do we need? A set of edges such that: -Every vertex touches at least one of the edges. (the edges span -The graph on just those edges is connected -The minimum weight set of edges that meet those conditions. Our goal is a tree! Minimum Spanning Tree Problem Minimum Spanning Tree Problem span the graph) connected. Given Given: an undirected, weighted graph G Find Find: A minimum-weight set of edges such that you can get from any vertex of G to any other on only those edges. We ll go through two different algorithms for this problem.

Example Try to find an MST of this graph: B 6 3 E 2 1 C 10 A 9 5 7 4 D F 8

Prims Algorithm Algorithm idea: choose an arbitrary starting point. Add a new edge that: -Will let you reach more vertices. -Is as light as possible We d like each not-yet-connected vertex to be able to tell us the lightest edge we could add to connect it.

Code PrimMST(Graph G) initialize costs to mark source as cost 0 mark all vertices unprocessed foreach(edge (source, v) ) { v.cost = weight(source,v) } while(there are unprocessed vertices){ let u be the closest unprocessed vertex add u.bestEdge to spanning tree foreach(edge (u,v) leaving u){ if(weight(u,v) < v.cost){ v.cost = weight(u,v) v.bestEdge = (u,v) } } mark u as processed } }

50 G Try it Out 6 B PrimMST(Graph G) initialize costs to mark source as cost 0 mark all vertices unprocessed foreach(edge (source, v) ) { v.cost = weight(source,v) } while(there are unprocessed vertices){ let u be the closest unprocessed vertex add u.bestEdge to spanning tree foreach(edge (u,v) leaving u){ if(weight(u,v) < v.cost){ v.cost = weight(u,v) v.bestEdge = (u,v) } } mark u as processed } } E 2 3 4 C 5 A 9 2 7 7 F D 8 Vertex Vertex Cost A B C D E F G Cost Best Edge Best Edge Processed Processed

50 G Try it Out 6 B PrimMST(Graph G) initialize costs to mark source as cost 0 mark all vertices unprocessed foreach(edge (source, v) ) { v.cost = weight(source,v) } while(there are unprocessed vertices){ let u be the closest unprocessed vertex add u.bestEdge to spanning tree foreach(edge (u,v) leaving u){ if(weight(u,v) < v.cost){ v.cost = weight(u,v) v.bestEdge = (u,v) } } mark u as processed } } E 2 3 4 C 5 A 9 2 7 7 F D 8 Vertex Vertex Cost A B C D E F G Cost -- 2 4 7 2 6 5 3 50 Best Edge Best Edge -- (A,B) (A,C) (A,D)(C,D) (B,E)(C,E) (B,F) (B,G) Processed Processed Yes Yes Yes Yes Yes Yes Yes

PrimMST(Graph G) initialize costs to mark source as cost 0 mark all vertices unprocessed //and add to priority queue foreach(edge (source, v) ) { v.cost = weight(source,v) } while(there are unprocessed vertices){ let u be the closest unprocessed vertex //removeMin add u.bestEdge to spanning tree foreach(edge (u,v) leaving u){ if(weight(u,v) < v.cost){ v.cost = weight(u,v) //updatePriority!! v.bestEdge = (u,v) } } mark u as processed } } Running time: (? log?) Analysis same as Dijkstra, but can assume ? ? 1

Some Exercise Notes We ll ask you to implement Prim s in Exercise 13. You have a few options for the priority queue: 1. Use a Java library priority queue---but it doesn t have updatePriority() so you ll need a workaround: A. Add edges instead of vertices to the priority queue OR B. Allow multiple copies of each vertex into the queue (instead of decreasing priority, put in a second copy at the new priority OR 2. Use your (Exercise 2) priority queue instead---call updatePriority! Will these change the running time? No! log ? = log ? for simple graphs. Read the paragraph in the spec about this before you get too far. Also see alternate version of pseudocode in section slides tomorrow.

Does This Algorithm Always Work? Prim s Algorithm is a greedy edge in the MST it never reconsiders its decision. Greedy algorithms rarely work. There are special properties of MSTs that allow greedy algorithms to find them. greedy algorithm. Once it decides to include an In fact MSTs are so magical that there s more than one greedy algorithm that works.

Why do all of these MST Algorithms Work? MSTs satisfy two very useful properties: Cycle Property: Cycle Property: The heaviest edge along a cycle is NEVER part of an MST. Cut Property: Cut Property: Split the vertices of the graph any way you want into two sets A and B. The lightest edge with one endpoint in A and the other in B is ALWAYS part of an MST. Whenever you add an edge to a tree you create exactly one cycle, you can then remove any edge from that cycle and get another tree out. This observation, combined with the cycle and cut properties form the basis of all of the greedy algorithms for MSTs.

Does This Algorithm Always Work? Prim s Algorithm is a greedy edge in the MST it never reconsiders its decision. Greedy algorithms rarely work. There are special properties of MSTs that allow greedy algorithms to find them. greedy algorithm. Once it decides to include an In fact MSTs are so magical that there s more than one greedy algorithm that works.

A different Approach Prim s Algorithm started from a single vertex and reached more and more other vertices. Prim s thinks vertex by vertex (add the closest vertex to the currently reachable set). What if you think edge by edge instead? Start from the lightest edge; add it if it connects new things to each other (don t add it if it would create a cycle) This is Kruskal s Algorithm.

Kruskals Algorithm KruskalMST(Graph G) initialize each vertex to be a connected component sort the edges by weight (increasing) foreach(edge (u, v) in sorted order){ if(u and v are in different components){ add (u,v) to the MST Update u and v to be in the same component } }

B Try It Out 6 3 E 2 KruskalMST(Graph G) initialize each vertex to be a connected component sort the edges by weight foreach(edge (u, v) in sorted order){ if(u and v are in different components){ add (u,v) to the MST Update u and v to be in the same component } } Edge Edge Include? Include? Reason (A,C) (C,E) (A,B) (A,D) (C,D) 1 C A 10 7 9 5 4 D F 8 Edge (cont.) Edge (cont.) (B,F) (D,E) (D,F) (E,F) (C,F) Inc Inc? ? Reason Reason Reason

B Try It Out 6 3 E 2 KruskalMST(Graph G) initialize each vertex to be a connected component sort the edges by weight foreach(edge (u, v) in sorted order){ if(u and v are in different components){ add (u,v) to the MST Update u and v to be in the same component } } Edge Edge Include? Include? Reason (A,C) Yes (C,E) Yes (A,B) Yes (A,D) Yes (C,D) No 1 C A 10 7 9 5 4 D F 8 Edge (cont.) Edge (cont.) (B,F) (D,E) (D,F) (E,F) (C,F) Inc Inc? ? Yes No No No No Reason Reason Reason Cycle A,C,E,D,A Cycle A,D,F,B,A Cycle A,C,E,F,D,A Cycle C,A,B,F,C Cycle A,C,D,A

Kruskals Algorithm: Running Time KruskalMST(Graph G) initialize each vertex to be a connected component sort the edges by weight foreach(edge (u, v) in sorted order){ if(u and v are in different components){ add (u,v) to the MST Update u and v to be in the same component } }

Kruskals Algorithm: Running Time How do we find connected components? Well BFS is our existing tool to do that, but Running a new BFS in the partial MST, at every step seems inefficient. The answer changes little by little, so we ll recompute work frequently. Do we have an ADT that will work here?

Union-Find Crash Course Union-Find ADT aka Disjoint Sets Represents well disjoint sets. state state Set of Sets - Disjoint: Disjoint: No element appears in multiple sets - No required order - Each set has representative behavior behavior makeSet(x) creates a new set where the only member (and the representative) is x. findSet(x) looks up the set containing element x, returns name of that set union(x, y) combines sets containing x and y. Picks new name for combined set.

Union-Find Running Time What s important for us? Amortized running times! We care about the total time across the entire set of unions and finds, not the running time of just one. Operation Operation Worst Worst- -case Amortized Amortized case Worst Worst- -case Non Non- -amortized amortized case MakeSet() Union() Find() (1) ?(log ?) ?(log ?) (1) ?(log?) ?(log?) Uses forest of up-trees implementation.

log? log ? the number of times you need to apply log() to get a number at most 1. E.g., log (16) = 3 log 16 = 4 log ? grows ridiculously log 1080 = 5. For all practical purposes these operations are constant time. They re not constants (don t delete them from big-O notation), but you will never worry about these in figuring out how many seconds a piece of code takes. log 4 = 2 ridiculously slowly. log 2 = 1.

Using Union-Find Have each disjoint set represent a connected component -A connected component is a piece of a (disconnected) undirected graph -i.e. a vertex, and everything you can reach from that vertex. When you add an edge, you union union those connected components.

Try it Out KruskalMST(Graph G) initialize each vertex to be a connected component sort the edges by weight foreach(edge (u, v) in sorted order){ if(find(u) != find(v)){ add (u,v) to the MST union(find(u),find(v)) } } 50 G 6 B E 2 3 4 C 5 A 9 2 7 7 F D 8

Running Time? KruskalMST(Graph G) initialize each vertex to be a connected component sort the edges by weight foreach(edge (u, v) in sorted order){ if(find(u) != find(v)){ add (u,v) to the MST union(find(u),find(v)) } } ? log? is the dominant term, but you ll usually see this written (? log?) Since ? ?2, those are equivalent. ? log? ? log ? 50 G 6 B ? E 2 3 ? log ? 4 C 5 A 9 2 7 7 F D 8

Try it Out Edge Edge Include? Include? Reason Reason 50 G 6 B E 2 3 4 C 5 A 9 2 7 7 F D 8

Try it Out Edge Edge (A,B) (C,D) (B,F) (A,C) (C,E) (B,E) (A,D) (D,E) (D,F) (E,F) (B,G) Include? Include? Yes Yes Yes Yes Yes No No No No No Yes Reason Reason 50 G 6 B E 2 3 4 C 5 A 9 2 Cycle A,C,D,B,A Cycle A,D,C Cycle C,D,E Cycle A,B,F,D,C,A Cycle E,F,B,A,C,E 7 7 F D 8

Some Extra Comments Prim was the employee at Bell Labs in the 1950 s The mathematician in the 1920 s was Boruvka -He had a different also greedy algorithm for MSTs. -Boruvka s algorithm is trickier to implement, but is useful in some cases. -In particular it s the basis for fast parallel parallel MST algorithms. If all the edge weights are distinct, then the MST is unique. If some edge weights are equal, there may be multiple spanning trees. Prim s/Kruskal s are only guaranteed to find you one of them.

Aside: A Graph of Trees A tree is an undirected, connected, and acyclic graph. How would we describe the graph Kruskal s builds. It s not a tree until the end. It s a forest! A forest is any undirected and acyclic graph

EVERY TREE IS A FOREST.

Two More Simple Graph Algorithms

Ordering Dependencies Today s next problem: Given a bunch of courses with prerequisites, find an order to take the courses in. CSE 331 Math 126 CSE 143 CSE 142 CSE 311 CSE 332

Ordering Dependencies Given a directed graph G, where we have an edge from u to v if u must happen before v. Can we find an order that respects dependencies respects dependencies? Topological Sort (aka Topological Ordering) Topological Sort (aka Topological Ordering) Given: Given: a directed graph G Find: Find: an ordering of the vertices so all edges go from left to right. Uses: Compiling multiple files Graduating.

Topological Ordering A course prerequisite chart and a possible topological ordering. CSE 331 Math 126 CSE 143 CSE 142 CSE 311 CSE 332 Math 126 CSE 331 CSE 332 CSE 311 CSE 142 CSE 143

Can we always order a graph? Can you topologically order this graph? A B C Directed Acyclic Graph (DAG) Directed Acyclic Graph (DAG) A directed graph without any cycles. A graph has a topological ordering if and only if it is a DAG.

Ordering a DAG Does this graph have a topological ordering? If so find one. C D A B E

Ordering a DAG Does this graph have a topological ordering? If so find one. C D A B E If a vertex doesn t have any edges going into it, we can add it to the ordering. More generally, if the only incoming edges are from vertices already in the ordering, it s safe to add.

How Do We Find a Topological Ordering? TopologicalSort(Graph G, Vertex source) count how many incoming edges each vertex has Collection toProcess = new Collection() foreach(Vertex v in G){ if(v.edgesRemaining == 0) toProcess.insert(v) } topOrder = new List() while(toProcess is not empty){ u = toProcess.remove() topOrder.insert(u) foreach(edge (u,v) leaving u){ v.edgesRemaining-- if(v.edgesRemaining == 0) toProcess.insert(v) } }

Whats the running time? TopologicalSort(Graph G, Vertex source) count how many incoming edges each vertex has Collection toProcess = new Collection() foreach(Vertex v in G){ if(v.edgesRemaining == 0) toProcess.insert(v) } topOrder = new List() while(toProcess is not empty){ u = toProcess.remove() topOrder.insert(u) foreach(edge (u,v) leaving u){ v.edgesRemaining-- if(v.edgesRemaining == 0) toProcess.insert(v) } } Running Time: ?( ? + ? )

Finding a Topological Ordering Instead of counting incoming edges, you can actually modify DFS to find you one (think about why). But the count incoming edges is a bit easier to understand (for me )

Problem 2: Find Strongly Connected Components K A B D E C F J {A}, {B}, {C,D,E,F}, {J,K} Strongly Connected Component Strongly Connected Component A subgraph C such that every pair of vertices in C is connected via some path in both directions, in both directions, and there is no other vertex which is connected to every vertex of C in both directions.

Connectedness Definitions In an undirected graph, a connected component is a piece of the graph: a vertex and everything its connected to via a path. Equivalently, a subgraph C such that every pair of vertices in C is connected via some path and there is no other vertex which is connected to every vertex of C in both directions. In a directed graph, you might care about Weakly connected components (ignore the directions on the edges, if it were undirected, would it be connected?) Strongly connected (can you get in both directions)

Can you find Strongly Connected Components? A couple of different ways to use DFS to find strongly connected components. Wikipedia has the details. High level: need to keep track of highest point in DFS tree you can reach back up to. Similar idea on undirected graphs on HW2. What do you need to know? On a small graph, find the SCC by hand Know that you can modify DFS to find SCCs in ? + ? time.

Optional: Graph practice

Designing New Algorithms When you need to design a new algorithm on graphs, whatever you do is probably going to take at least (? + ?) time. So you can run any ?(? + ?)algorithm as preprocessing Finding connected components (undirected graphs) Finding SCCs (directed graphs) Do a topological sort (DAGs)