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

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

Рис. 9.11. Примеры графов: а) простой граф; б) ори­ентированный граф со стоимостями, назначенными дугам

Графы могут быть представлены на языке Prolog несколькими методами. Один из методов состоит в том, чтобы каждое ребро или каждая дуга были представлены от­дельно, в виде одного предложения. Поэтому графы, показанные на рис. 9.11, могут быть представлены с помощью множеств предложений, например, следующим образом:

connected! а, Ь). connected! Ь, с).

arc< s, t, 3). atc(t, v, 1). arc(u, t, 2).

Еще один метод состоит в том, что весь граф может быть представлен как один объект данных. Поэтому граф представляется как пара из двух множеств: узлы и ребра. Каждое множество узлов можно представить как список, а каждое ребро в множестве ребер - как пару узлов. Для объединения обоих множеств в пару выбе­рем функтор graph, а для представления ребер будем применять функтор е. Таким образом, один из методов представления (неориентированного) графа, показанного на рис. 9.11, выглядит таким образом: G1 = graph; ta,b,c,dj. te(a,b}, e(b,dj, e(b,c), e;c,d;]|

Для представления ориентированного графа можно выбрать функторы digraph и а (для дуг). Поэтому ориентированный граф, показанный на рис. 9.11,. принимает следующий вид: G2 = digraph! [s,t,u,v], [a(s,t,3>, a{t,v,l), a(t,u,5), a[u,t,2), a(v,u_f2Jl>

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

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

Часть I. Язык Prolog

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

S1 - [ а -> [b], b -> [a,C,dJ, с -> [Ь,й], d -> [b,c) ]

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

Безусловно, приведенные выше символы "->" и "/" представляют собой инфикс­ные операторы.

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

• Поиск пути между двумя указанными узлами,

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

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