dfs in prolog. Visiting a node once

Question

dfs(S, Visited, Path) :-
    move(S, S2),
    \+member(S2, Visited),
    dfs(S2, [S2|Visited], Path).

Hi,

Above piece of code is a prototype of dfs in Prolog. But, move bases on backtracking and because of that fact I lose Visited list so it is impossible to make sure that I visit every node once. How to deal with it without using global variable and similar to it- I would like use pure logical solution.

Answer 1

You could use an iterative(stack-based) approach for your dfs instead of recursive, as explained in How to implement depth first search for graph with non-recursive aprroach.

Move will be called to check what the possible neighbors are. The difference here is that you first loop over the possible candidates. By always putting them in front of the stack, we are iteratively going first in to depth since the top of the stack will be explored first.

The finding of the possible next candidates can for instance be done with findall

Example:

%% Dfs starting from a root
dfs(Root) :-
    dfs([Root], []).
%% dfs(ToVisit, Visited)
%% Done, all visited
dfs([],_).
%% Skip elements that are already visited
dfs([H|T],Visited) :-
    member(H,Visited),
    dfs(T,Visited).
%% Add all neigbors of the head to the toVisit
dfs([H|T],Visited) :-
    not(member(H,Visited)),
    findall(Nb,move(H,Nb),Nbs),
    append(Nbs,T, ToVisit),
    dfs(ToVisit,[H|Visited]).