I have an undirected graph which nodes are numbered from 0 to 5. Adjacencies are given with a vector of lists #((1 2) (0 3) (0) (1) (5) (4)))
, thus node 0 is connected to nodes 1 and 2, node 1 is connected to nodes 0 and 3 and so on.
I want to walk using a DFS recursive algorithm:
Function walk(vector: vadj, integer: x, list: acc)
If x is not in acc then
append x to acc
Foreach successor y of x
walk(vadj, y, acc)
EndForeach
EndIf
EndFunction
With Scheme, I try:
(define (walk vadj x acc)
(unless (member x acc)
(set! acc (append acc (list x)))
(let loop ((lst (vector-ref vadj x)))
(unless (null? lst)
(walk vadj (car lst) acc)
(loop (cdr lst))))))
(let ((adj #((1 2) (0 3) (0) (1) (5) (4)))
(res '()))
(walk adj 0 res)
(newline)(display res))
I get an empty list as a result, the result should be '(0 1 3 2)
. I suspect acc
is sometimes redefined by successive walk
environments.
Warning : I never used Scheme before to write that answer
The algorithm supposes the parameter acc is an input-output parameter, but it seems in scheme the parameters can only be input parameters (I don't see in docs how to specify the parameter direction)
So a way is to return acc and assign it (or res) on the calls of walk to simulate the input-output:
(define (walk vadj x acc)
(unless (member x acc)
(set! acc (append acc (list x)))
(let loop ((lst (vector-ref vadj x)))
(unless (null? lst)
(set! acc (walk vadj (car lst) acc))
(loop (cdr lst)))))
acc)
(let ((adj #((1 2) (0 3) (0) (1) (5) (4)))
(res '()))
(set! res (walk adj 0 res))
(newline)(display res)
)
and the execution prints (0 1 3 2)
Or of course simplify replacing :
(set! res (walk adj 0 res))
(newline)(display res)
by :
(newline)(display (walk adj 0 res))