Структури графів використовуються в багатьох додатках, таких як представле-ня відносин, ситуацій або проблем. Граф визначається як безліч вузлів і безліч ребер, в якому кожне ребро з'єднує пару вузлів. Якщо ребра являють-ся орієнтованими, вони іменуються також дугами. Дуги представляються за допомогою на-гою упорядкованих пар вузлів. Такий граф називається орієнтованим. Ребрах можуть бути поставлені у відповідність вартості, імена або позначення будь-якого ро-да, в залежності від програми. Приклади графів показані на рис, 9.11.
Мал. 9.11. Приклади графів: а) простий граф; б) ори-ентірованний граф з вартостями, призначеними дуг
Графи можуть бути подані мовою Prolog декількома методами. Один з методів полягає в тому, щоб кожне ребро або кожна дуга були представлені від-но, у вигляді одного речення. Тому графи, показані на рис. 9.11, можуть бути представлені за допомогою множин пропозицій, наприклад, наступним чином:
connected! а, Ь). connected! Ь, с).
Ще один метод полягає в тому, що весь граф може бути представлений як один об'єкт даних. Тому граф представляється як пара з двох множин: вузли та ребра. Кожне безліч вузлів можна уявити як список, а кожне ребро в безлічі ребер - як пару вузлів. Для об'єднання обох множин в пару вибе-рем функтор 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>, af 2Jl>
Якщо кожен вузол пов'язаний, щонайменше, ще з одним вузлом, то можна ис-ключить з цього подання список вузлів, оскільки в такому випадку безліч вузлів неявно задано списком ребер.
Ще один метод полягає в тому, щоб кожен вузол був пов'язаний зі списком вузлів, суміжних по відношенню до цього вузла. В цьому випадку граф являє собою список
Частина I. Мова Prolog
пар, що складається з вузла і відповідного йому списку суміжності. Тому графи, що розглядаються в якості прикладів, можна представити таким чином;
Безумовно, наведені вище символи "->" і "/" представляють собою Інфікси-ні оператори.
Вибір найбільш гідного представлення залежить від програми і від того, які операції повинні виконуватися з графами. Дві найпоширеніші опе-рації полягають у наступному.
• Знайдіть свій шлях між двома зазначеними вузлами,
• Пошук в графі такого подграфа, який володіє деякими заданими
властивостями.
Прикладом операції останнього типу є пошук остовного дерева графа. У наступних розділах розглядаються деякі прості програми пошуку шляху і формування остовного дерева.