<div class="notebook">

<div class="nb-cell markdown" name="md1">
Vamos começar criando um grafo, baseado na rede de metrô de São Paulo (e ignorando CPTM).
</div>

<div class="nb-cell program" data-background="true" name="p1">
% Rede de metrô em São Paulo, apenas com interconexões entre linhas.
% http://www.metro.sp.gov.br/pdf/mapa-da-rede-metro.pdf
estação(tucuruvi).
estação(luz).
estação(sé).
estação(paraíso).
estação(ana_rosa).
estação(santa_cruz).
estação(jabaquara).
estação(barra_funda).
estação(república).
estação(brás).
estação(itaquera).
estação(vila_madalena).
estação(consolação).
estação(chácara_klabin).
estação(vila_prudente).
estação(são_mateus).
estação(morumbi).
estação(paulista).
estação(capão_redondo).
estação(santo_amaro).

% Linha azul
caminho(tucuruvi, luz).
caminho(luz, sé).
caminho(sé, paraíso).
caminho(paraíso, ana_rosa).
caminho(ana_rosa, santa_cruz).
caminho(santa_cruz, jabaquara).

% Linha vermelha
caminho(barra_funda, república).
caminho(república, sé).
caminho(sé, brás).
caminho(brás, itaquera).

% Linha verde
caminho(vila_madalena, consolação).
caminho(consolação, paraíso).
% caminho(paraíso, ana_rosa) já está presente na linha azul
caminho(ana_rosa, chácara_klabin).
caminho(chácara_klabin, vila_prudente).

% Linha amarela
caminho(morumbi, paulista).
caminho(paulista, república).
caminho(república, luz).

% Conexão a pé
caminho(paulista, consolação).

% Linha prata
caminho(vila_prudente, são_mateus).

% Linha lilás
caminho(capão_redondo, santo_amaro).
caminho(santo_amaro, santa_cruz).
caminho(santa_cruz, chácara_klabin).
</div>

<div class="nb-cell markdown" name="md2">
Abaixo o código da questão original do Stack Overflow, que não executa uma busca em largura, mas sim em profundidade.
</div>

<div class="nb-cell program" data-singleline="true" name="p2">
/* Chegar de A a Z, retornando caminho percorrido P,
   comecando de um caminho vazio
*/
path(A,Z,P) :- path1(A,Z,[],P).

/* Se ja' cheguei ao destino, parar a busca e incluir
   destino na lista contendo o caminho percorrido */
path1(Z,Z,L,L).

/* Se ainda nao cheguei no destino, encontrar caminho
   parcial de A para Y,  adicionar `a lista contendo o
   caminho parcial e continuar a busca a partir de Y
*/
path1(A,Z,L,P) :- (caminho(A,Y);caminho(Y,A)),
       \+ member(Y,L),
      path1(Y,Z,[Y|L],P). /* encontra caminho parcial de */
                          /* Y a Z */
</div>

<div class="nb-cell query" name="q1">
path(morumbi, tucuruvi, P).
</div>

<div class="nb-cell markdown" name="md3">
Vamos fazer algumas correções miúdas...
</div>

<div class="nb-cell program" data-singleline="true" name="p3">
conectado(A, B) :- caminho(A, B); caminho(B, A).

path(estação(A), estação(Z), P) :-
    path_(A, Z, [A], P1),
    reverse(P1, P).

path_(Z,Z,L,L).
path_(A,Z,L,P) :-
    conectado(A, Y),
    \+ member(Y, L),
    path_(Y, Z, [Y|L], P).
</div>

<div class="nb-cell query" name="q2">
path(estação(morumbi), estação(tucuruvi), P).
</div>

<div class="nb-cell markdown" name="md4">
A pergunta pede para visualizar o caminho que o Prolog percorreu para encontrar o caminho final. Isso é possível de 3 maneiras:

1. Manualmente, usando `trace` para acompanhar todos os passos internos;
2. Com o bom e velho debug orientado a printf, imprimindo o caminho explorado até o momento;
3. Acumulando as mudanças em um termo mutável.


Vamos começar pela alternativa #2.
</div>

<div class="nb-cell program" name="p4">
conectado(A, B) :- caminho(A, B); caminho(B, A).

path(estação(A), estação(Z), P) :-
    path_(A, Z, [A], P1, 0),
    reverse(P1, P).

path_(Z,Z,L,L, _).
path_(A,Z,L,P, Depth) :-
    conectado(A, Y),
    \+ member(Y, L),
    format("#~d: caminho(~w, ~w)~n", [Depth, A, Y]),
    Depth1 is Depth+1,
    path_(Y, Z, [Y|L], P, Depth1).
</div>

<div class="nb-cell query" name="q3">
path(estação(morumbi), estação(tucuruvi), P).
</div>

<div class="nb-cell markdown" name="md5">
Vamos agora tentar armazenar as informações saídas no print (A, Y e Depth) em uma lista mutável. Essa informação é suficiente para construir uma árvore mostrando todas as tentativas, posteriormente.
</div>

<div class="nb-cell program" name="p5">
conectado(A, B) :- caminho(A, B); caminho(B, A).

path(estação(A), estação(Z), P) :-
    Debug = debug([]),
    path(estação(A), estação(Z), P, Debug),
    writeln(Debug).

path(estação(A), estação(Z), P, Debug) :-
    path_(A, Z, [A], P1, 0, Debug),
    reverse(P1, P).

path_(Z,Z,L,L, _, _).
path_(A,Z,L,P, Depth, Debug) :-
    conectado(A, Y),
    \+ member(Y, L),
    %%%%
    arg(1, Debug, Changes),
    Changes1 = [passo(Depth, A, Y)|Changes],
    nb_setarg(1, Debug, Changes1),
    %%%%
    Depth1 is Depth+1,
    path_(Y, Z, [Y|L], P, Depth1, Debug).
</div>

<div class="nb-cell query" name="q4">
path(estação(morumbi), estação(tucuruvi), P).
</div>

</div>