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

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