Graph traversal anhtt-fit@mail.hut.edu.vn Graph Traversal We need also algorithm to traverse a graph like for a tree Graph traversal may start at an arbitrary vertex. (Tree traversal generally starts at root vertex) Two difficulties in graph traversal, but not in tree traversal: The graph may contain cycles; The graph may not be connected. There are two important traversal methods: Breadth-first traversal, based on breadthfirst search (BFS). Depth-first traversal, based on depth-first search (DFS). 1 Breadth-First Search Traversal Breadth-first traversal of a graph: Is roughly analogous to level-by-level traversal of an ordered tree Start the traversal from an arbitrary vertex; Visit all of its adjacent vertices; Then, visit all unvisited adjacent vertices of those visited vertices in last level; Continue this process, until all vertices have been visited. 0 8 9 2 source 0 4 3 5 7 1 4 3 6 9 2 source 1 8 7 5 6 Breadth-First Traversal The pseudocode of breadth-first traversal algorithm: BFS(G,s) for each vertex u in V do visited[u] = false Report(s) visited[s] = true initialize an empty Q Enqueue(Q,s) While Q is not empty do u = Dequeue(Q) for each v in Adj[u] do if visited[v] = false then Report(v) visited[v] = true Enqueue(Q,v) 2 An Example Breadth-First Search Traversal Example of breadth-first traversal Visit the first vertex (in this example 0) Visit its adjacent nodes in Adj[0] :7 5 2 1 6 Visit adjacent unvisited nodes of the those visited in last level Visit adjacent unvisited nodes of the those visited in last level Visit adjacent nodes of 7 in Adj[7] : 4 Visit adjacent nodes of 5 in Adj[5] : 3 Visit adjacent nodes of 2 in Adj[2] : none Visit adjacent nodes of 1 in Adj[1] : none Visit adja