На этом шаге мы рассмотрим реализацию такого алгоритма.
Теперь зададимся вопросом, какими свойствами будет обладать остовное дерево, построенное с помощью процедуры поиска в ширину?
При поиске в ширину просмотренные вершины располагаются в порядке неубывания их расстояния от начальной вершины. Поэтому в остовном дереве, построенном с помощью поиска в ширину, единственный путь, соединяющий какую-либо вершину с начальной, совпадает с кратчайшим путем в исходном графе между этими двумя вершинами.
Необходимые для построения остовного дерева с помощью поиска в ширину изменения в функции brfi более существенны по сравнению с аналогичными изменениями в функции defi. Дело в том, что при поиске в ширину нам не нужна была информация о предшественнике рассматриваемой вершины - в этом смысле поиск в ширину нелокален. Поэтому вместо очереди вершин, предназначенных для просмотра, мы введем очередь, состоящую непосредственно из элементов структуры смежности.
Приведем текст такой функции.
Раскрыть/скрыть текст примера.
-- Функция построения остовного дерева; -- graph - граф в виде структуры смежности; -- root - корень остовного дерева ------------------------------------ import LibGrp_2 -------------------------------------- spanBF graph root = spBF graph [root] (snd (head (assoc root graph (==)))) [] (fst (head (assoc root graph (==)))) ---------------------------------------------------------------- -- queue - очередь списков вершин для просмотра; -- car - список вершин для просмотра; -- father - предок просматриваемых вершин ----------------------------------------- spBF graph visited car queue father | null car && null queue = [] | null car = spBF graph visited (snd (head queue)) (tail queue) (fst (head queue)) | elem (head car) visited = spBF graph visited (tail car) queue father | True = (father,(head car)): (spBF graph ((head car):visited) (tail car) (queue ++ (assoc (head car) graph) (==)) father) ------------------------------------- -- Неудачные тестовые примеры: ------------------------------ -- "Тестирование дерева..." ---------------------------------------------------- test = spanBF [(1,[2,3]),(2,[4,5]),(3,[6,7])] 1 == [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)] ---------------------------------------------------------------- -- "Тестирование циклического графа..." ------------------------------------------------------- && spanBF [(1,[2,3]),(2,[4,5]),(3,[6,7]),(4,[5]),(6,[7])] 1 == [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)] && spanBF [(1,[2,3]),(2,[3,4,5]),(3,[6,7]), (4,[5]),(6,[7])] 1 == [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)] && spanBF [(1,[2,3]),(2,[3,4,5]),(3,[6,7]), (4,[5]),(6,[7]),(5,[6])] 1 == [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)] && spanBF [(1,[2,3]),(2,[3,4,5]),(3,[6,7]), (4,[5]),(6,[7]),(5,[6])] 2 == [(2,3),(2,4),(2,5),(3,6),(3,7)] ------------------------------------------------------ && spanBF [(1,[2,4]),(2,[1,3]),(4,[1,3]),(3,[1,4])] 1 == [(1,2),(1,4),(2,3)] && spanBF [(1,[2,4]),(2,[1,3]),(4,[1,3]),(3,[1,4])] 2 == [(2,1),(2,3),(1,4)] && spanBF [(1,[2,4]),(2,[1,3]),(4,[1,3]),(3,[1,4])] 3 == [(3,1),(3,4),(1,2)] && spanBF [(1,[2,4]),(2,[1,3]),(4,[1,3]),(3,[1,4])] 4 == [(4,1),(4,3),(1,2)] && spanBF [(1,[2,3]),(2,[4,5]),(3,[6,7])] 1 == [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)]
Библиотека для работы с графами, представленными ассоциативными списками смежности.
Раскрыть/скрыть текст библиотеки.
-- Библиотека для работы с графами, представленными ассо- -- циативными списками смежности. -- Ассоциативные списки смежности моделируются ассоциати- -- вным списком точечных пар следующего вида: -- -- [(A ,[x ,x ,...,x ]),...,(A ,[y ,y ,...,y ])], -- 1 1 2 k n 1 2 j -- -- каждая из которых описывает дугу, соединяющую вершины -- -- A и x , A и x ,..., A и x ,..., -- 1 1 1 2 1 k -- -- A и y , A и y ,..., A и y . -- n 1 n 2 n j -- -- Автор программы (на языке LISP): М.В.Швецкий -- Переписано на язык Haskell: И.А.Кудрявцева (28.01.2010) ---------------------------------------------------------- module LibGrp_2 (pairLis,reKey,reData,assoc1,rAssoc,putAssoc1,addArc, deleteNode,deleteArc,walk,neighb2,oneRange,listSet,assoc) where import List ----------------------------------------------------------- -- Построение графа из списка вершин KEY и списка списков -- смежных вершин DATA с помощью добавления к существующему -- графу Graph -------------------------------------------------------------- pairLis:: [Integer] -> [[Integer]] -> [(Integer,[Integer])] -> [(Integer,[Integer])] pairLis key dta graph | null key = graph | null dta = graph | elem (head key) (reKey graph) = pairLis (tail key) (tail dta) (putAssoc1 (head key) (listSet (head dta ++ (assoc1 (head key) graph))) graph) | True = (head key,head dta) : pairLis (tail key) (tail dta) graph ----------------------------------------------------- -- Восстановление списка вершин графа Graph из -- ассоциативного списка инцидентности ------------------------------------------ reKey:: [(Integer,[Integer])] -> [Integer] reKey graph | null graph = [] | True = fst (head graph) : reKey (tail graph) ---------------------------------------------------------------- -- Восстановление списка списков смежных вершин графа -- Graph из ассоциативного списка инцидентности -------------------------------------------------- reData:: [(Integer,[Integer])] -> [[Integer]] reData graph | null graph = [] | True = snd (head graph) : reData (tail graph) ----------------------------------------------------------- -- Функция возвращает список вершин графа Graph, содержащий -- вершины, смежные вершине Node ------------------------------------------------------ assoc1:: Integer -> [(Integer,[Integer])] -> [Integer] assoc1 node graph | null graph = [] | fst (head graph)==node = snd (head graph) | True = assoc1 node (tail graph) ------------------------------------------------------------ -- Функция возвращает список из вершины графа Graph, имеющей -- заданный список смежных вершин LST -------------------------------------------------------- rAssoc:: [Integer] -> [(Integer,[Integer])] -> [Integer] rAssoc lst graph | null graph = [] | sort (snd (head graph))==sort lst = [fst (head graph)] | True = rAssoc lst (tail graph) --------------------------------------------------------- -- Изменение в графе Graph списка вершин, смежных вершине -- Key, на список Data ------------------------------------------------------------ putAssoc1:: Integer -> [Integer] -> [(Integer,[Integer])] -> [(Integer,[Integer])] putAssoc1 key dta graph | null graph = [] | fst (head graph)/=key = head graph : putAssoc1 key dta (tail graph) | True = (fst (head graph),dta) : putAssoc1 key dta (tail graph) ------------------------------------------------------------- -- Добавление в граф Graph дуги (x,y) ------------------------------------------------------- addArc:: Integer -> Integer -> [(Integer,[Integer])] -> [(Integer,[Integer])] addArc x y graph | null graph = [(x,[y])] | fst (head graph)==x && not (elem y (snd (head graph))) = putAssoc1 x (y : snd (head graph)) graph | fst (head graph)==x && elem y (snd (head graph)) = graph | True = head graph : addArc x y (tail graph) ---------------------------------------------------------------- -- Удаление вершины X из графа Graph ------------------------------------------------ deleteNode:: Integer -> [(Integer,[Integer])] -> [(Integer,[Integer])] deleteNode x graph | (null graph) = [] | fst (head graph)==x = deleteNode x (tail graph) | elem x (snd (head graph)) = (fst (head graph), filter (x/=) (snd (head graph))) : deleteNode x (tail graph) | True = head graph : deleteNode x (tail graph) ------------------------------------------------------------ -- Удаление дуги (X,Y) из графа Graph ---------------------------------------------------------- deleteArc:: Integer -> Integer -> [(Integer,[Integer])] -> [(Integer,[Integer])] deleteArc x y graph | null graph = [] | fst (head graph)==x && elem y (snd (head graph)) = (x,filter (y/=) (snd (head graph))) : deleteArc x y (tail graph) | True = head graph : deleteArc x y (tail graph) -------------------------------------------------------------- -- Построение списка, содержащего все вершины графа, заданного -- ассоциативным списком инцидентности Graph -------------------------------------------- walk:: [(Integer,[Integer])] -> [Integer] walk graph | null graph = [] | True = sort (listSet (oneRange graph)) --------------------------------------------------------- -- Функция возвращает всех "соседей" данной вершины X -- в графе Graph, представленном в виде ассоциативного -- списка инцидентности ------------------------------------------------------- neighb2:: Integer -> [(Integer,[Integer])] -> [Integer] neighb2 x graph | null (assoc x graph (==)) = [] | True = snd (head (assoc x graph (==))) -------------------------------------------------------- -- Вспомогательные функции библиотеки: -------------------------------------- -- Преобразование списочной структуры -- -- ((A .(x x ... x ))...(A .(y y ... y ))), -- 1 1 2 k n 1 2 j -- -- в одноуровневый список --------------------------------------------- oneRange:: [(Integer,[Integer])] -> [Integer] oneRange lst | null lst = [] | True = (fst (head lst) : snd (head lst)) ++ oneRange (tail lst) ------------------------------------------------------- -- Преобразование одноуровневого списка LST в множество -- (удаление из списка повторяющихся элементов) ----------------------------------------------- listSet:: [Integer] -> [Integer] listSet lst | null lst = [] | elem (head lst) (tail lst) = listSet (tail lst) | True = head lst : listSet (tail lst) ------------------------------------------------------------- -- Функция, выполняющая линейный поиск в ассоциативном списке -- alist пары, для которой при сравнении её fst-элемента с -- ключом key по тесту test признак не равен False. -- Если пара элементов, удовлетворяющая тесту, найдена, то -- возвращается список из этой пары; иначе - пустой список ---------------------------------------------------------- assoc:: Integer -> [(Integer,[Integer])] -> (Integer -> Integer -> Bool) -> [(Integer,[Integer])] assoc key alist test | null alist = [] | test (fst (head alist)) key = [head alist] | True = assoc key (tail alist) test
Обратите внимание, что при работе функции spbf параметр car всегда есть список соседей вершины, определяемой параметром father, что позволяет знать предшественника текущей вершины.
На следующем шаге мы рассмотрим приведем перечень задач для самостоятельного решения.
