Неизвестно - Prolog

расширить( [Ребро], Дер, Граф).

расширить( Дер1, Дер, Граф) :-

добребро( Дер1, Дер2, Граф),

расширить( Дер2, Дер, Граф).

расширить( Дер, Дер, Граф) :-

not добребро( Дер, _, Граф).

% Добавление любого ребра приводит к циклу

добребро( Дер, [А-В | Дер], Граф) :-

смеж( А, В, Граф), % А и В - смежные вершины

вершина( А, Дер). % А содержится в Дер

не вершина( В, Дер). % А-В не порождает цикла

смеж( А, В, Граф) :-

принадлежит ( А-В, Граф);

принадлежит ( В-А, Граф).

вершина( А, Граф) :- % А содержится в графе, если

смеж( А, _, Граф). % А смежна какой-нибудь вершине

Pис. 9. 22. Построение остовного дерева: алгоритмический подход.

Предполагается, что Граф- связный граф.

связный граф; Дер1и Дер- два подмножества G, являющиеся деревьями. Дер- остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из Gк Дер1. Можно сказать, что " Дер1расширено до Дер".

Интересно, что можно написать программу построения остовного дерева совершенно другим, полностью декларативным способом, просто формулируя на Прологе некоторые математические определения. Допустим, что как графы, так и деревья задаются списками своих ребер, как в программе рис. 9.22. Нам понадобятся следующие определения:

(1) Т является остовным деревом графа G, если

Т - это подмножество графа G и

Т - дерево и

Т "накрывает" G, т.е. каждая вершина из G содержится также в Т.

(2) Множество ребер Т есть дерево, если

Т - связный граф и

Т не содержит циклов.

Эти определения можно сформулировать на Прологе (с использованием нашей программы путьиз предыдущего раздела) так, как показано на рис. 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.

% Построение остовного дерева

% Графы и деревья представлены списками ребер.

остдерево( Граф, Дер) :-

подмнож( Граф, Дер),

дерево( Дер),

накрывает( Дер, Граф).

дерево( Дер) :-

связи( Дер),

not имеетцикл( Дер).

связи( Дер) :-

not ( вершина( А, Дер), вершина( В, Дер),

not путь( А, А, Дер, _ ) ).

имеетцикл( Дер) :-

смеж( А, В, Дер),

путь( А, В, Дер, [А, X, Y | _ ). % Длина пути > 1

накрывает( Дер, Граф) :-

not ( вершина( А, Граф), not вершина( А, Дер) ).

подмнож( [ ], [ ]).

подмнож( [ Х | L], S) :-

подмнож( L, L1),

( S = L1; S = [ Х | L1] ).

Рис. 9. 23. Построение остовного дерева: "декларативный подход".

Отношения вершинаи смежсм. на рис. 9. 22.

Упражнение

9. 15. Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимость остовного дерева определена как сумма стоимостей составляющих его ребер. Напишите программу построения для заданного графа его остовного дерева минимальной стоимости.

Резюме

В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе

Списки:

варианты представления списков

сортировка списков:

сортировка методом "пузырька"

сортировка со вставками

быстрая сортировка

эффективность этих процедур

Представление множеств двоичными деревьями и двоичными справочниками:

поиск элемента в дереве

добавление элемента

удаление элемента

добавление в качестве листа или корня

сбалансированность деревьев и его связь с

эффективностью этих операций

отображение деревьев

Графы:

представление графов

поиск пути в графе

построение остовного дерева

Литература

В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).