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

## Download

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( [Edge], Tree, Graph).

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

spread( Tree1, Tree, Graph)  :-
addedge( Tree1, Tree2, Graph),
spread( Tree2, Tree, Graph).

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

% addedge( Tree, NewTree, Graph):
%   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

adjacent( Node1, Node2, Graph)  :-
member( Node1-Node2, Graph)
;
member( Node2-Node1, Graph).

node( Node, Graph)  :-             % Node is a node in Graph if
adjacent( Node, _, Graph).       % Node is adjacent to anything in Graph
```

## Comments

pl/prolog/pllib/trees_spanning.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna) 