# Minimum Spanning Tree of weighted undirected graph

163 views

### Hannes Wiedenhofer

Apr 30, 2018, 7:42:24 AM4/30/18
to SWI-Prolog

I need to write a predicate that creates a minimum spanning tree of a weighted undirected graph, using Prim's Algorithm. How do I approach this problem?

The graph consists of multiple `edge(v1, v2, length)` predicates.

A minimum spanning tree is the shortest path that connects all edges without cycles.

Prim's algorithm:

Pick one arbitrary node and add it to the visited list.

Choose the smallest edge that connects it to another node.

Add that node to the visited list.

Look at all the nodes in the visited list and pick the smallest edge connected to one of them.

Add that node to the visited list.

Continue like this.

If the smallest edge connects two nodes that are already in the visited list, do not pick it.

### Kuniaki Mukai

May 1, 2018, 7:02:32 AM5/1/18
to Hannes Wiedenhofer, SWI-Prolog
As far as I understand your description of the problem correctly,  the builtins  setof/3 or findall/3 might be
useful for solving the problem.  It seems fairy easy with them but difficult without them, at leas for me.

Kuniaki Mukai

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.

### Hannes Wiedenhofer

May 1, 2018, 7:28:21 AM5/1/18
to SWI-Prolog
It doesn't seem that easy for me.

% call the method with the list of all nodes as argument
msp(T) :- nodes(L), msp(T,L).

msp(T, [H|T] :- msp_1(H,T).

% the recursive step using setof (this is where I have problems)
msp_1(T, L) :- setof(C, connection(L, X, C), Y), ...?

### Kuniaki Mukai

May 1, 2018, 8:03:50 AM5/1/18
to Hannes Wiedenhofer, SWI-Prolog

On May 1, 2018, at 20:28, Hannes Wiedenhofer <hon...@gmail.com> wrote:

It doesn't seem that easy for me.

By this, all nodes are collected into a list.

allnodes(Nodes):- findall(X, (connect(X,_,_); connect(_,X,_)), Bag),  sort(Bag, Nodes).

minimum_weight(M) :-  allnodes(Nodes),  solve(Nodes, [],  _,  0, M).

where solve/5 is a main predicate, say

solve(Nodes, Visitted, NewVisited, TotalWeight, NewTotalWeight)

which describe transitions of computation configurations (S,V,W),
where S is a set of nodes not yet in the visited list,
V is the visited list,  W is the weight.

(S, V, W)          ->            (S-{x], V+{x}, W+w)

select node x from S and weight w according to the condition of the problem

Hope this help.

Kuniaki Mukai