Board index » delphi » "breadth first search"

"breadth first search"

I got a question....how do you do a "breadth first search"  on pascal???
 

Re:"breadth first search"


Quote
u1510804 wrote:
> I got a question....how do you do a "breadth first search"  on
> pascal???

What is your data structure that you are trying to search?  If you draw
it on a piece ofpaper, does it have a two-dimensional form?  If so, can
you see how you might visit
every location by going "across the breadth" of the structure, as
opposed to "going down
the depth" first?

Bob Schor
Pascal Enthusiast

Re:"breadth first search"


In article <36F1C518.C8A36...@site.uottawa.ca>,

Quote
u1510804  <u1510...@site.uottawa.ca> wrote:
>I got a question....how do you do a "breadth first search"  on pascal???

I assume you are using a tree as data structure. Well what you need is a
queue. First handle the root and put the children in the queue. Then
handle the nodes in the queue each time putting the children to the
queue until the queue is empty.

Osmo

Re:"breadth first search"


Quote
u1510804 wrote in message <36F1C518.C8A36...@site.uottawa.ca>...
>I got a question....how do you do a "breadth first search"  on pascal???

Hah, fellow Ottawa U student!!! Probably taking CSI 2114?...  With Holte?...
I loved that guy!!

The basic idea is to use an external structure, a queue, as your "to
process" list.  You put the root on the queue, then while the queue is not
empty you
1) remove an item from the queue
2)put its children (if any) onto the back of the queue
3) process the removed item.

Depending in which order you put in the children (right child first or left
child first) you'll get the right-hand traversal or left-hand traversal.

If you ever need to do depth-first traversal, you just use a stack instead
of a queue in the above algorithm.  Watch out, because now if you put on the
stack RIGHT child first, and then LEFT, you'll get a LEFT-hand traversal
(i.e. all left branches will be processed before all right branches).

Hope this helps, and look up the notes on the web.  I believe the address
is:

www.csi.uottawa.ca/ftppub/courses/Winter/

Then find the page for CSI 2114 there.

Good luck, and I hope this helps.

Nikita.

Re:"breadth first search"


In article <yDAI2.4839$8c4.24653...@news.magma.ca>,
  "Nikita Synytskyy" <nik...@NOSPAMmondenet.com> wrote:

Quote

> u1510804 wrote in message <36F1C518.C8A36...@site.uottawa.ca>...
> >I got a question....how do you do a "breadth first search"  on pascal???

> Hah, fellow Ottawa U student!!! Probably taking CSI 2114?...  With Holte?...
> I loved that guy!!

> The basic idea is to use an external structure, a queue, as your "to
> process" list.  You put the root on the queue, then while the queue is not
> empty you
> 1) remove an item from the queue
> 2)put its children (if any) onto the back of the queue

where I come from they call that a FIFO.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re:"breadth first search"


Quote

>where I come from they call that a FIFO.

"First in--First out".  The major property of the queue.

Nikita.

Other Threads