Government & Politics

Directed Acyclic Graphs and Strongly Connected Components. CSE 101: Design and Analysis of Algorithms Lecture 3

Description
Directed Acyclic Graphs and Strongly Connected Components CSE 101: Design and Analysis of Algorithms Lecture 3 CSE 101: Design and analysis of algorithms Directed acyclic graphs and strongly connected
Published
of 53
1
Published
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
Directed Acyclic Graphs and Strongly Connected Components CSE 101: Design and Analysis of Algorithms Lecture 3 CSE 101: Design and analysis of algorithms Directed acyclic graphs and strongly connected components Reading: Sections 3.3 and 3.4 Homework 1 due Oct 9, 11:59 PM CSE 101, Fall Max bandwidth path Graph represents network, with edges representing communication links. Edge weights are bandwidth of link. 6 A F D 5 7 B What is the largest bandwidth of a path from A to H? 8 G E 9 7 C 6 H Based on slides courtesy of Miles Jones CSE 101, Fall Problem statement Instance: Directed graph G= (V, E) with positive edge weights w(e), two vertices s, t Solution type: A path p in G Restriction: The path must go from s to t Bandwidth of a path BW Objective: Over all possible paths between s and t, find the maximum BW CSE 101, Fall Results from last lecture groups Two kinds of ideas Modify an existing algorithm (depth first search, breadth first search, Dijkstra s algorithm) Use an existing algorithm (depth first search) as a sub routine (possibly modifying the input when you run the algorithm) CSE 101, Fall Approaches modifying algorithms Use a stack as in depth first search, but instead of keeping just a vertex, the stack has pairs (V, B), where B is the current bandwidth of A path from s to V. Also, keep an array with the best known bandwidth of paths to each u. When you explore from (V,B), compare the current best bandwidth to each neighbor u with the smaller of B and w((v,u)). If the bandwidth to u improves, update the array and push u with the improved bandwidth. CSE 101, Fall Example where this method is quadratic time CSE 101, Fall Example where this method is quadratic time CSE 101, Fall Modifying algorithms Use depth first search, but instead of searching vertices in order of their index, order them by the weight of the edges coming into them CSE 101, Fall Problematic instance CSE 101, Fall Problematic instance CSE 101, Fall Modifying Dijkstra s algorithm Use a priority queue as in Dijkstra s algorithm, but using a max heap keyed by the best bandwidth of a path to v. You explore the highest bandwidth v, and increase the keys for neighbors u with w((v,u)) if higher than the current key. This is a good approach, but we ll defer discussion until after reviewing Dijkstra s algorithm (next week) CSE 101, Fall Using graph search as subroutine Keep on removing the smallest weight edge until there is no path from s to t. The weight of the last removed edge is the bandwidth. Find some path from s to t using depth first search. Remove all edges whose weight is at most the smallest weight of an edge in this path and repeat until no path is found. The last edge removed is the bandwidth. CSE 101, Fall Related approach Add edges from highest weight to lowest, stopping when there is a path from s to t CSE 101, Fall A B C F G H D E What is the largest bandwidth of a path from A to H? 6 Reducing to graph search These approaches use reductions We are using a known algorithm for a related problem to create a new algorithm for a new problem Here, the known problem is graph search or graph reachability The known algorithms for this problem include depth first search and breadth first search In a reduction, we map instances of one problem to instances of another. We can then use any known algorithm for that second problem as a sub routine to create an algorithm for the first. CSE 101, Fall Graph reachability Given a directed graph G and a start vertex s, produce the set X V of all vertices v reachable from s by a directed path in G CSE 101, Fall Reduction from a decision version Reachability is Boolean Yes it is reachable, no it is not MaxBandwidth is optimization What is the best bandwidth path? To show the connection, let s look at a decision version of max bandwidth path Decision version of MaxBandwidth Given G, s, t, and B, is there a path of bandwidth B or better from s to t? CSE 101, Fall Max bandwidth path Say B = 7, and we want to decide whether there is a bandwidth 7 or better path from A to H. Which edges could we use in such a path? Can we use any such edges? 6 A F D 5 7 B 8 G E 9 7 CSE 101, Fall C 6 H Decision to reachability Let Lemma: There is a path from s to t of bandwidth at least B if and only if there is a path from s to t in Proof: If p is a path of bandwidth BW B, then every edge in p must have w(e) B and so is in. Conversely, if there is a path from s to t with every edge in, the minimum weight edge e in that path must be in, so BW(p)= w(e) B As such, to decide the decision problem, we can use reachability Construct by testing each edge. Then use reachability on s, t, CSE 101, Fall Decision to reachability Let Lemma: There is a path from s to t of bandwidth at least B if and only if there is a path from s to t in Proof: If p is a path of bandwidth BW B, then every edge in p must have w(e) B and so is in. Conversely, if there is a path from s to t with every edge in, the minimum weight edge e in that path must be in, so BW(p)= w(e) B As such, to decide the decision problem, we can use reachability Construct by testing each edge. Then use reachability on s, t, CSE 101, Fall Reducing optimization to decision Suggested approach: if we can test whether the best is at least B, we can find the best value by starting at the largest possible one, and reducing it until we get a yes answer Here, possible bandwidths = weights of edges In our example, this is the list: 3, 5, 6, 7, 8, 9 Is there a path of bandwidth 9? If not, then Is there a path of bandwidth 8? If not, then Is there a path of bandwidth 7? If not, then CSE 101, Fall Time for this approach Let n= V, m= E From previous classes, we know depth first search, breadth first search both time O(n+m) When we run it on, no worse than running on E, since In the above strategy, how many depth first search runs do we make in the worst case? Each edge might have a different weight, and we might not find a path until we reach the smallest, so we might run DFS times What is the total time? Running an algorithm times means total time = CSE 101, Fall Time for this approach Let n= V, m= E From previous classes, we know depth first search, breadth first search both time O(n+m) When we run it on, no worse than running on E, since In the above strategy, how many depth first search runs do we make in the worst case? Each edge might have a different weight, and we might not find a path until we reach the smallest, so we might run depth first search times What is the total time? Running an algorithm times means total time = CSE 101, Fall Ideas for improvement Is there a better way we could search for the optimal value? CSE 101, Fall Binary search Create sorted array of possible edge weights See if there is a path of bandwidth at least the median value Is there a path of bandwidth 6? Yes If so, then look in the upper part of the values, if not, then the lower part, always testing the value in the middle Is there a path of bandwidth 8? No 6 7 Is there one of bandwidth 7? No. Therefore, best is 6 CSE 101, Fall Total time for binary search version How many depth first search runs do we need in this version, in the worst case? log m runs total = O(log n) runs What is the total time of the algorithm? Sorting array: O(m log n) with mergesort O(log n) runs of depth first search at O(n+m) time per run = O((n+m)log n) time Total: O((n+m) log n) CSE 101, Fall Total time for binary search version How many depth first search runs do we need in this version, in the worst case? log m runs total = O(log n) runs What is the total time of the algorithm? Sorting array: O(m log n) with mergesort O(log n) runs of depth first search at O(n+m) time per run = O((n+m) log n) time Total: O((n+m) log n) CSE 101, Fall Differences F is stack, last found is first explored Depth first search F is queue, first found is first explored Breadth first search F is priority queue based on total length Dijkstra s algorithm CSE 101, Fall Graph reachability procedure GraphSearch (G: directed graph, s: vertex) Initialize X = empty, F = {s}, U = V F. While F is not empty: Pick v in F. For each neighbor u of v: If u is not in X or F: move u from U to F. Move v from F to X. X: explored F: frontier (reached but have not yet explored) U: unreached Return X. CSE 101, Fall Graph reachability procedure GraphSearch (G: directed graph, s: vertex) Initialize X = empty, F = {s}, U = V F. While F is not empty: Pick v in F. For each neighbor u of v: If u is not in X or F: move u from U to F. Move v from F to X. Return X. Let s make F a stack and see what types of problems we can solve. The book implements a stack using a recursive algorithm: procedure explore(g = (V,E), s) visited(s)=true for each edge (s,u): if not visited(u): explore(g,u) CSE 101, Fall Graph reachability procedure explore (G: directed graph, s: vertex) Initialize F is a stack push(s,f) While F is not empty: v = head(f) if visited(v): pop(f) For each neighbor u of v: If not visited(u) push(u,f) visited(v) = True Let s make F a stack and see what types of problems we can solve. The book implements a stack using a recursive algorithm: procedure explore(g = (V,E), s) visited(s)=true for each edge (s,u): if not visited(u): explore(g,u) CSE 101, Fall Explore takes as input Explore A graph (directed or undirected) and an initial vertex The output is an array visited such that visited( ) is true if and only if is reachable from for all vertices CSE 101, Fall Keeping track of paths We only get information about if there is a path from s to another vertex. What if we want to know what those paths are? CSE 101, Fall Keeping track of paths procedure explore (G: directed graph, s: vertex) Initialize F is a stack push(s,f) prev(s) = null While F is not empty: v = head(f) if visited(v): pop(f) For each neighbor u of v: If not visited(u) push(u,f) prev(u) = v visited(v) = True We can include another array of information. Set prev(u) to be the parent of u in the depth-first search output tree We only get information about if there is a path from s to another vertex. What if we want to know what those paths are? procedure explore(g = (V,E), s) visited(s)=true for each edge (s,u): if not visited(u): prev(u) = s explore(g,u) CSE 101, Fall Keeping track of paths Example: explore A A B C D E F G H Note: when we do graph examples in this class, by default, if a vertex has more than one neighbor, then in the adjacency list, the neighbors are ordered alphabetically unless stated otherwise. I J K L CSE 101, Fall Keeping track of paths 4 Example: explore A A E B F 7 8 C G D H 9 10 Note: when we do graph examples in this class, by default, if a vertex has more than one neighbor, then in the adjacency list, the neighbors are ordered alphabetically unless stated otherwise. 5 6 I J K L A B C D E F G H I J K L prev: null A B G B A F G E I CSE 101, Fall Keeping track of paths Example: explore A A B C D A Depth-first search output tree E F G H B F C E G I J K L I D H J CSE 101, Fall Keeping track of paths Example: explore A A B C D A Depth-first search output tree E F G H B F C E G I J K L I D H J Back edges CSE 101, Fall Back edges in undirected graphs Definition: back edges in an undirected graph G that has been explored are edges in G that are not in the depth first search tree of G What do back edges tell you about the graph? Back edges tell you if there are cycles How do you know if an edge is a back edge? Each edge (u,v) is a back edge if prev(u) v and prev(v) u CSE 101, Fall Back edges in undirected graphs Definition: back edges in an undirected graph G that has been explored are edges in G that are not in the depth first search tree of G What do back edges tell you about the graph? Back edges tell you if there are cycles How do you know if an edge is a back edge? Each edge (u,v) is a back edge if prev(u) v and prev(v) u CSE 101, Fall Cycle edges Notice that removing a back edge will not disconnect the graph In fact, removing an edge that is in a cycle will not disconnect an undirected graph and removing an edge that is not in a cycle will disconnect an undirected graph CSE 101, Fall Connected undirected graphs Definition: An undirected graph G is connected if for every pair of vertices v,u in G, there exists a path from v to u explore only reaches one connected component of the graph, namely the set of vertices reachable from s To examine the rest of the graph, we need to restart explore on a vertex that has not been visited CSE 101, Fall Depth first search procedure explore (G: directed graph, s: vertex) Initialize F is a stack push(s,f) prev(s) = null While F is not empty: v = head(f) if visited(v): pop(f) For each neighbor u of v: If not visited(u) push(u,f) prev(u) = v visited(v) = True component(v) = cc procedure DFS (G) cc = 0 for each vertex v: visited(v) = false for each vertex v: if not visited(v): cc++ explore(g,v) procedure explore(g = (V,E), s) visited(s)=true for each edge (s,u): if not visited(u): prev(u) = s explore(g,u) CSE 101, Fall Depth first search Example A B D E C F procedure DFS (G) cc = 0 for each vertex v: visited(v) = false for each vertex v: if not visited(v): cc++ explore(g,v) G H I CSE 101, Fall Depth first search Example A B D E C F procedure DFS (G) cc = 0 for each vertex v: visited(v) = false for each vertex v: if not visited(v): cc++ explore(g,v) G H I A B C D E F G H I cc: prev: null A null A C B E A F CSE 101, Fall Depth first search on directed graphs A C E G B D F H CSE 101, Fall Depth first search on directed graphs A C E G B D F H CSE 101, Fall Pre and post numbers Pre and post numbers assign 2 integers to each vertex These correspond to the steps of when that vertex enters the stack and leaves the stack procedure DFS (G) cc = 0 clock = 1 for each vertex v: visited(v) = false for each vertex v: if not visited(v): cc++ explore(g,v) procedure explore(g = (V,E), s) visited(s)=true component(s)=cc previsit(s) for each edge (s,u): if not visited(u): prev(u) = s explore(g,u) postvisit(s) procedure previsit(v) pre(v)=clock clock++ procedure postvisit(v) post(v)=clock clock++ CSE 101, Fall Depth first search on directed graphs (reverse alphabetical order) A C E G B D F H CSE 101, Fall Depth first search on directed graphs (reverse alphabetical order) A C E G B D F H CSE 101, Fall Edge types (directed graph) Tree edge: solid edge included in the depth first search output tree Back edge: leads to an ancestor Forward edge: leads to a descendent Cross edge: leads to neither ancestor or descendent Note that back edge is slightly different in directed and undirected graphs CSE 101, Fall Edge types and pre/post numbers The different types of edges can be determined from the pre/post numbers for the edge is a tree/forward edge then is a back edge then is a cross edge then CSE 101, Fall Next lecture Strongly connected components and breadthfirst search Reading: Sections 3.4, 4.1, 4.2, and 4.3 CSE 101, Fall
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x