cs42 Consider Figure 32 9 Page 122 of Textbook Suppose N is

cs42

Consider Figure 3.2 9 (Page 122 of Textbook). Suppose N is a goal state. Give the list of nodes visited and a solution by using DFS and BFS, respectively.

Solution

DFS:

Stack: A
Output:

Stack: B C D
Output: A

Stack: B C H I
Output: A D

Stack: B C H P R
Output: A D I

Stack: B C H P
Output: A D I R

Stack: B C H
Output: A D I R P

Stack: B C O
Output: A D I R P H

Stack: B C
Output: A D I R P H O

Stack: B G
Output: A D I R P H O C

Stack: B M N
Output: A D I R P H O C G

Stack: B M
Output: A D I R P H O C G N

So, we reached our goal state(N). So, The final output is:

A D I R P H O C G N

BFS:

Queue: A
Output:

Queue: B C D
Output: A

Queue: C D E F G
Output: A B

Queue: D E F G
Output: A B C

Queue: E F G H I
Output: A B C D

Queue: F G H I J K L
Output: A B C D E

Queue: G H I J K L
Output: A B C D E F

Queue: H I J K L M N
Output: A B C D E F G

Queue: I J K L M N O P
Output: A B C D E F G H

Queue: J K L M N O P R
Output: A B C D E F G H I

Queue: K L M N O P R
Output: A B C D E F G H I J

Queue: L M N O P R
Output: A B C D E F G H I J K

Queue: M N O P R
Output: A B C D E F G H I J L

Queue: N O P R
Output: A B C D E F G H I J L M

Queue: O P R
Output: A B C D E F G H I J L M N

So, we reached our goal state(N). So, The final output is:
A B C D E F G H I J L M N