Trees spanning

Description

Program finds a spanning tree of a graph and program assumes that the graph is connected.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: trees_spanning.pl

Listing

```% Figure 9.22   Finding a spanning tree of a graph: an `algorithmic' % program. The program assumes that the graph is connected.

% Finding a spanning tree of a graph
%
% Trees and graphs are represented by lists of their edges.
% For example: Graph = [a-b, b-c, b-d, c-d]

% stree( Graph, Tree): Tree is a spanning tree of Graph

stree( Graph, Tree)  :-
member( Edge, Graph),

% spread( Tree1, Tree, Graph): Tree1 `spreads to' spanning tree Tree of Graph

not(addedge( Tree, _, Graph)). % No edge can be added without creating a cycle

%   add an edge from Graph to Tree without creating a cycle

addedge( Tree, [A-B | Tree], Graph)  :-
adjacent( A, B, Graph),          % Nodes A and B adjacent in Graph
node( A, Tree),                  % A in Tree
not(node( B, Tree)).              % A-B doesn't create a cycle in Tree 