Поиск остовного дерева графа
Граф называется связным, если в нем имеется путь от любого узла до любого другого узла. Предположим, что 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, если
... adjacentf 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, Node2p 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) .