Task 3: Depth-First Search (DFS) [5 Marks] Now, imagine your rival, Gary, who was also sent to the Pokémon world, wants

[answerhappygod]

Task 3 Depth First Search Dfs 5 Marks Now Imagine Your Rival Gary Who Was Also Sent To The Pokemon World Wants 1 (40.62 KiB) Viewed 37 times

Task 3: Depth-First Search (DFS) [5 Marks] Now, imagine your rival, Gary, who was also sent to the Pokémon world, wants to become Pokémon master before you. He is planning to get to Victory Road using the DFS algorithm. Implement a DFS algorithm to determine the places he needs to visit to get to the victory road! Sample Pseudocode for the DFS implementation: (You are allowed to try different approaches with same or less time complexity, but the outputs must match) visited =[0]*noOfPlacesOrNodes printed = [] #this will store the graph traversing sequence DFS_VISIT (graph, node) DFS VISIT (graph, node) #This part is needed if the graph is disconnected. DFS (graph, endPoint) For each node in graph If node not visited #Driver Read data from input.txt and create a graph DFS(graph, '12') vasswww~~~==Ñ Sample Inputs: Same as Task 1 12 17 2 Do visited[int(node)-1] 1 printed.append(node) For each node in in graph[node] If node not visited 7 8 8 9 DFS VISIT (graph, node) Print "printed" list in a loop till you get the end point 10 11 NASAMONTO FOREN 3 4 5 11 6 7 7 8 11 9 10 10 11 12 Sample Output: Places: 1 2 3 4 7 11 12