node(1).
node(2).
node(3).
node(4).
node(5).

edge(1, 2).
edge(1, 3).
edge(2, 4).
edge(3, 4).
edge(4, 5).

adj(X, Y) :-
    node(X), node(Y),
    (edge(X, Y); edge(Y, X)).

:- dynamic(queue/1).

queue_push(X) :-
    assertz(queue(X)).

queue_pop(X) :-
    queue(X),
    retract(queue(X)), !.

queue_info :-
    findall(X, queue(X), L),
    write(L).

:- dynamic(used/1).
:- dynamic(parent/2).

bfs(X, Y, P) :-
    retractall(queue(_)),
    retractall(used(_)),
    retractall(parent(_, _)),
    queue_push(X),
    assertz(used(X)),
    bfs_loop,
    bfs_find_path(X, [Y], P).

bfs_loop :-
    queue_pop(X),
    bfs_adj(X),
    bfs_loop, !;
    true.

bfs_adj(X) :-
    adj(X, T),
    \+ used(T),
    assertz(used(T)),
    assertz(parent(X, T)),
    queue_push(T),
    bfs_adj(X), !;
    true.

bfs_find_path(X, [X|Xs], [X|Xs]) :- !.
bfs_find_path(X, [Y|Ys], P) :-
    parent(T, Y),
    bfs_find_path(X, [T,Y|Ys], P).