最小生成树

1 .CSE 373 : Data Structures & Algorithms Spanning Trees and Minimum Spanning Trees Riley Porter Winte r 2017 CSE373: Data Structures & Algorithms 1

2 .Course Logistics HW4 due tonight HW5 out t omorrow (more graphs!) coding: Dijkstra’s shortest path algorithm written: lots of practice with BFS, DFS, Topological Sort, and Spanning Trees (today!) Midterm regrades due by the end of this week 2 CSE373: Data Structures & Algorithms

3 .Problem Statement 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 3 CSE373: Data Structures & Algorithms

4 .Observations Problem not defined if original graph not connected. Therefore, we know | E| >= |V|-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 Solution not unique unless original graph was already a tree A tree with |V| nodes has |V|-1 edges So every solution to the spanning tree problem has |V|-1 edges 4 CSE373: Data Structures & Algorithms

5 .Motivation A spanning tree connects all the nodes with as few edges as possible In most compelling uses, we have a weighted undirected graph and we want a tree of least total cost Example: Electrical wiring for a house or clock wires on a chip Example: A road network if you cared about asphalt cost rather than travel time This is the minimum spanning tree problem Will do that next, after intuition from the simpler case 5 CSE373: Data Structures & Algorithms

6 .Two Approaches Different algorithmic approaches to the spanning-tree problem: Do a graph traversal (e.g., depth-first search, but any traversal will do), keeping track of edges that form a tree Iterate through edges; add to output any edge that does not create a cycle 6 CSE373: Data Structures & Algorithms

7 .Spanning tree via DFS 7 CSE373: Data Structures & Algorithms spanning_tree (Graph G) { for each node v : v. marked = false dfs ( someRandomStartNode ) } dfs (Vertex a ) { // recursive DFS a .marked = true for each b adjacent to a : if( ! b .marked ) { add ( a , b ) to output dfs ( b ) } } Correctness: DFS reaches each node in connected graph. We add one edge to connect it to the already visited nodes. Order affects result, not correctness. Runtime : O (|E|)

8 .Example dfs (1) 8 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output:

9 .Example dfs (1) Pending Callstack : dfs (2) dfs (5) dfs (6) 9 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output:

10 .Example 10 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2) dfs (2) Pending Callstack : dfs (7) dfs (3) dfs (5) dfs (6)

11 .Example dfs (7) Pending Calls tack : dfs (5) dfs (4) dfs (3) dfs (5) dfs (6) 11 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (2,7)

12 .Example dfs ( 5 ) Pending C allstack : dfs (4) dfs (6) dfs (4) dfs (3) dfs (6) 12 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (2,7), (7,5)

13 .Example dfs (4) Pending Callstack : dfs (3) dfs (6) dfs (3) 13 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (2,7), (7,5), (5,4)

14 .Example dfs (3) Pending Callstack : dfs (6) 14 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (2,7), (7,5), (5,4) , ( 4,3)

15 .Example dfs (6) Pending Callstack : 15 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (2,7), (7,5), (5,4), (4,3), (5,6)

16 .Example Bubble up the recursive callstack . Ignore each edge that would have been considered, but now is adjacent to a vertex already marked true. 16 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (2,7), (7,5), (5,4), (4,3), (5,6)

17 .Second Approach 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 The graph is connected, so we reach all vertices Efficiency: Depends on how quickly you can detect cycles Reconsider after the example 17 CSE373: Data Structures & Algorithms

18 .Example 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) 18 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output:

19 .Example 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) 19 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2)

20 .Example 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) 20 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4)

21 .Example 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) 21 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4), (5,6),

22 .Example 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) 22 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4), (5,6), (5,7)

23 .Example 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) 23 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4), (5,6), (5,7), (1,5)

24 .Example 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) 24 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4), (5,6), (5,7), (1,5)

25 .Example 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) 25 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4), (5,6), (5,7), (1,5)

26 .Example 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) 26 CSE373: Data Structures & Algorithms 1 2 3 4 5 6 7 Output: (1,2), (3,4), (5,6), (5,7), (1,5), (2,3) Can stop once we have |V|-1 edges

27 .Cycle Detection To decide if an edge could form a cycle is O ( |V| ) because we may need to traverse all edges already in the output So overall algorithm would be O ( |V||E| ) But there is a faster way we know: use union-find! Initially, each item is in its own 1-element set Union sets when we add an edge that connects them Stop when we have one set 27 CSE373: Data Structures & Algorithms

28 .Using Disjoint-Set Can use a disjoint-set implementation in our spanning-tree algorithm to detect cycles: Invariant: u and v are connected in output-so-far iff u and v in the same set Initially, each node is in its own set When processing edge ( u,v ) : If find(u) equals find(v) , then do not add the edge Else add the edge and union(find(u),find(v)) O ( |E| ) operations that are almost O (1) amortized 28 CSE373: Data Structures & Algorithms

29 .Summary So Far The spanning-tree problem Add nodes to partial tree approach is O ( |E| ) Add acyclic edges approach is almost O ( |E| ) Using union- find But really want to solve the minimum-spanning-tree problem Given a weighted undirected graph, give a spanning tree of minimum weight Same two approaches will work with minor modifications Both will be O ( |E| log |V| ) 29 CSE373: Data Structures & Algorithms