Graph Traversal and Topological SortPowerPoint PresentationSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Topological Sort—Another O(n+m) Time Algorithm101/14/19Graph Traversal and Topological SortBFSDFSTopological Sort201/14/19Breadth-First Search on GraphsThe purposes of breadth-first search aretraversing all nodes in the graphcalculating the minimum hop path from the source node to all other nodesThe idea of the algorithm is tostart from a chosen nodeconstruct a tree (BFS Tree)traverse the tree in a breadth-first manner301/14/19Data Structures for Breadth-First SearchUse adjacency lists to represent the graphThe vertex u of a graph consists of fields•u.d: distance to the source vertex•u.color: {white, gray, black}•u.: pointer to u’s parent vertexUse a FIFO queue to store vertices under processing (gray). . .. . .. . .. . .A breadth-first search tree is constructed by the algorithm401/14/19Breadth-First Search AlgorithmThe idea of the algorithm is to construct a breadth-first tree:1. Consider all nodes white (unprocessed)2. Start from a given vertex s (source). Put s in a FIFO queue Q3. u := head(Q). If u = nil (Q empty) then return.4. for each v  u.adj do:If v.color = white (a white vertex is discovered), then Assign u as the parent of v: v. := u;The distance to the root is v.d = u.d + 1Change the color of v from white to gray: v.col or := grayAdd v into the FIFO Qend-for5. Remove u from Q6. Change u’s color from gray to black: u.color := blac k7. Go back to step 3.501/14/19BFS(G, s)1. for each u  V(G) do // initialization2. u.color := white3. u.d := 4. u.  := nil5. s.color := gray6. s.d := 07. Q := {s} // initialize the Q8. while Q   do9. u := head(Q)10. for each v  u.adj do 11. if v.color = white12. then v.color := gray13. v.d := u.d + 114. v. := u15. Enqueue(Q, v)16. Dequeue(Q)17. u.color := blackRunning time:BFS visit each vertex and each edge once:O(|V| + |E|)601/14/190Example: Breadth-First Search Algorithmr s t uv w x ysQ0101r s t uv w x ywQr1 110122r s t uv w x yrQtx1 2 2120122r s t uv w x ytQxv2 2 21201223r s t uv w x yxQvu2 2 312012233r s t uv w x yQ = ...701/14/19Time Complexity of BFSTheorem: Let n and m be the number of vertices and the number of edges in the graph, respectively. The time complexity of BFS is O(n+m).Each node will be entered to the queue and deleted from the queue exactly once: O(n)Each edge will be traversed exactly twice: O(m)801/14/19Depth-First Search AlgorithmThe idea of depth-first search algorithm is to go deeper whenever possible: 1. Start from any vertex u;2. Follow an unexplored edge to discover a new vertex v;3. repeat step 24. In step 3, if all edges of a vertex have been explored, the search “backtracks” to explore the edges leaving the vertex from which v was discovered901/14/19Depth-First Search AlgorithmThe depth-first algorithm searches deeper whenever possible. As extra information, the algorithm puts two timestamps in each vertex: v.dsc: time when the vertex is discoveredv.fin: time when the vertex is finishedDFS(G)1. for each u  V[G] do: // initial node values2. u.color := white3. u. := nil4. time := 05. for each u  V[G] do:6. if u.color = white7. then DFS-Visit(u)DFS-Visit(u)1. u.color := gray2. u.dsc := ++time;3. for each v  u.adj do4. if v.color = white5. then v. := u6. DFS-Visit(v)7. u.color := black8. u.fin := ++time;Time: O(|V| + |E|)1001/14/191/Example: Depth-First Search Algorithmu v wx y z1/4/2/3/u v wx y z1/4/52/3/u v wx y zB1/4/52/73/6u v wx y zB1/4/52/73/6u v wx y zBF1/84/52/73/6u v wx y zBF1/84/52/73/69/u v wx y zBFC1/84/52/73/69/10/u v wx y zBFC1/84/52/73/69/1210/11u v wx y zBFC1/84/52/73/69/1210/11two treesBB1101/14/19Time Complexity of DFSTheorem: Let n and m be the number of vertices and the number of edges in the graph, respectively. The time complexity of DFS is O(n+m).Each node will be pushed onto the stack (colored gray) and popped off from the stack (colored black) exactly once: O(n)Each edge will be traversed exactly twice: O(m)1201/14/19Classification of edges in undirected graphDepth-first search can be used to classify different kinds of edges:Tree edges: Edges in the depth-first forest. An edge (u, v) is in a tree if v is first discovered by exploring edge (u, v). Back edges are those edges (u, v) connecting a vertex u to an ancestor v (but not a parent) in a depth-first tree. A loop is then formed. A self-loop edge is considered as a back edge.Cross edges are all other edges. They go between different trees. They can go between vertices in the same tree as long as one vertex is not the descendant of the other.1301/14/19Classification of Edges in Undirected GraphTheoremIn a depth-first search of an undirected graph, every edge is either a tree edge or a back edge.Why?Any addition of a non tree edge will form a loop.1401/14/19Topological Sort: An Application of Depth-First Search AlgorithmDefinition: Given a directed, acyclic graph G = (V, E), a topological sort of G is a linear ordering of all its vertices, such that if G contains an edge (u, v), then u appears before v in the ordering.Note, if there is a cycle in G, linear ordering is not possible.Topological-Sort1. Call DFS(G) to compute the finishing time v.fin for all v2. When a vertex is colored black, insert it to a linked list3. return the linked list1501/14/19Topological Sort—Another O(n+m) Time AlgorithmFor each vertex v, define in-degree(v).We can compute the in-degrees of all vertices in O(V+E) time.Color all vertices white.If in-degree(v)=0, insert v into a queue Q.While Q is not empty{delete v from Q.For all edges (v, u) doin-degree(u)--;if in-degree(u)=0, insert u into Q;color v black;}If all vertices are black, the order they are deleted from Q form a topological sort.Otherwise, the graph has a