Narain%Rand-Unix@sri-unix.UUCP (03/31/84)
The following pure Prolog program will do breadth-first
traversal of a tree in o(v) time. The input to 'bf' is
a list of nodes at some level. (At the top level it is
simply [root]). The output is a list of nodes of the
tree traversed in breadth-first order.
The algorithm may also be used to traverse a graph without
cycles, but as there is no equivalent of a 'mark' bit here,
nodes may be repeated in the output.
bf([],[]).
bf(L,Z):-successor_list(L,SL),bf(SL,BSL),append(L,BSL,Z).
successor_list([],[]).
successor_list([U|V],Z):-succ(U,SU),successor_list(V,SV), append(SU,SV,Z).
append([],X,X).
append([U|V],W,[U|Z]):-append(V,W,Z).
Procedure 'succ' contains clauses of the form
succ(Node,Successor_list)
where 'Successor_list' is a list of immediate sucessors of
'Node'. If 'Node' is a terminal node then 'Successor_list'
is [].
-- Sanjai Narain