Depth-First Search 1. 2. 3. From the given vertex, visit one of its adjacent vertices and leave others; Then visit one of the adjacent vertices of the previous vertex; Continue the process, visit the graph as deep as possible until: A visited vertex is reached; An end vertex is reached. Depth-First Traversal 1. 2. 3. 4. 5. 6. 7. Depth-first traversal of a graph: Start the traversal from an arbitrary vertex; Apply depth-first search; When the search terminates, backtrack to the previous vertex of the finishing point, Repeat depth-first search on other adjacent vertices, then backtrack to one level up. Continue the process until all the vertices that are reachable from the starting vertex are visited. Repeat above processes until all vertices are visited. 0 source 0 8 9 2 4 3 source 1 7 5 6 8 9 2 4 3 1 7 5 6 1 Algorithm The pseudocode of depth-first traversal algorithm: Boolean visited[V.size]; void DepthFirst(Graph G) { Vertex u; for each vertex u in V do visited[u] = false; for each vertex u in V do if visited[u] = false then RDFS(u); } void RDFS(Vertex u){ visited[u] = true; Visit(u); for each vertex w in Adj[u] do if visited[w] = false then RDFS(w); } Example: Depth-First Traversal An adjacent list of a graph: 2 Example: Depth-First Traversal Function calls of depth-first traversal of the graph visit 0 visit 7 (first on 0’s list) visit 1 (first on 7’s list) check 7 on 1’s list check 0 on 1’s list visit 2 (second on 7’s list) check 7 on 2’s list check 0 on 2’s list check 0 on 7’s list visit 4 (fourth on 7’s list) visit 6 (first on 4’s list) check 4 on 6’s list check 0 on 6’s list Example: Depth-First Traversal visit 5 (second on 4’s list) check 0 on 5’s list check 4 on 5’s list visit 3 (third on 5’s list) check 5 on 3’s list chec