Чтение онлайн

(2) отпечатать корень дерева Т;

(3) отобразить левое поддерево дерева Т с отступом вправо на расстояние Н.

Величина отступа Н, которую можно выбирать по желанию, - это дополнительный параметр при отображении деревьев. Введем процедуру

отобр2( Т, Н)

печатающую дерево Т с отступом на Н пробелов от левого края листа. Связь между процедурами отобр и отобр2 такова:

отобр( Т) :- отобр2( Т, 0).

На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.

отобр( Т) :-

отобр2( Т, 0).

отобр2( nil, _ ).

отобр2( дер( L, X, R), Отступ) :-

Отступ2 is Отступ + 2,

отобр2( R, Отступ2),

tab( Отступ), write( X), nl,

отобр( L, Отступ2).

Рис. 9. 17. Отображение двоичного дерева.

Упражнение

9. 14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья - справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.

Посмотреть ответ

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

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

9. 5. Графы

9. 5. 1. Представление графов

Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершин вместе с множеством ребер, причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На рис. 6.18 показаны примеры графов.

В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Например, графы, показанные иа рис. 9.18, можно представить в виде следующего множества предложений:

связь( а, b).

связь( b, с).

. . .

дуга( s, t, 3).

дуга( t, v, 1).

дуга( u, t, 2).

. . .

Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р. Тогда (ненаправленный) граф рис. 9.18 примет вид:

G1 = граф( [a, b, c, d],

[р( а, b), р( b, d), р( b, с), p( c, d)] )

Рис. 9. 18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.

Для представления направленного графа (рис. 9.18), применив функторы диграф и д (для дуг), получим

G2 = диграф( [s, t, u, v],

[д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),

д( v, u, 2) ] )

Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер.

Еще один способ представления графа - связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (рис. 9.18), например, можно представить как

G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]

G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]

Здесь символы '->' и '/' - инфиксные операторы.

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

найти путь между двумя заданными вершинами;

найти подграф, обладающий некоторыми заданными свойствами.

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

9. 5. 2. Поиск пути в графе

Пусть G - граф, а А и Z - две его вершины. Определим отношение

путь( А, Z, G, Р)

где Р - ациклический путь между А и Z в графе G. Если G - граф, показанный в левой части рис. 9.18, то верно:

путь( a, d, G, [a, b, d] )

путь( а, d, G, [a, b, c, d] )

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

Для того, чтобы найти ациклический путь Р между А и Z в графе G, необходимо:

Если А = Z , то положить Р = [А], иначе найти ациклический путь Р1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из Р1.