cs42 Suppose P is a goal state Give the list of nodes visite

cs42

Suppose P is a goal state. Give the list of nodes visited and a solution by using DFS and BFS, respectively.

Solution

BFS:
step1: Consider A
   Adjacent vertices: B C D
   add them in queue B C D
   set visted =true for A
  
step2: Consider first of queue: B
   Queue: C D E F G
Visited[B]=true
step3: Consider C
   Queue: D E F G
Visited[C]=true

step4: Consider D
   Queue: E F G H I
Visited[D]=true
step5: Consider E
   Queue: G H I J K L
Visited[E]=true
step6: Consider F
   Queue: G H I J K L
Visited[F]=true
step7: Consider G
   Queue: H I J K L M N
Visited[G]=true
step8: Consider H
   Queue: I J K L M N O P
Visited[H]=true
step9: Consider I
   Queue: J K L M N O P R
Visited[I]=true
step8: Consider J
   Queue: K L M N O P R
Visited[J]=true

step9: Consider K
   Queue: L M N O P R
Visited[K]=true
step10: Consider L
   Queue: M N O P R
Visited[L]=true
step11: Consider M
   Queue: N O P R
Visited[M]=true

step12: Consider N
   Queue: O P R
Visited[N]=true
step13: Consider O
   Queue: P R
Visited[O]=true
step14: Consider P
   Queue: R
Visited[P]=true

P is found

List of nodes visited till now:
A->B->C->D->E->F->G->H->I->J->K->L->M->N->O->P

---------------------------------------------------------------------------------------------------------------------------

DFS:

DFS:
step1: Consider A
   left child: B
   stack : A
   set visted[A]=true
step2: Consider B
B has left child E
   stack: A B
Visited[B]=true
step3: Consider E
E has left child J
   stack: A B E J
Visited[E]=true
step4: Consider J
J has no child.
pop the stack: E
   stack: A B
Visited[J]=true
step4: Consider E
Consider E is next child K.
   stack: A B E K
step5: Consider K
K has no child.
pop the stack: E
   stack: A B
step6: Consider E
Consider E is next child L.
   stack: A B E L
step7: Consider L
L has no child.
pop the stack: E
   stack: A B
step8: Consider E
   All childrens of E are processed.
So pop stack: B
stack:B
like wise we traverse the rest of the graph.

List of nodes: A->B->E->J->K->L->F->G->M->N->H->O->P
P found