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

Для представления графов в языке Пролог можно использовать три способа:

1. Использование факта языка Пролог для описания дуг или рёбер графа.

2. Использование списка или структуры данных для объединения двух списков: списка вершин и списка рёбер.

3. Использование списка списков: каждый подсписок в качестве головы содержит вершину графа, а в качестве хвоста - список смежных вершин.

Две самые распространённые операции, которые выполняются над графами:

· Поиск пути между двумя вершинами;

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

Пример 74:

Определить наличие связи между вершинами графа, представленного на рисунке:

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

domains

top=symbol

predicates

edge (top, top)

/* аргументы обозначают имена вершин */

path( top,top)

/*Предикат connected(symbol, symbol) определяет отношение связанности вершин.*/

clauses

edge (a, b).

edge (c, d).

edge (a, c).

edge (d, e).

edge (b, d).

edge (f, g).

path (X, X).

path (X, Y):- edge (X, Z), path (Z, Y).

Пример 75:

Решить задачу из примера 74, используя списочные структуры для представления графа. Граф задается двумя списками: списком вершин и списком ребер. Ребро представлено при помощи структуры edge.

domains

edge= e(symbol, symbol)

list=edge*

predicates

path(list, symbol, symbol)

member(list,edge)

/*предикат path(graf, symbol, symbol) определяет отношение связности вершин.*/

clauses

member([H|_],H).

member([_|T],X):-member(T,X).

%path ([],_,_):-fail.

path(L,X,Y):-member(L,e(X,Y)),!.

path(L,X,Y):-member(L,e(X,Z)),path(L,Z,Y).

goal

path ([e(a, b),e(b, c),e(a, f),e(c, d),e(f,d)], a, d).

%path ([e(a, b),e(c, d),e(a, c),e(d, e),e(b, d),e(f, g)], b, g).

Пример 76:

Решить задачу из примера 74, используя списочные структуры для представления графа. Граф задается списком списков: в каждом подсписке голова является вершиной, а хвост – списком смежных вершин.

domains

edge= e(symbol, symbol)

/* аргументы обозначают имена вершин */

list1=symbol*

list2=edge*

graf = g(list1, list2)

predicates

path(graf, symbol, symbol)

/*Предикат path(graf, symbol, symbol) определяет отношение связанности вершин в графе.*/

clauses

path (g([],[]),_,_).

path (g([X|_],[e(X,Y)|_]),X,Y).

%path (g([X|T],[e(X,_)|T1]),X,Y):-

%path (g([X|T],T1),X,Y).

path (g([X|T],[e(X,Z)|T1]),X,Y):-

path (g(T,T1),Z,Y).

path (g([Z|T],T1),X,Y):-Z<>X,

path (g(T,T1),X,Y).

path (g([X|T],[e(_,_)|T1]),X,Y):-

path (g([X|T],T1),X,Y).

goal

path (g([a, b, c, d],[e(a, b),e(b, c),e(a, d),e(c, e)]), b, e).