Practice With Searches #1
Putprop, Depth First, and Breadth First

1.  Draw the graph for these putprops:
   (putprop 'A '(B D) 'adjacent)
   (putprop 'B '(A C E) 'adjacent)
   (putprop 'C '(A E) 'adjacent)
   (putprop 'D '(A) 'adjacent)
   (putprop 'E '(D C) 'adjacent)

2. Depth First,  trace a search from A to C

   #1 expand A, put the new lists on a stack (in a lists of lists)
   #2  ((B A)  nodes are put on in reverse order
        (D A))
   #3  Pop first path off stack and extend node B, put back on stack:
       ((A B A)
        (C B A)
        (E B A)
        (D A))  ;;from the first stack
   #4  Pop first path off stack and extend node A.  This results in 
       an infinite cycle.

3.  Depth First, trace a search from E to B
   #1 expand E, put the new lists on a stack
   #2  ((D E)  nodes are put on in reverse order
        (C E))
   #3  Pop first path off stack and extend node D, put back on stack:
       ((A D E)
        (C E))
   #4  Pop first path off stack and extend node A.
       ((B A D E)
        (D A D E)
        (C E))
   #5  Pop path off stack, B is the goal node.

4. Breadth First, trace a search from A to C
   #1 expand A, put new path lists on the queue
      front  ((B A) (D A))  rear    (nodes are put on in reverse order)
   #2 dequeue first path from the front of the queue.  Expand node B,
      put the new paths on the rear of the queue:

      front  ((D A) (A B A) (C B A) (E B A))  rear

   #3 dequeue a path from the front of the queue, expand node D,
      put the new paths on the rear of the queue:

      front  ((A B A) (C B A) (E B A) (A D A)) rear

    #4 dequeue a path from the front of the queue, expand node A,
      put the new paths on the rear of the queue:

      front  ((C B A) (E B A) (A D A) (B A B A) (D A B A))  rear
 
    The path is found (C B A)  path is in reverse       

5.  Breadth First, trace a search from E to B
   #1 expand E, put new path lists on the queue
      front  ((D E) (C E))  rear    (nodes are put on in reverse order)
   #2 dequeue first path from the front of the queue.  Expand node D,
      put the new paths on the rear of the queue:

      front  ((C E) (A D E))  rear

   #3 dequeue a path from the front of the queue, expand node C,
      put the new paths on the rear of the queue:

      front  ((A D E) (A C E) (E C E)) rear

    #4 dequeue a path from the front of the queue, expand node A.

      front  ((A C E) (E C E) (B A D E) (D A D E)) rear 

    #5 dequeue path from the fron of the queue, expand node A.

      front  ((E C E) (B A D E) (D A D E) (B A C E) (D A C E)) rear

     #6 One more level 3 path, (E C E), expand node E.

      front  ((B A D E) (D A D E) (B A C E) (D A C E) (D E C E) (C E C E)) rear

     #7 Dequeue (B A D E) and B is the goal node.

6. Depth first with "remove".  Path from A to C
   #1 expand A, put the new lists on a stack
       (B A)  nodes are put on in reverse order
       (D A)
   #3  Pop first path off stack and extend node B, put back on stack:
       (A B A)  remove the cycle, don't put this path on the stack 
       (C B A)
       (E B A)
       (D A)  ;;from the first stack
   #4  Pop first path off stack and extend node C.
       (C B A)
       (E B A)
       (E B A)
       (D A)
               C is the goal node.