7. (10 points) Please apply Depth First Search (DFS) to the graph below and show two...

Transcribed Image Text:

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 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

Answer rating: 100% (QA)

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 the full answer