Answer Happy

Task 2: Breadth-First Search (BFS) [5 marks] Since you are a genius and you have an idea of the BFS algorithm, you can calculate the least number of cities you need to visit to get to your destination, Victory Road. Implement a BFS algorithm to determine the places you need to visit to get to the victory road! Sample Pseudocode for the BFS implementation: (You are allowed to try different approaches with same or less time complexity, but the outputs must match) visited =[0]*noOfPlacesOrNodes, queue =[] BFS (visited, graph, node, endPoint) 12 17 1 •NNN33 3 10 10 10 10 100.000 2 #Driver Read data from input.txt and create a graph BFS(visited, graph, '1', '12') Sample Inputs: 2 2 5 5 6 6 7 8 8 9 Do visited[int(node)-1] 1 Do queue append(node) While queue not empty Dom pop() 10 11 2 8LLSHVAGAWN 6 Print m // [into output text file] If m= endPoint break 11 9 10 10 11 12 For each neighbour of m in graph If visited [int(neighbour)-1] = 0 Do visited[int(neighbour)-1] 1 Do queue append(neighbour) Sample Output: Places: 1 2 3 4 5 7 11 6 12