Różnice między wybraną wersją a wersją aktualną.
| — |
pl:prolog:pllib:trees_spanning [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== Trees spanning ====== | ||
| + | {{tag>trees}} | ||
| + | ===== 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 ===== | ||
| + | <code prolog> | ||
| + | % 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 | ||
| + | |||
| + | </code> | ||
| + | ===== Comments ===== | ||
