3
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.

Gilgamesz
  • 4,727
  • 3
  • 28
  • 63
  • 1
    You will need some extra-logical machinery for this. But generally, we are quite happy with visiting nodes more than once, provided cycles are avoided. See [`path/4`](http://stackoverflow.com/q/30328433) for a general solution to avoiding cycles. – false Jun 18 '16 at 09:49

1 Answers1

2

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]).
Community
  • 1
  • 1
Sam Segers
  • 1,951
  • 2
  • 22
  • 28
  • 2
    This is not An iterative deepening algorithm? And I'm keeping track of visites nodes so how can I have multiples then? – Sam Segers Jun 18 '16 at 10:37
  • You are right. Nevertheless, OP "would like use pure logical solution". Neither `findall/3` nor the `not` qualify in that respect. – false Jun 18 '16 at 12:54