| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Prolog] Минимальное остовное дерево |
| Автор: Arun 12.2.2008, 15:43 |
| Дан взвешенный граф. Необходимо вычислить связный подграф, включающий все вершины исходного графа, и суммарный вес которого минимален. сама не разбираюсь в языке, а когда искала находила тока в других средах разработки =\ /* * Алгоритм Краскала */ kruskal(Vertices, Edges, MinimalSpanningTree):- listify(Vertices, Components), insertion_sort(Edges, SortedEdges), kruskal_1(Components, SortedEdges, MinimalSpanningTree). 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([], []). listify([X|Xs], [[X]|Yss]):- listify(Xs, Yss). 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). это похожая задача, но препод не принимает =\ |