Question: 7. (10 points) Please apply Depth First Search (DFS) to the graph below and show two timestamps (u.d and u.fin the pseudocodes) of each
7. (10 points) Please apply Depth First Search (DFS) to the graph below and show two timestamps (u.d and u.fin the pseudocodes) of each vertex. Start from the vertex a and search in alphabetical order. DFS (G) I 2 3 4 5 6 for each vertex u G.V u.color = WHITE U. = NIL time=0 for each vertex u G.V if u.color == WHITE DFS-VISIT (G,u) b h C g DFS-VISIT (G. u) time u.d = time 1 2 3 4 time +1 u.color GRAY for each ve G.Adj[u] if v.color 5 6 7 8 9 time 10 u.f = time WHITE V.I=U DFS-VISIT (G,V) u.color= BLACK time +1 f
Step by Step Solution
3.42 Rating (155 Votes )
There are 3 Steps involved in it
To find the depth first order of the graph G starting from vertex a we can use a depthfirst search DFS algorithm The DFS algorithm starts at the starting vertex a and explores as far as possible along each branch before backtracking Heres the stepbystep process to perform DFS on the given graph G Start with the starting vertex a and mark it as visited Visit the first unvisited neighbour of a which is b Mark b as visited and add it to the DFS traversal path From b visit its first unvisited neighbour which is g Mark g as visited and add it to the DFS traversal path From g visit its first unvisited neighbour which is c Mark c as visited and add it to the DFS traversal path From c visit its first unvisited neighbour which is f Mark f as visited and add it to the DFS traversal path From f visit its first unvisited neighbour which is e Mark e as visited and add it to the DFS traversal path From e visit its next unvisited neighbour which is c c has already been visited so backtrack to g backtrack to b From b visit its unvisited neighbour which is h Mark h as visited and add it to the DFS traversal path From h backtrack to b then backtrack to a From a visit its next unvisited neighbour which is d Mark d as visited and add it to the DFS traversal path From d backtrack to a Therefore the depth first order starting from vertex a in alphabetical order is a b g c f ehd To find the start ... View full answer
Get step-by-step solutions from verified subject matter experts
Study Help