algorithm 0: random walk

current cell <-- origin while current cell != destination current cell <-- random neighbour of current cell print current cell

random walk maze traversal

this implementation is recursive

pro: easy to describe, leave some implementation details to language implementers

con: harder to learn, lose control to language implementers (e.g. stack overflow)

analysis of algorithm

correct? (does it always do what it is supposed to?)

efficient? (w.r.t. time? w.r.t. space?)

can it be improved?

hint: Theseus' thread, Hansel+Gretel's breadcrumbs

a maze and its adjacency graph

X X X X X X a - b - c - d X . . . . X | | X . X . X X e f X . . X . X | X . . . . X g - h i X X X X X X | | | j - k - l - m nodes or points: a b c ... m edges or lines: ab ae bc cd cf eg gh gj hk im jk kl lm

graph traversal

our version

from a given start node, see what nodes we can reach by following edges

there is a more general version of graph traversal

maintain list L of nodes seen but not yet explored

do not add a node to a list if we have already seen it

breadth first search:

L is queue, FIFO list

so remove node appended earliest

iterative depth-first search:

L is stack, LIFO list

so remove node appended most recently

depth-first search

recursive (recurse as soon as unseen nbr found)

differs slightly from iterative-dfs

iterative bfs,dfs

for all nodes v: v.seen <- False L = [start], start.seen = True while not empty(L): v <- L.remove() for each neighbour w of v: if w.seen==False: L.append(w), w.seen = True

example trace of bfs

use the above adjacency graph, start from node j initialize L = [ j ] while loop execution begins remove j from L L now [ ] nbrs of j are g,k append g to L, g.seen <- T L now [ g ] append k to L, k.seen <- T L now [ g, k ] while loop continues (bfs, so L is queue, so remove g) remove g from L L now [ k ] nbrs of g are e,h,j append e to L, e.seen <- T L now [ k, e ] append h to L, h.seen <- T L now [ k, e, h ] j already seen while loop continues: remove k from L v <- k L now [ e, h ] nbrs of k are j,h,l j already seen h already seen append l to L, l.seen <- T L now [ e, h, l ] while loop continues: ...

exercises

complete the above bfs trace (hint: order of removal of nodes from L is j g k j g k e h l a m b i c d f)

perform an iterative dfs trace (hint: the only difference is that the list is a stack

recursive dfs

for all nodes v: v.seen <- False def dfs(v): v.seen <- True for each neighbour w of v: if w.seen==False: dfs(w) dfs(start)

example dfs trace

use above graph, start from j dfs(j) nbrs g,k . dfs(g) nbrs e,h,j . . dfs(e) nbrs a,g . . . dfs(a) nbrs b,e . . . . dfs(b) nbrs a,c . . . . . a already seen . . . . . dfs(c) nbrs b,d,f . . . . . . b already seen . . . . . . dfs(d) nbrs c . . . . . . . c already seen . . . . . . dfs(f) nbrs c . . . . . . . c already seen . . . . e already seen . . . g already seen . . dfs(h) nbrs g,k . . . g already seen . . . dfs(k) nbrs g,h,l . . . . g already seen . . . . h already seen . . . . dfs(l) nbrs k,m . . . . . k already seen . . . . . dfs(m) nbrs l,i . . . . . . l already seen . . . . . . dfs(i) nbrs m . . . . . . . m already seen . . j already seen . k already seen

example, above maze graph, from j

- assume nbrs are stored in alphabetic order - iterative bfs: order of removal from list? j g k e h l a m b i c d f - iterative dfs: order of removal from list? j k l m i h g e a b c f d - recursive dfs: order of dfs() calls? j g e a b c d f h k l m i - iterative dfs with nbrs added to list in reverse order: j g e a b c d f k h l m i notice that this differs from recursive dfs

algorithm 1: use list to keep track of cells we have seen

list cells examined in FIFO manner (queue)?

list cells examined in FILO manner (stack)?