ПРЕДСТАВЛЕНИЕ ГРАФОВ В TURBO PROLOG

Графы в Прологе могут представляться многими способами. Рассмотрим некоторые из них на модельном графе (рис. 8.2).

рис. 8.2

Первый способ — перечислить ребра графа в виде утверждений базы данных (для неориентированного графа каждое ребро повторяется дважды):

after(1,2). after(2,1). after(1,3). after(3,1).

after(1,4). after(4,1). after(2,3). after(3,2).

after(2,5). after(5,2). after(3,4). after(4,3).

after(5,4). after(4,5).

Однако, для многих алгоритмов более предпочтительным представлением являются СПИСКИ ИНЦИДЕНТНОСТИ (когда к каждой вершине прицеплен список соседок — смежных с ней вершин):

graph([1,2,3,4]).

graph([2,3,1,5]).

graph([3,1,2,4]).

graph([4,1,3,5]).

graph([5,2,4]).

Голова списка — сама вершина, хвост — список ее соседок.

Граф можно хранить в виде динамической структуры — списка списков — и передавать ее в качестве аргумента из процедуры в процедуру:

domains

uzl=integer

list=uzl*

llist=list*

<.............>

goal

Graph = [[1,2,3,4],[2,1,3,5],[3,1,2,4],[4,1,3,5],[5,2,4] ], <....>.

Для «нагруженных» графов, ребрам которых приписаны веса (или стоимости) нужно произвести некоторые изменения:

у предиката after появится третий аргумент — вес ребра:

after1(1,2,3).

after1(2,1,3). /* вес ребра 1-2 равен 3*/;

у предиката graph появится второй аргумент — список весов соответствующих ребер:

graph1([5,2,4], [5,1]).

/* вес ребра 5-2 равен 5, ребра 5-4 равен 1 */.

К динамическому списку списков, представляющему граф, нужно добавить еще один список списков — с весами соответствующих ребер.

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

num_reb(7).

num_uzl(5).