Depth First Search traversal of this list

Discussion of Common Lisp
Post Reply
crashoverride

Depth First Search traversal of this list

Post by crashoverride » Wed Sep 10, 2008 3:52 pm

Hello,
I am trying to traverse the list (A (B (D E) C)) in a way that the print output should be in the following order D, E, B, C, A aka depth first traversal.

So far, I have come up with this code but it seems to have some strange problem.

Code: Select all

(setq start (list 'a (list 'b (list 'd 'e) 'c )))           ====> gives ====> (A (B (D E) C))

(defun depth-first (start)
	(cond
		((null start) 0)
		((listp (first start)) (setq start (first start)) 
							   (depth-first (first start)))
		((not (eq nil (car start))) (print (car start))
					(setq start (rest start)) 
					(depth-first (start)))
		(t "Go home")))
Can someone please help me out.

Kohath
Posts: 61
Joined: Mon Jul 07, 2008 8:06 pm
Location: Toowoomba, Queensland, Australia
Contact:

Re: Depth First Search traversal of this list

Post by Kohath » Wed Sep 10, 2008 5:44 pm

Remember that your list looks like this (with depth going down):

Code: Select all

(a, .............)
    (b, ....., c)
        (d e)
So do you want the output to be D, E, B, C, A? I thought it would be A, B, D, E, C. Breadth first would be A, B, C, D, E. I haven't done much of this kind of thing though, so I could be mistaken.

P.S. Your error is caused by you trying to call start as a function (see the second last line of your code).

smithzv
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Depth First Search traversal of this list

Post by smithzv » Thu Sep 11, 2008 1:26 pm

This problem looks a bit homework-ish, so I will try not to reveal an answer outright, but also, I hope I don't come off too condescending.

What Kohath is talking about is the normal way we think of trees in CL. These are binary trees where the CAR is and the CDR are the two branches from an interior node. Only leaves hold values. You are looking to do something a bit different (perhaps, or perhaps you are confused).

Let me ask a question, how would you print this list: (A (B C) (D (E F)))? I am honestly not sure how this would be printed from your example. Better than hazarding guess, I will just ask and wait for a response.

Code: Select all

(defun depth-first (start)
   (cond
      ((null start) 0)
      ((listp (first start)) (setq start (first start))
                        (depth-first (first start)))
      ((not (eq nil (car start))) (print (car start))
               (setq start (rest start))
               (depth-first (start)))
      (t "Go home")))
Looks like some clumsy assignments in there. There really is no reason for that on a problem like this.

My suggestion is to think this out in pseudo code first. Or, like I do, just pretend you are the computer walking along the tree. Develop a set of rules that you will follow at each point and see if it works for various inputs. Then you can sit down and start thinking about an algorithm that works for all inputs.

Zach S

danb
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

Re: Depth First Search traversal of this list

Post by danb » Sat Sep 13, 2008 5:36 am

crashoverride wrote:I am trying to traverse the list (A (B (D E) C)) in a way that the print output should be in the following order D, E, B, C, A aka depth first traversal.
This is a depth-based ordering of the nodes, but you need to collect elements breadth-first. Try writing a function that takes a tree as its only argument and returns a list of lists, where the nth element of the list is a list of all atoms at the nth level of the tree. You'll also need a function that combines two of those level lists into a single level list, and you'll have to massage the final list a little to get a flat bottom-up list.

Post Reply