Breadth First Search in Prolog

Question

I'm new to Prolog and currently implementing DFS (depth-first search) and BFS (breadth-first search) algorithms. My DFS works fine as the code below, but the BFS is terminated and aborted when it reaches the leaf node (it doesn't backtrack and continue searching). I also read some sample code about this but there are some functions they don't define like s(Node, NewNode)... so it's hard to understand, or the version use Queue is too complicated.

Here is my code: Some ground functions:

%connected(+Start, +Goal, -Weight)
connected(1,7,1).
connected(1,8,1).
connected(1,3,1).
connected(7,4,1).
connected(7,20,1).
connected(7,17,1).
connected(8,6,1).
connected(3,9,1).
connected(3,12,1).
connected(9,19,1).
connected(4,42,1).
connected(20,28,1).
connected(17,10,1).

connected2(X,Y,D) :- connected(X,Y,D).
connected2(X,Y,D) :- connected(Y,X,D).

next_node(Current, Next, Path) :-
    connected2(Current, Next, _),
    not(member(Next, Path)).

DFS implement:

depth_first(Goal, Goal, _, [Goal]).
depth_first(Start, Goal, Visited, [Start|Path]) :-
    next_node(Start, Next_node, Visited),
    write(Visited), nl,
    depth_first(Next_node, Goal, [Next_node|Visited], Path).

BFS implement:

breadth_first(Goal, Goal, _,[Goal]).
breadth_first(Start, Goal, Visited, Path) :-
    findall(X,
            (connected2(X,Start,_),not(member(X,Visited))),
            [T|Extend]),
    write(Visited), nl,
    append(Visited, [T|Extend], Visited2),
    append(Path, [T|Extend], [Next|Path2]),
    breadth_first(Next, Goal, Visited2, Path2).

The Path is something like the Queue list. For example when call DFS:

?- depth_first(1, 28, [1], P).

BFS:

?- breadth_first(1, 28, [1], []).

Solution

First, the usual notion of s(A,B) is just like your connect2(A,B,_).

You should make your interface predicates explicit:

depth_first( Start, Goal, Path):-
    depth_first( Start, Goal, [Start], Path).

Maintaining a queue in BFS is not complicated at all. Instead of Visited, have VisitedLists queue (pop from front; add at end; thus FIFO):

consed( A, B, [B|A]).

bfs( Goal, [Visited|Rest], Path) :-                     % take one from front
    Visited = [Start|_],            
    Start \== Goal,
    findall( X,
        ( connected2(X, Start, _), \+ member(X, Visited) ),
        [T|Extend]),
    maplist( consed(Visited), [T|Extend], VisitedExtended),      % make many
    append( Rest, VisitedExtended, UpdatedQueue),       % put them at the end
    bfs( Goal, UpdatedQueue, Path ).

When the goal is reached, Path is instantiated:

bfs(Goal, [[Goal|Visited]|_], Path):- 
    reverse([Goal|Visited], Path).

The interface call needs to be adjusted correspondingly. It should be

breadth_first( Start, Goal, Path):- bfs( Goal, [[Start]], Path).

later note: repeated appending of course causes quadratic slowdown, so for efficiency this should be re-written with difference lists (also a straightforward task).

Comments

[Will Ness]

@hardik-upadhyay thank you for your edit suggestion. I used the same piece of code as was in the question, apparently, so if that was ever to be changed, the changes would have to be introduced in sync to the question as well. since many years have passed, I think it's all better left as it is. :)