Depth First Search traversal of this list

Discussion of Common Lisp

Depth First Search traversal of this list

Postby 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.
crashoverride
 

Re: Depth First Search traversal of this list

Postby 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).
User avatar
Kohath
 
Posts: 50
Joined: Mon Jul 07, 2008 8:06 pm
Location: Brisbane, Queensland, Australia

Re: Depth First Search traversal of this list

Postby 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
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Depth First Search traversal of this list

Postby 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.
danb
 
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US


Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 2 guests