Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!akgua!mcnc!unc!ulysses!mhuxl!ihnp4!zehntel!hplabs!sri-unix!Narain@Rand-Unix
From: Narain%Rand-Unix@sri-unix.UUCP
Newsgroups: net.lang.prolog
Subject: Reply to Yoav Shoham
Message-ID: <12450@sri-arpa.UUCP>
Date: Fri, 30-Mar-84 16:00:00 EST
Article-I.D.: sri-arpa.12450
Posted: Fri Mar 30 16:00:00 1984
Date-Received: Mon, 23-Apr-84 01:17:11 EST
Lines: 28

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