Is this really the first Breadth First Search
There is a pseudocode snippet of the width of the first search on page 303 of OnLisp, which is shown below. For the graph below, it processes node 1 first and then puts node 2, 3, and 4 into the queue, and then just iteratively calls itself again. It will then continue with node 4 which is at the head of the queue. This in turn puts node 7 and 8 at the head of the queue, etc.
Finally, the path traveled will be 1-> 4-> 7-11-> 12-> 8-> 3-> 2-> 5-> 9-> 10-> 6, which is the first depth search. Am I wrong here?
(define (path node1 node2)
(bf-path node2 (list (list node1))))
(define (bf-path dest queue)
(if (null? queue)
'@
(let* ((path (car queue))
(node (car path)))
(if (eq? node dest)
(cdr (reverse path))
(bf-path dest
(append (cdr queue)
(map (lambda (n)
(cons n path))
(neighbors node))))))))
source to share
The first search uses the first, first queue first for the elements that will intersect.
It should look at the first node (1)
, then grab its children (2, 3, 4)
and populate the list in that order. Now look at the first item in the list and take its children (5, 6)
and add them to the end of the list of things to see (3, 4, 5, 6)
.
Repeat this for the first element only.
3 -> (4, 5, 6)
4 -> (5, 6, 7, 8)
5 -> (6, 7, 8, 9, 10)
6 -> (7, 8 , 9, 10)
7 -> (8, 9, 10, 11, 12)
8 -> (9, 10, 11, 12)
9 -> (10, 11, 12)
10 -> (11, 12)
11 -> (12)
12 -> ()
By doing in, last out first (looping over the last added element, as you do), you create the first depth search.
source to share