Problem 3: BFS/DFS [20 pts] In this problem you will have to describe the depth and breadth rst search trees calculated for particular graphs. Let...

Hi,

How would I solve Question 3)a) ?

I have the solution to Question 4)a) below which asks a very similar question but in slightly different contexts regarding the adjacency lists.

Thanks a lot!

• Attachment 1
• Attachment 2

Problem 3: BFS/DFS [20 pts] In this problem you will have to describe the depth and breadth first searchtrees calculated for particular graphs. Let graph G” be the n X 71 gridcontaining the n2 points (0,3),1: 0,. . . ,n7 1, j 2 0, . . . ,n7 1. Figure (A)illustrates Gs. Each point is connected to four neighbors: The one belowit, the one above it, the one to its left and the one to its right. Note thatsome points only have two or three neighbors, e_g., the four corner pointsonly have 2 neighbors and that the edge points (aside from the corners)each have three neighbors. The acjaceney list representation used is (M) = (M *1) a (M + 1) e (1' 7 113') % ((+111)- For example, the adjacency list re Jresentation for (1,1) in G6 is (1,1) :4 (1,0) 4} (1, 2) a (0,1) a (2, 1). (0,51' '(5,5) (0.5) (5,5) [015:(0,0). .(5.0) (0,0) (5.0) (0,0)(A) (B) (C)Sorne nodes will only have two or three neighbors; their adjacency listsshoulr be adjusted appropriately. For example (00) H (0,1) 4, (1,0) and (12,0) H (1,1) % (17 1,0) 4 (1+ 1,0) fori:1,...,n72. In what follows Describe the tree means (i) list the edges in the tree and(ii) sketch a diagram that illustrates how the tree looks. (a) Describe the tree produced by Depth First Search run on G).1starting at root 5 2 (0,0). Figure (B) illustrates the tree producedfor GE. (b) Describe the tree produced by Breadth First Search run on G‘,1 starting at root 5 = (0,0). Figure (C) illustrates the tree producedfor G5. (5.5)