Minimal Spanning Tree of a Graph

Given a weighted undirected graph G with vertices V, edges E, and a non-negative weight for each edge in E, then a spanning tree for G is a tree which is a subgraph of G and contains all the vertices V of G. A minimal spanning tree is one for which the sum of the weights on its edges is less than or equal to the sum of the weights on the edges of any other spanning tree for G.

/*
 * Kruskal's Algorithm
 */
 
/* kruskal(Vertices, Edges, MST) is true if MST are the edges of a minimal */
/*   spanning tree of the graph specified by the Vertices and Edges.       */
/* e.g. kruskal([1,2,3,4,5],
                [e(3,4,3),e(1,2,5),e(4,5,6),e(1,5,1),e(2,4,3),e(2,3,3)], 
                [e(1,5,1),e(2,4,3),e(2,3,3),e(1,2,5)]).                    */
kruskal(Vertices, Edges, MinimalSpanningTree):-
  listify(Vertices, Components),
  insertion_sort(Edges, SortedEdges),
  kruskal_1(Components, SortedEdges, MinimalSpanningTree).

/* e.g. kruskal_1([[1],[2],[3],[4],[5]],
                  [e(1,5,1),e(3,4,3),e(2,4,3),e(2,3,3),e(1,2,5),e(4,5,6)], 
                  [e(1,5,1),e(2,4,3),e(2,3,3),e(1,2,5)]).                  */
kruskal_1([_], _, []):-!.
kruskal_1(Components, [e(A,B,C)|Edges], [e(A,B,C)|MinimalSpanningTree]):-
  member_of_member(Components, A, Comp1, Components1),
  member_of_member(Components1, B, Comp2, Components2), !,
  ord_union(Comp1, Comp2, Comp),
  kruskal_1([Comp|Components2], Edges, MinimalSpanningTree).
kruskal_1(Components, [_|Edges], MinimalSpanningTree):-
  kruskal_1(Components, Edges, MinimalSpanningTree).

/* listify(Xs, Yss) is true if each element of the list of lists Yss is    */
/*   the list containing the corresponding element of Xs.                  */
/* e.g. listify([1,2,3], [[1],[2],[3]]).                                   */
listify([], []).
listify([X|Xs], [[X]|Yss]):-
  listify(Xs, Yss).

/* member_of_member(Xss, X, Xs, Zss) is true if X is a member of the       */
/*   ordered set Xs, which is a member of the list of lists Xss, and Zss   */
/*   is the result of deleting Xs from Xss.                                */
/* e.g. member_of_member([[1,5],[2,4],[3]], 2, [2,4], [[1,5],[3]]).        */
member_of_member([Xs|Xss], X, Xs, Xss):-
  ord_member(X, Xs).
member_of_member([Xs|Xss], X, Ys, [Xs|Zss]):-
  member_of_member(Xss, X, Ys, Zss).
  
/*
 * Prim's Algorithm
 */
 
/* prim(Vertices, Edges, MST) is true if MST are the edges of a minimal    */
/*   spanning tree of the graph specified by the Vertices and Edges.       */
/* e.g. prim([1,2,3,4,5],
             [e(3,4,3),e(1,2,5),e(4,5,6),e(1,5,1),e(2,4,3),e(2,3,3)], 
             [e(1,5,1),e(1,2,5),e(2,4,3),e(3,4,3)]).                       */
prim(Vertices0, Edges, MinimalSpanningTree):-
  sort(Vertices0, [Vertex|Vertices]),
  insertion_sort(Edges, SortedEdges),
  prim_1(Vertices, [Vertex], SortedEdges, MinimalSpanningTree).

prim_1([], _, _, []):-!.
prim_1(VBs, Bs, Edges, [Edge|MinimalSpanningTree]):-
  prim_2(Edges, VBs, Bs, Edge, Vertex),
  remove(Edge, Edges, Edges1),
  remove(Vertex, VBs, VBs1), !,
  ord_insert(Bs, Vertex, Bs1),
  prim_1(VBs1, Bs1, Edges1, MinimalSpanningTree).

prim_2([e(U,W,_)|_], VBs, Bs, e(U,W,_), U):-
  ord_member(U, VBs),
  ord_member(W, Bs), !.
prim_2([e(U,W,_)|_], VBs, Bs, e(U,W,_), W):-
  ord_member(U, Bs),
  ord_member(W, VBs), !.
prim_2([_|Edges], VBs, Bs, Edge, U):-
  prim_2(Edges, VBs, Bs, Edge, U).

/* insertion_sort(Xs, Zs) is true if Zs is a sorted permutation of the     */
/*   list Xs.                                                              */
insertion_sort(Xs, Ys):-insertion_sort_1(Xs, [], Ys).

insertion_sort_1([], Ys, Ys).
insertion_sort_1([X|Xs], Ys0, Ys):-
  insert(Ys0, X, Ys1),
  insertion_sort_1(Xs, Ys1, Ys).

insert([Y|Ys], X, [Y|Zs]):-le(Y, X), !, insert(Ys, X, Zs).
insert(Ys, X, [X|Ys]).

/* le(Edge1, Edge2) is true if the cost of Edge1 is less than or equal to  */
/*   the cost of Edge2.                                                    */
le(e(_,_,Cost1), e(_,_,Cost2)):-Cost1 =< Cost2.

/* ord_insert(Xs, Y, Zs) is true if Zs is the ordered list resulting from  */
/*   inserting Y into the ordered list Xs, without duplicates.             */
ord_insert([Y|Xs], Y, [Y|Xs]):-!.
ord_insert([X|Xs], Y, [X|Ws]):-X @< Y, !, ord_insert(Xs, Y, Ws).
ord_insert(Xs, Y, [Y|Xs]).

/* ord_member(X, Set) is true if X is a member of the ordered set Set.     */
ord_member(X, [X|_]):-!.
ord_member(X, [Y|Xs]):-Y @< X, ord_member(X, Xs).
  
/* ord_union(Set1, Set2, Union) is true if Set1 and Set2 are the ordered   */
/*   representations of two sets and Union is unified with the ordered     */
/*   representation of their union.                                        */
ord_union([], Ys, Ys). 
ord_union([X|Xs], [], [X|Xs]):-!. 
ord_union([X|Xs], [X|Ys], [X|Zs]):-!, ord_union(Xs, Ys, Zs).
ord_union([X|Xs], [Y|Ys], [X|Zs]):-X @< Y, !, ord_union(Xs, [Y|Ys], Zs).
ord_union([X|Xs], [Y|Ys], [Y|Zs]):-X @> Y, !, ord_union([X|Xs], Ys, Zs).

go:-
  /* www.ececs.uc.edu/~cpurdy/lec21.html */
  kruskal([1,2,3,4,5],
          [e(3,4,3),e(1,2,5),e(4,5,6),e(1,5,1),e(2,4,3),e(2,3,3)], 
          [e(1,5,1),e(2,4,3),e(2,3,3),e(1,2,5)]),
  prim(   [1,2,3,4,5],
          [e(3,4,3),e(1,2,5),e(4,5,6),e(1,5,1),e(2,4,3),e(2,3,3)], 
          [e(1,5,1),e(1,2,5),e(2,4,3),e(3,4,3)]),

  /* Bratko - Figure 9.18(a) */
  kruskal([1,2,3,4],
          [e(1,2,3),e(4,2,2),e(2,3,1),e(3,4,2)],
          [e(2,3,1),e(4,2,2),e(1,2,3)]),
  prim(   [1,2,3,4],
          [e(1,2,3),e(4,2,2),e(2,3,1),e(3,4,2)],
          [e(1,2,3),e(2,3,1),e(4,2,2)]),
  
  /* Nilson */
  kruskal([a,b,c,d,e],
          [e(a,b,4),e(b,c,2),e(c,d,1),e(d,e,3),e(e,a,5),e(e,b,2)],
          [e(c,d,1),e(b,c,2),e(e,b,2),e(a,b,4)]).

LPA Index     Home Page