赋权图的最小生成树
我需要使用Prim's Algorithm编写一个谓词来创建加权无向图的最小生成树。这就是我到目前为止所知道的：
% call the recursive predicate with the list of all nodes and
% one element (in this case the last one).
mst(T) :- nodes(N), last(N,E), mst(T,N,E).
% The element E is added to the visited list and removed from the toVisit list.
mst(T,N,E) :- append(T,E,S), delete(R,E,L)...则应该根据连接到访问列表中任何节点的边的距离对toVisit列表进行排序。对如何做到这一点有什么建议吗？
Stack Overflow用户
发布于 2018-05-02 04:17:53
因此，首先让我们尝试从维基百科中创建一个解决方案来找到一棵生成树，而不是最小生成树：“无向图G的生成树T是一个包含G的所有顶点的子图，具有最小可能的边数”和“一棵树是一个没有圈的连通无向图。如果它跨越G (也就是说，它包括G的每个顶点)并且是G的一个子图(树中的每条边都属于G)，则它是图G的生成树”。在这个例子中，我考虑一个以这种方式构建的图：
graph(ListOfVertices,ListOfEdges)ListOfEdges的每个元素都是edge(X,Y,Cost)。
让我们构建一个创建树的谓词(在本例中是一个完全连接的图)。make_kn_weighted/4将每个节点的度数(Size)、边的代价的MinValue和MaxValue作为输入，并在graph(LV,Comb)中创建图形。
make_kn_weighted(Size,MinValue,MaxValue,graph(LV,Comb)):-
Size1 is Size+1,
make_ordered_list(1,Size1,LV),
find_all_combinations_weighted(LV,MinValue,MaxValue,[],Comb).
make_ordered_list(Max,Max,[]):- !.
make_ordered_list(I,Max,[I|T]):-
I < Max,
I1 is I+1,
make_ordered_list(I1,Max,T).
find_all_combinations_weighted([_],_,_,C,C):- !.
find_all_combinations_weighted([H|T],Min,Max,CT,CO):-
find_combinations_weighted(H,T,Min,Max,C),
append(CT,C,C1),
find_all_combinations_weighted(T,Min,Max,C1,CO).
find_combinations_weighted(_,[],_,_,[]):- !.
find_combinations_weighted(E,[H|T],Min,Max,[edge(E,H,V)|TE]):-
random(Min,Max,V),
find_combinations_weighted(E,T,Min,Max,TE).
?- make_kn_weighted(4,2,7,G).
G = graph([1, 2, 3, 4], [edge(1, 2, 6), edge(1, 3, 6), edge(1, 4, 5), edge(2, 3, 4), edge(2, 4, 5), edge(3, 4, 5)]).然后我们创建一个生成生成树的谓词：
spanning_tree(graph([N|T],Edges),graph([N|T],TreeEdges)) :-
generate_spanning_tree(T,Edges,TreeEdgesUnsorted),
sort(TreeEdgesUnsorted,TreeEdges).
generate_spanning_tree([],_,[]).
generate_spanning_tree(Curr,Edges,[Edge|T]) :-
select(Edge,Edges,Edges1),
get_vertices(Edge,X,Y),
is_connected_to_tree(X,Y,Curr),
delete(Curr,X,Curr1),
delete(Curr1,Y,Curr2),
generate_spanning_tree(Curr2,Edges1,T).
get_vertices(edge(X,Y),X,Y).
get_vertices(edge(X,Y,_),X,Y).
is_connected_to_tree(X,Y,Ns):-
memberchk(X,Ns),
\+ memberchk(Y,Ns), !.
is_connected_to_tree(X,Y,Ns):-
memberchk(Y,Ns),
\+ memberchk(X,Ns).因此，很明显，生成树和图都有相同的顶点，这就是我编写graph([N|T],Edges),graph([N|T],TreeEdges)的原因。为了生成实际的树，首先我们从列表中选择一个节点，使用select/3 (在Edges1中，我们有来自Edges的所有元素，没有Edge。然后，使用get_vertices/3，我们找到由一条边连接的两个顶点。使用is_connected_to_tree/3，我们检查两个顶点是否已经连接(在列表中或剩余的顶点中)。然后，我们将两条选定的边从未连接顶点列表(Curr)中删除，并对Curr应用两次delete/3。上一次调用，更新了参数的递归调用。测试：
?- make_kn(4,G), spanning_tree(G,T).
G = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(1, 4), edge(2, 3), edge(2, 4), edge(3, 4)]),
T = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(1, 4)]) ;
G = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(1, 4), edge(2, 3), edge(2, 4), edge(3, 4)]),
T = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(2, 4)])
and so on...现在让我们关注Primm的算法:为了调整我们的谓词以生成成本最低的树，我们首先考虑到每条边的成本对边进行排序，然后我们可以如上所述调用generate_spanning_tree/3。因此，在prolog代码中：
mst_prim(graph([H|T],Edges),graph([H|T],TreeEdges),Cost):-
predsort(compare_edges_value,Edges,SortedEdges),
generate_spanning_tree(T,SortedEdges,TreeEdgesUnsorted),
sort(TreeEdgesUnsorted,TreeEdges),
sum_cost(TreeEdges,0,Cost).
compare_edges_value(O,edge(X1,Y1,C1),edge(X2,Y2,C2)):-
compare(O,C1+X1+Y1,C2+X2+Y2).
sum_cost([],C,C).
sum_cost([edge(_,_,C)|T],CT,Tot):-
CT1 is CT+C,
sum_cost(T,CT1,Tot).predsort/3使用compare_edge/3进行排序以确定顺序。sum_cost/3只是简单地对每条选定边的成本求和。查询：
make_kn_weighted(4,2,7,G), mst_prim(G,T,C).
G = graph([1, 2, 3, 4], [edge(1, 2, 3), edge(1, 3, 6), edge(1, 4, 6), edge(2, 3, 5), edge(2, 4, 2), edge(3, 4, 2)]),
T = graph([1, 2, 3, 4], [edge(1, 2, 3), edge(2, 4, 2), edge(3, 4, 2)]),
C = 7 ;在回溯中，它会生成所有的生成树(如果你不想要这种行为，你可以在调用generate_spanning_tree/2之后添加一个cut )。
https://stackoverflow.com/questions/50116985
复制相似问题
腾讯云开发者
