* Monday: BFS, Dijkstra's algorithm. * Wednesday: Bellman/Ford. * Today: DFS (depth-first search), and applications. ----------------- Reminder: breadth-first search (BFS). Given: graph G, source vertex s. Find: every node reachable from s. Produces a tree such that all nodes at depth d in the tree are exactly d hops away from s in G. Put s at the root of the tree. Repeat until nothing else happens: * for every node u that's currently a leaf of the tree, for every node v that's a neighbor of u, add v as a child of u if v has not already been discovered. Or, an alternative perspective: enqueue(Q, s) while Q is not empty: u <- dequeue(Q) for every neighbor v of u if v is unexplored enqueue(Q, v) ----------------- Today: DEPTH-FIRST SEARCH (DFS). Given: graph G, source vertex s. Find: every node reachable from s. white -> gray -> black not explored --> fully explored DFS-Visit(u): time++. color u gray, set discovery[u] := time. for each v in Adj[u] that's white: // v's "parent" in the DFS forest is u. color v gray. DFS-Visit(v) color u black. time++. finished[u] := time. DFS(G): for every vertex u, if u is white, then DFS-Visit(u). ----------------- ----------------- Types of edges in DFS: -- tree edges. (u->v where u is v's parent in the DFS forest.) -- back edges. (u->x where x is an ancester in the forest.) -- forward edges. (u->x where x is a descendant in the forest.) -- cross edges. (other edges.) An example of DFS: 1: 2,3 2: 3,4 3: 4 4: 5 5: 1 6: 4 1->2, 2->3, 3->4, 4->5 tree edges. 5->1 back. 2->4, 1->3 forward. 6->4 cross. ----------------- BFS/DFS Basically the same thing -- just built on different data structures. 1. v := EXTRACT-NEXT(D). 2. Mark v as explored. 3. For every u where (v,u) in E, INSERT(u,D). BFS: D is a queue. DFS: D is a stack. ----------------- ----------------- TOPOLOGICAL SORT -->6.012 / 6.001 --> 6.002 --> 6.003 --> 6.013 | \__________ \ \ \-> 6.004 --> 6.033 |\ \ \---> 6.034 \ ---\ ->6.046 ---/ / 6.042 --> 6.045 topological ordering: given a partial order (i.e., a DAG), produce a linear orer consistent with it. (can't do it if it's not a DAG.) How do we find a topological ordering? TOPOLOGICAL-SORT(G): L := empty list. while the graph is not fully explored pick an arbitrary node u. perform a DFS starting from u. every time a node is finished, insert it into the front of L. return L. (aka perform DFS and sort by finishing time -- but faster.) running time: O(|E|+|V|). correctness: suppose not. Then L contains (u ... v) where v->u in G. But then when exploring v, must have inserted v before inserting u. But then we finished v before finishing u. And that's not what DFS does. ----------------- ----------------- STRONGLY CONNECTED COMPONENTS SCC(G): run DFS on G. (*) while the graph is not fully re-explored pick unreexplored node u with highest finishing time from (*) run DFS from u exploring edges _backwards_. return the set of nodes reachable from u. component graph: node for each SCC; directed edge from C to D if there's an edge from c in C to d in D. basically SCC does the following: run topological sort on the component graph of G. figure out what the components were. Claim #1: The component graph is a DAG. pf: all nodes in a cycle form an SCC! Claim #2: If C,D are different SCCs with C-->D. Then we finish the last node of C after we finish the last node of D in (*). pf: if explore D first, never get to C before finishing D. if explore C first, then fully explore D before finishing C. ==> If C,D are different SCCs with D-->C in backwards edges, then we have finish(D) no outgoing edges.) ----------------- How do you find a cycle in a graph using DFS? Classify all edges. There's a back edge iff there's a cycle. ----------------- How do you find shortest paths in a DAG? Okay, you have a directed graph that has no cycle in it. You want to find shortest paths in it. * topological sort the vertices. * for each vertex u, taken in the order of the topological sort: relax every edge u->v. Why does this work? * The topological sort must respect the order of the edges in every path from s to any node u. * Thus we relax the edges of the path in order. This implies correctness. ------------------ Recap of some other graph algorithms: MSTs: ---- * Kruskal's: sort the edges in increasing order. add next cheapest edge that does not create a cycle. How do we check for cycles? --> never add an edge within a component. --> maintain components using a disjoint-set data structure (union find). ==> O(E log E) = O(E log V). * Prim's: start from an arbitrary vertex v. at every step, find the cheapest edge that extends the current tree. Use a min-heap for set of nodes adjacent to the tree. --> when adding a new node (or v to start), insert all vertices adjacent. (may need to decrease key to do so if already present -- if so, can just delete.) --> each edge induces <= 2 insertions. --> each node induces <= 1 extraction. --> O(log E) = O(log V) each. --> O((E+V) log V) = O(E log V) total. Can use a Fibonacci heap instead ==> O(V log V). SINGLE-SOURCE SHORTEST PATH --------------------------- * Dijkstra -- **NONNEGATIVE EDGES ONLY** idea: some nodes have known distances, some have "best guesses". take the "best guess" closest to the frontier and draw it into the "known" section. Need a data structure that -- maintains node neighborhoods. -- can select minimum distance. * Each node brought inside the frontier exactly once. * May have to update all other distances when each node enters the frontier. Naive array implementation: O(V^2). Fibonacci heap: O(V log V + E). --> don't worry about the details of Fibonacci heaps. * BELLMAN-FORD -- negative edges okay. idea: as in Dijkstra, maintain a "best guess" of distance from s to every other node. initially, d(s,s) = 0 d(s,u) = +infty. try to "relax" every edge in the graph. if d(s,u) + weight(u,v) < d(s,v) then update. repeat |V|-1 rounds. round #1: only nodes incident to s will be updated. round #2: only nodes within distance two of s ... why does this work? --> after i relaxation rounds, we've found the best length-i path from s to u (or better). --> after |V|-1 rounds ==> done! O(VE) time total. ALL-PAIRS SHORTEST PATHS ------------------------ To compute a full shortest path matrix d(u,v) = length of shortest path from u to v? * run Bellman-Ford (or Dijkstra) |V| times, starting from every node. O(V^2 E). * next week in lecture: we'll do better.