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

Граф называется связным, если в нем имеется путь от любого узла до любого дру­гого узла. Предположим, что G = (v, 7, I - связный граф с множеством узлов V и множеством ребер Е. Остовным деревом графа G является связный граф Г = (V, Е '), где £ ' • •-• подмножество множества Е, такое, что:

1. Т является связным;

2. в Т нет ни одного цикла.

Глава 9. Операции СО струоурами данных

Эти два условия гарантируют, что Т представляет собой дерево. Для графа, пока­занного на рис. 9.11, а, имеются три остовных дерева, которые соответствуют сле­дующим трем спискам ребер:

Treel - [a-b, b-c, c-d] Тгее2 = [a-b, b-d, d-c] ТгееЗ = [a-b, b-d, b-c]

где каждый терм в форме X-Y обозначает ребро между узлами X и Y. В таком списке в качестве корня дерева может быть выбран любой узел. Остовные деревья представ­ляют интерес, например, в проблематике сетей связи, поскольку они позволяют соз­давать соединения между любыми парами узлов с помощью минимального количест­ва линий связи.

Определим следующую процедуру: stree [ G, Т)

где Т — остовное дерево графа G. Мы исходим из предположения, что граф G являет­ся связным. Алгоритмически можно представить процесс формирования остовного дерева следующим образом: начать с пустого множества ребер и постепенно добав­лять из графа G все новые ребра, следя за тем, чтобы не создавался цикл, до тех пор, пока не возникнет ситуация, при которой больше нельзя будет добавлять ребра, по­скольку это приведет к созданию цикла. Полученное в результате множество ребер определяет остовное дерево. За соблюдением условия отсутствия цикла можно сле­дить с помощью следующего простого правила: любое ребро можно добавлять, только если один из его узлов уже находится в растущем дереве, а другой узел — еще нет. Программа, которая реализует этот замысел, приведена в листинге 9.10. Основным отношением этой программы является следующее: spread: Treel, Tree, G]

Листинг 9.10. Поиск остовного дерева графа: "алгоритмическая" программа; в этой программе принято предположение, что граф является связным

% Поиск'остовного дерева графа

" Деревья и графы представлены списками ix ребер. *г Например, Graph = [а-Ь, Ь-с, b-d, c-d]

I stree{ Graph, Tree): Tree - остовное дерево графа Graph

street Graph, Tree;:-member! Edge, Graph), spread! [Edge], Tree, Graph).

% spread!" Treel, Tree, Graph): дерево Treel "расширяется"
% КО остовного дерева Tree графа Graph

spread' Treel, Tree, Graph):-addedge(Treel, Tree2, Graph), spread! Tree2, Tree, Graph).

spread! Tree, Tree, Graph):-

not addedge! Tree, _, Graph). - Нельзя ввести ни одного ребра, не создав цикл %addedge(Tree, HewTree, Graph):

добавить ребро графа Graph в дерево Tree, не создавая цикл

addedge(Tree, [A-B | Tree], Graph):-

adjacent! A, В, Graph),: Узлы "> и В в графе Graph являются смежными

node! A, Tree), % Узел А находится в дереве Tree

not node! В, Tree). % Ребро А-В не создает цикл в дереве Tree

adjacent С Node!, Node2, Graph):-member £ Hodel-Node2, Graph)

member{ Hode2-Model, Graph).

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

node! Mode, Graph]:- % Node - узел графа Graph, если

... adjacent f Mode,, Graph]. % он является смежным с любым узлом графа Graph

Все три параметра этого отношения представляют собой множества ребер. G — это связный граф, Treel и Tree - подмножества графа G, такие, что оба они являются деревьями. Tree — это остовное дерево графа G, полученное путем добавления ребер графа G в дерево Treel (в количестве от нуля и больше). Такую операцию можно описать словесно так, что "дерево Treel было расширено до Tree" (отсюда и назва­ние процедуры — spread).

Любопытно отметить, что может быть также создана работоспособная программа для формирования остовного дерева на основе иного, полностью декларативного под­хода, при котором задаются математические определения. Предположим, что и графы, к деревья представлены в виде списков их ребер, как в программе из листинга 9.IQ. Для разработки программы необходимо ввести приведенные ниже определения.

1. Т — остовное дерево С-, если одновременно выполняются следующие условия:

• Т — подмножество G,

• Т — дерево,

• Т "покрывает" G, т.е. каждый узел G находится также в Т.

2. Множество ребер Т представляет собой дерево, если одновременно выполняют­
ся следующие условия:

• Т связно,

• Т не имеет циклов.

С помощью программы path (см. предыдущий раздел) эти определения можно сформулировать на языке Prolog, как показано в листинге 9.11. Но следует отме­тить, что данная программа в такой форме не представляет практического интереса из-за ее неэффективности.

Листинг 9.11, Поиск остовного дерева графа: "декларативная" программа; отношения node иadjacentприведены в листинге 9,10

% Поиск остовного дерева

I Графы и деревья представлены как списки ребер

¥ street Graph, Tree): Tree - Остовное дерево графа Graph

stree (Graph, Tree):-subset! Graph, Tree), tree(Tree), coverst Tree, Graph).

tree(Tree):-

connected; Tree),

not hasacycle! Tree). % connected(Graph): есть путь между любыми двумя узлами в Графе Graph

connected) Graph):-

not { node! A, Graph), node (3, Graph), not path! ft, B, Graph, _)).

hasacycle! Graph):-

adjacent; Model, Node2_p Graph),

path! Model, Node2, Graph, [Model, X, Y | _] ). % Путь имеет длину больше 1

% covets! Tree, Graph): каждый узел графа Graph находится в дереве Tree

covers) Tree, Graph):-

not (node! Bode, Graph), not node (Node, Tree)).

Глава 9. Операции со структурами данных

% subsetf Listl, List2); список List2 представляет собой П<5ДМКОЖес«В0 Llstl

subset ([], []).

subset! [X I Set], Subset):- % Элемент X м находится в подмножестве subset) Set, Subset).

subset([X I Set], [X I Subset)):- >6 Элемент Х включен в подмножество subset f Set, Subset).