Ответ в теме: Алгоритм Крускала – минимальное остовное дерево на Prolog

      Комментарии к записи Ответ в теме: Алгоритм Крускала – минимальное остовное дерево на Prolog отключены
#2821

За основу можно взять программу, выполняющую ввод и вывод графа — однако граф там является невзвешенным (его ребра не имеют вес), а в алгоритме Крускала минимизируется суммарный вес подграфа. Кроме того, в алгоритме используется лес — в теории графов так называют множество деревьев, для него нам нужно будет объявить дополнительный тип данных:

DOMAINS
	node_d = string
	edge_d = edge(node_d, node_d, integer)
	
	nodes_d = node_d*
	edges_d = edge_d*
	
	branching_d = nodes_d*

В базе данных будет храниться граф в виде набора вершин и дуг:

DATABASE
	node(node_d)
	edge(node_d, node_d, integer)

kruskal_algorithm_flowchart Блок-схема алгоритма Крускала

В алгоритме можно выделить подготовительный этап, связанный с сортировкой списка ребер и построением набора деревьев из вершин, вынесем его в отдельную функцию:

kruskal_minimum_spanning_tree_algorithm(SpanningTree):-
	findall(Edge, get_edge(Edge), Edges),
	findall(Node, node(Node), Nodes), 
		
	qsort(Edges, SortedEdges),
	nodes_to_branching(Nodes, Branching),
		
	kruskal_minimum_spanning_tree_algorithm(SortedEdges, Branching, [], SpanningTree).

Эта функция:

  1. собирает все дуги графа с помощью стандартного предиката findall и функции get_edge, возвращающей дугу. Вспомогательная функция нужна в связи с тем, что Visual Prolog не разрешает следующее поведение findall: findall(edge(From, To, Distance), edge(From, To, Distance), Edges). Поэтому мы вынуждены написать вспомогательную функцию, которая завернет дугу графа в нужную нам структуру:
    % nondeterm get_edge(edge_d)
    get_edge(edge(From, To, Dist)):-
      	edge(From, To, Dist).

  2. Функция qsort выполняет быструю сортировку списка, однако для сравнения элементов (дуг) нужно использовать вспомогательную функцию:
    edge_less(edge(_AFrom, _ATo, ALen), edge(_BFrom, _BTo, BLen)):-
    	ALen >= BLen.

  3. для построения начального списка деревьев, которые во время работы алгоритма будут объединяться, каждый узел графа нужно поместить в отдельный список. Все деревья будут при этом являться элементами списка:
    nodes_to_branching([], []):-!.
    nodes_to_branching([Head|Tail], [[Head]|TailBranching]):-
    	nodes_to_branching(Tail, TailBranching).

В основном цикле алгоритма Крускала последовательно выбираются заранее отсортированные дуги. Для каждой дуги выполняется поиск деревьев, содержащих начало и конец дуги. Для поиска узла внутри дерева можно применить функцию member, но дерево мало найти — нужно выполнить его удаление из списка, т.к. деревья, содержащие начало и конец должны объединиться. Одновременно поиск и удаление элементов может выполняться с помощью функции select. Соединение деревьев может быть выполнено с помощью предиката append:

kruskal_minimum_spanning_tree_algorithm(_SortedEdges, [_Tree], Buffer, Buffer):-!.
kruskal_minimum_spanning_tree_algorithm([edge(From, To, Distance)|TailEdges], Branching, Buffer, SpanningTree):-
	select(ToTree, Branching, BranchingWithoutTo), member(To, ToTree),
	select(FromTree, BranchingWithoutTo, BranchingWithoutToFrom), member(From, FromTree),
	NOT(ToTree = FromTree), 
	append(ToTree, FromTree, ToFromTree), !,
	kruskal_minimum_spanning_tree_algorithm(
		TailEdges,  
		[ToFromTree|BranchingWithoutToFrom], 
		[edge(From, To, Distance)|Buffer], 
		SpanningTree
	);
	kruskal_minimum_spanning_tree_algorithm(TailEdges, Branching, Buffer, SpanningTree).

Функции select, memeber и append являются встроенными в SWI Prolog, однако в Visual Prolog и Turbo Prolog их нужно реализовывать вручную.

Приведенный фрагмент алгоритма:

  1. выбирает первую дугу из упорядоченного списка;
  2. удаляет из леса деревья, содержащие начало и конец дуги;
  3. если начало и конец принадлежат разным деревьям — деревья объединяются и обрабатываются рекурсивно;
  4. если же они принадлежат одному дереву — дуга пропускается и рекурсивно обрабатываются остальные