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

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

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

2. Использование списка.

Пример 57:

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

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

domains

top=symbol

predicates

edge (top, top)

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

connected(top,top)

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

clauses

edge (a, b).

edge (c, d).

edge (a, c).

edge (d, e).

edge (b, d).

edge (f, g).

connected (X, X).

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

Пример 58:

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

domains

edge= e(symbol, symbol)

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

list1=symbol*

list2=edge*

graf = g(list1, list2)

predicates

connected(graf, symbol, symbol)

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

clauses

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

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

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

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

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

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

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

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

goal

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

Дата добавления: 2015-06-27