% nacteni:
/* ['2.10_23.pl']. */

stree(Graph,Tree) :- member(Edge,Graph),spread([Edge],Tree,Graph).
spread(Tree1,Tree,Graph) :- addedge(Tree1,Tree2,Graph),spread(Tree2,Tree,Graph).
spread(Tree,Tree,Graph) :- \+ addedge(Tree,_,Graph).
addedge(Tree,[A-B|Tree],Graph) :- adjacent(A,B,Graph),node(A,Tree), \+ node(B,Tree).
adjacent(A,B,Graph) :- member(A-B,Graph);member(B-A,Graph).
node(A,Graph) :- adjacent(A,_,Graph),!.

% demonstracni vypis

  % abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
       write_all_X/3,
       start/0.

write_all_X(Goal,X,Name):-
            call(Goal),write('  '),write(Name),write(' = '),write(X),nl,fail.
write_all_X(_,_,_).

start:- 
    write('Kostra grafu'),nl,
    write('Volani "stree([a-b,b-c,b-d,c-d],T)" vrati:'),nl,
    write_all_X(stree([a-b,b-c,b-d,c-d],T), T, 'T').

?-start.

:- retractall(write_all_X/3).
:- retractall(start/0).

Kostra grafu
Volani "stree([a-b,b-c,b-d,c-d],T)" vrati:
  T = [b-d,b-c,a-b]
  T = [c-d,b-c,a-b]
  T = [b-c,b-d,a-b]
  T = [d-c,b-d,a-b]
  T = [b-a,b-d,b-c]
  T = [b-a,c-d,b-c]
  T = [b-d,b-a,b-c]
  T = [c-d,b-a,b-c]
  T = [b-a,b-c,b-d]
  T = [b-c,b-a,b-d]
  T = [d-c,b-a,b-d]
  T = [b-a,d-c,b-d]
  T = [b-a,c-b,c-d]
  T = [b-a,d-b,c-d]