python
Part A: Goal vertices Modify the functions dfs.traversal and bfs.traversal such that they accept an optional third parameter goals with default value an empty collection (set() or I). The behaviour of both traversal functions should be such that the traversal should be stopped as soon as one of the goal vertices is visited. For example: >>> graphs.print_grid_traversal (g, 10, bfs_traversal (g, 0, {12))) 000---001---002 1 1 ***---*** ***---*** ***---***---*** ***---***---003-=-***---***-- 1 I *** -***---***---*** 1 1 *** *** *** 1 ***---*** ******** ! *** 1 ***---***---***---*** 1 ***---*** *** -***---***---*** Can you find inputs (by varying the input graph, the starting vertex and/or the goal vertices) such that the bfs traversal is longer than the dfs traversal and vice versa? You can use the functionality from the graphs module to generate other graphs and optionally add/remove individual edges by modifying the adjacency matrices. Part B: Path to goal Write new functions dfs.path and bfs path that take the same arguments as dfs.traversal and bfs traversal but that, instead of returning the entire traversal, they only return the path from the start vertex to the goal vertex that has been reached. For example: ***-*** *** >>> print_grid_traversal(g, 10, dfs_traversal (g, 0, {9, 39))) 000---001---002 ***---*** ***---***---*** 1 1 1 1 ***---***---003---025---026---027---029---033---035 *** 1 1 1 1 1 022---018---004---016---017 028 030 034 036 1 1 1 1 1 023 019 005---006---008---015 031---032 037---038 1 1 1 1 024 020---021 007 009---010---011---012---013---014 >>> print-grid_traversal(g, 10, dfs_path(g, 0, {9, 39})) 000---001---002 ***---*** ***---*** ***---***---*** 1 1 1 1 1 ***---***---003---004---005---006---007---008---009 1 ! 1 1 1 *** 010 1 1 1 ---***- ***---*** 011---012 1 1 *** ** *** -*** *** Can you find inputs (by varying the input graph, the starting vertex and/or the goal vertices) such that the bfs path is shorter than the dfs path (although the corresponding dfs traversal is shorter than the bfs traversal)? Discuss your findings in a short text in the doc string at the end of your module file. Include visualisations of your discovered example inputs by copying the corresponding output of the print-grid_traversal function. def bfs_traversal(graph, s, goals=[): >>> g = graphs.ex_tree >>> bfs_traversal(g. O, {12}) [0, 1, 2, 12] >>> print_grid_traversal(g, 10, bfs_traversal(g, 0, [12])) 000---001---002 ***__ ***_. *** ***---***---*** ** ***---003--- 1 IIIII *** *** *** $$. III *** *** *** **** *** *** *** *** ***---** *** >>> print_grid_traversal(9, 10, bfs_traversal(g, O. [22])) 000---001 ---002 ***--- 11 I 1 1 ***---004---003---005-- 1 | | | | ***---***---006--- III *** *** *** . *** *** *** *** *** *** *** **___*** 11 *** *** *** ***---*** visited = 0 boundary = [s] while len(boundary) > 0: v = boundary.pop(0) visited += [v] for elem in visited: if elem not in goals: for w in neighbours(v, graph): if w not in visited and w not in boundary: boundary.append(w) return visited def dfs_traversal(graph, s, goals): >>> g = graphs.ex_tree >>> print_grid_traversal(g, 10, dfs_traversal(g, 0, [12])) 000---001---002 ** 1 1 1 --003- 1 . *** . .. . ... . ... ... ... >>> print_grid_traversal(g, 10, dfs_traversal(g, 0, [9, 40, 49])) 000---001---002 ***--- 1 1 1 *---003---** ---004--- 1 1 *** 005---006---008---*** *** *** 007 009---010---011---012---013---014 visited = 1) boundary = [s] while len(boundary) > 0: v = boundary.pop() visited += [v] for w in neighboursiv, graph): if w not in visited and w not in boundary: boundary.append(w) return visited def bfs_path(graph, s, goals=[]): ****** ### >>> g = graphs.ex_tree >>> print_grid_traversal(g, 10, bfs_path(g, 0, {22}}) 000---001 ---002 ***---*** I --003--- 1 ---004-- 1 1 1 1 1 *** *** *** ** ** ** .-*** 111111 pass def dfs_path(graph, s, goals=0): >>> g = graphs.ex_tree >>> print_grid_traversal(g, 10, dfs_path(g, 0, [9, 39])) 000---001---002 ***- 1 1 *---003---004---005---006---007---008---009 1 . *** 010 1 ***---*** 011---012 . 11 pass
