Программирование на языке Пролог для искусственного интеллекта



         

Построение остовного дерева - часть 2


Программа, реализующая эту идею, показана на рис. 9.22. Основное отношение, используемое в этой программе, - это

        расширить( Дер1, Дер, G)

Здесь все три аргумента - множества ребер.  G

-

line();

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

%

%  Деревья и графы представлены списками

%  своих ребер, например:

%            Граф = [а-b, b-с, b-d, c-d]

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

                           % Дер - остовное дерево Граф'а

                принадлежит( Ребро, Граф),

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

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

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

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

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

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

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

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

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

                           % А и В - смежные вершины



Содержание  Назад  Вперед