Graph Traversal and Topological Sort 01 14 19 BFS DFS Topological Sort 1 Breadth First Search on Graphs The purposes of breadth first search are traversing all nodes in the graph calculating the minimum hop path from the source node to all other nodes The idea of the algorithm is to 01 14 19 start from a chosen node construct a tree BFS Tree traverse the tree in a breadth first manner 2 Data 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 algorithm 01 14 19 3 Breadth First Search Algorithm The 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 Q 3 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 1 Change the color of v from white to gray v color gray Add v into the FIFO Q end for Remove u from Q Change u s color from gray to black u color black Go back to step 3 5 6 7 01 14 19 4 01 14 19 BFS G s 1 for each u V G do initialization 2 u color white 3 u d Running time 4 u nil BFS visit each vertex 5 s color gray 6 s d 0 and each edge once 7 Q s initialize the Q O V E 8 while Q do 9 u head Q 10 for each v u adj do 11 if v color white 12 then v color gray 13 v d u d 1 14 v u 15 Enqueue Q v 16 Dequeue Q 17 u color black 5 Example Breadth First Search Algorithm r s t u 0 Q r s t u 1 0 2 t x v s r s 1 0 v w 2 1 2 y v w x t u r s t u 1 0 2 3 x 0 Q v w x s t u 1 0 2 v 1 2 w x 1 1 y r 01 14 19 1 y Q x v u 2 1 2 v w x Q r s r t x 1 1 2 2 2 2 2 y wr Q 2 2 3 y t u 0 2 3 2 1 2 3 v w x y Q 6 Time Complexity of BFS Theorem 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 01 14 19 7 Depth First Search Algorithm The 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 2 4 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 discovered 01 14 19 8 Depth First Search Algorithm The 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 discovered v fin time when the vertex is finished DFS G 1 for each u V G do initial node values 2 u color white 3 u nil 4 time 0 5 for each u V G do 6 if u color white 7 then DFS Visit u 01 14 19 Time O V E DFS Visit u 1 u color gray 2 u dsc time 3 for each v u adj do 4 if v color white 5 then v u 6 DFS Visit v 7 u color black 8 u fin time 9 Example Depth First Search Algorithm u 1 v w u 1 v 2 7 u 1 8 w F B 4 5 3 6 z x y z u 1 v2 w u 1 v 2 7 w 4 3 x y z B 4 5 3 6 x y z F v2 w F B 01 14 19 u 1 8 4 5 3 x y z v 2 7 w B 4 5 3 6 x y y v 2 7 z w 9 C B 4 5 3 6 10 x u 1 8 y v 2 7 z w 9 12 F u 1 3 6 x u 1 8 y w 9 C B 4 5 x F v 2 7 B C B 4 5 3 6 x y 1 8 2 7 9 12 4 5 3 6 10 11 10 11 B z z two trees 10 Time Complexity of DFS Theorem 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 01 14 19 11 Classification of edges in undirected graph Depth 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 01 14 19 12 Classification of Edges in Undirected Graph Theorem In 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 01 14 19 13 Topological Sort An Application of Depth First Search Algorithm Definition 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 Sort 1 Call DFS G to compute the finishing time v fin for all …
View Full Document
Unlocking...