tailieunhanh - Graph traversal

Graph traversal is The graph may contain cycles, The graph may not be connected, There are two important traversal methods (Breadth-first traversal, based on breadth-first search (BFS); Depth-first traversal, based on depth-firstsearch (DFS)). | Graph traversal anhtt-fit@ 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 6 9 2 source 1 8 1 4 3 5 7 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 adjacent nodes of 6 in Adj[6] : none Visit adjacent nodes of 4 in Adj[4] : none Visit adjacent nodes of 3 in Adj[3] : none Done 3 Breadth-First Traversal Breadth-first traversal of a graph: - Implemented with .