Curiously enough, both of the traversal methods we considered can be very naturally implemented with the help of one of these data structures. First, we'll write the following simple helper functions, for putting a bunch of stuff into a stack or queue.
(: push-all (All (A) (-> (Listof A) (Stack A) (Stack A)))
;; Push all items in given list onto given stack, from left to right.
(define (push-all xs st)
(foldl (inst push A) st xs))
(: enqueue-all (All (A) (-> (Listof A) (Queue A) (Queue A)))
;; Enqueue all items in given list into given queue, from left to right.
(define (enqueue-all xs qu)
(foldl (inst enqueue A) qu xs))
Here, we use the same strategy as with building trees. We're essentially aggregating a stack/queue over the list of elements, so this ends up being a fold. We use foldl since the order in which we add the elements matters.
With that out of the way, we can consider why it is we need these data structures to do traversals. In addition to remembering which nodes we've visited, we also need to manage in which order we visit the neighbours of those nodes. For depth-first traversal, this happens when we run into a dead end and begin backtracking. For breadth-first traversal, this happens when we run consider each "level" of neighbours. Either way, we need a systematic way of remembering this information.
We'll start with depth-first traversal, which can be accomplished by using a stack. Our algorithm can be described as follows:
First, we notice that we need to keep track of which vertices have been visited. We will do this by keeping a list of the visited vertices. Then we can use this to determine the unmarked neighbours of a given vertex.
(: unmarked-neighbours (-> Symbol Graph (Listof Symbol) (Listof Symbol)))
;; From a list of neighbours, remove those vertices that have been marked
(define (unmarked-neighbours v g marked)
(local
{(: remove-marked (-> Symbol (Listof Symbol) (Listof Symbol)))
;; Given a marked vertex, remove it if it's in the list
(define (remove-marked v vs)
(filter (lambda ([u : Symbol]) (not (symbol=? u v))) vs))}
(foldr remove-marked (neighbourhood v g) marked)))
Now, why does a stack happen to do exactly what we need to do for a depth-first traversal? Since we always try to follow an edge from the current node, we are always considering the most recent set of neighbours. Now, when we run into a dead end, we need to backtrack. But we backtrack to the most recent set of viable neighbours. This means that the set of vertices that we want to attempt to visit will always be the most recent ones we consider. A stack will naturally capture that information.
Before getting to the code, let's look at the other case.
Our approach for breadth-first traversal will look very similar. Our algorithm can be described as follows:
Luckily, we have already written a helper function for determining the unmarked neighbours of a vertex and a lot of the reasoning of the depth-first traversal applies here concerning marking vertices.
Now let's consider why a queue makes sense for a breadth-first traversal. In a breadth-first traversal, we consider neighbours at each "level" away from our starting vertex. For instance, we can consider a starting vertex $v$ to be at level 0. Then level 1 are the immediate neighbours of $v$. Level 2 would then be the neighbours of all level 1 vertices, and so on.
As with depth-first traversal, when we visit a vertex, we also need to remember its neighbours. However, we want to consider the neighbours of each level before moving on to the next. Since we visit the neighbours level-by-level, this means that we really want to consider the oldest neighbours first. A queue naturally captures this notion.
We then arrive at the following function.
(: breadth-first-traversal (-> Symbol Graph (Listof Symbol)))
;; Produce a list of labels of vertices visited via breadth-first traversal
(define (breadth-first-traversal v g)
(local
{(: bft (-> Graph (Queue Symbol) (Listof Symbol) (Listof Symbol)))
(define (bft g q marked)
(match (dequeue q)
['None '()]
[(Some (Pairof curr next))
(local
{(define us (unmarked-neighbours curr g marked))}
(cons curr (bft g
(enqueue-all us next)
(append marked us))))]))}
(bft g (enqueue v '()) (list v))))