Depth First to Breadth First

JCW2
JCW2 used Ask the Experts™
on
I'm trying to convert a depth first search algorithm to a depth first search algorithm. What suggestions do you have?
;;;; New programming

(defun dfs (end queue graph)
  (if (null queue) nil
    (let ((path (first queue)))
      (let ((node (first path)))
       (if (eql node end)
              (format t "~% Complete path is: ~a" (reverse path))
	      (dfs end 
		   (append (dfs-new-path path node graph) (rest queue))
		   graph)
       )
      ) 
    )
  )  
)

(defun dfs-new-path (path node graph)
  (print (reverse path))
  (mapcar #'(lambda (n)
	            (cons N path))
	  (remove-if #'(lambda (repeat-node)
			       (member repeat-node path))
		     (rest (assoc node graph))
          )
  )
)

Open in new window

Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Just curious what flavor of lisp is it?  I mostly used auto list   (autocad)...  

Author

Commented:
Common Lisp.
is there a free compiler/interpeter anywhere to use to test the code with?
Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

what is it supposed to do exactly?  the goal?

Author

Commented:
The goal of this is to display intermediate paths and the final path for a breadth first search. This code performs a depth first search.
Alg.PNG
Commented:
I've come up with a solution:
;;;; New programming

(defun bfs (end queue graph)
  (if (null queue) nil ; if we don't have a queue, no place to start
    (let ((path (first queue))) ; retrieve path
      (let ((node (first path))) ; retrieve node
       (if (eql node end)
              (format t "~% Complete path is: ~a" (reverse path)) ; tell complete path and reverse to get order correct
	      (bfs end 
		   (append (rest queue) (dfs-new-path path node graph) ) ; reverse where queue data is placed and include new-path information
		   graph)
       )
      ) 
    )
  )  
)

(defun bfs-new-path (path node graph)
  (print (reverse path)) ; invert path data to get straight
  (mapcar #'(lambda (N) ; start iteration
	            (cons N path)) ; put N and path together
	  (remove-if #'(lambda (repeat-node) ; remove if "repeat-node"
			       (member repeat-node path))
		     (rest (assoc node graph)) ; repeat-node is the rest of assoc of the key node and the list graph
          )
  )
)

Open in new window

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial