На этом шаге мы рассмотрим реализацию этого алгоритма.
С помощью поиска на графе можно ответить на некоторые вопросы относительно структуры графа.
Рассмотрим две задачи, связанные с поиском:
- (1) вычисление компонентов связности графа;
- (2) построение остовного дерева связного графа.
- Определение.
- Связным компонентом графа называется максимальный связный подграф.
Для вычисления компонентов связности графа воспользуемся уже построенной функцией depthFirst.
Рассмотрим ещё раз работу функции defi. Заметим, что когда к списку просмотренных вершин visited добавляется новая вершина, список path представляет собой путь из этой вершины в начальную. Поэтому по окончанию работы в списке visited содержатся только те вершины, которые можно соединить с начальной.
Можно показать (см. [1]), что в этом списке содержатся все вершины, обладающие этим свойством.
Таким образом, функция depthFirst вычисляет список вершин связной компоненты вершины root, и теперь мы готовы решить задачу о построении всех компонентов связности данного графа.
Приведем пример построения компонентов связности графа.
Раскрыть/скрыть текст примера.
-- Функция возвращает список списков вершин компонентов -- связности графа graph -- graph - граф в виде ассоциативных списков инцидентности ---------------------------------------------------------- import LibGrp_2 ----------------------------------- connLists graph = connLsts graph [] ------------------------------------------- connLsts graph lists | null graph = lists | not (lMember (fst (head graph)) lists) = connLsts (tail graph) ((depthFirst graph (fst (head graph))): lists) | True = connLsts (tail graph) lists ------------------------------------------------------- -- Функция проверяет, содержится ли вершина vertex в -- каком-либо из списков, составляющих lists -------------------------------------------- lMember vertex lists | null lists = False | elem vertex (head lists) = True | True = lMember vertex (tail lists) ------------------------------------------------------ -- Функция возвращает список вершин графа в порядке их -- прохождения в глубину; -- graph - граф в виде ассоциативного списка инцидентности, -- root - вершина графа, с которой начинается обход --------------------------------------------------- depthFirst graph root | null graph = [] | True = defi graph [root] [root] ------------------------------------------------------ -- visited - список уже просмотренных вершин; -- path - список вершин, определяющих путь просмотра ---------------------------------------------------- defi graph visited path | null path = reverse visited | null (expnd graph visited (head path)) = defi graph visited (tail path) | True = defi graph (expnd graph visited (head path) ++ visited) (expnd graph visited (head path) ++ path) ------------------------------------------------------------- -- Выбор следующей, еще не просмотренной вершины, -- соседней с вершиной vertex ----------------------------- expnd graph visited vertex | null (neighb2 vertex graph) = [] | True = firstNotVisited visited (neighb2 vertex graph) -------------------------------------------------------------- firstNotVisited visited vlist | null vlist = [] | not (elem (head vlist) visited) = [(head vlist)] | True = firstNotVisited visited (tail vlist) -- *********************************************************** -- Функция, выделяющая компоненты связности, представленные -- в виде структур смежности ---------------------------- f2 graph lst | null lst = [] | True = (f1 graph (head lst)): (f2 graph (tail lst)) ---------------------------------------------------------------- f1 graph lst | null graph = [] | elem (fst (head graph)) lst = (head graph):(f1 (tail graph) lst) | True = f1 (tail graph) lst ----------------------------------------------- -- Неудачные тестовые примеры: --------------------------------------------- test = connLists [(1,[2,3]),(2,[3]),(5,[])] == [[5],[1,2,3]] && connLists [(1,[2,3]),(2,[3]),(5,[]),(6,[])] == [[6],[5],[1,2,3]] && connLists [(1,[2,3]),(2,[3]),(5,[6])] == [[5,6],[1,2,3]] && connLists [(1,[2,3,5]),(2,[3]),(5,[6])] == [[1,2,3,5,6]] ------------------------------------------------------ && f2 [(1,[2,3]),(4,[5,6]),(5,[4]),(3,[2,1])] [[1,2,3],[4,5,6]] == [[(1,[2,3]),(3,[2,1])],[(4,[5,6]),(5,[4])]]
Библиотека для работы с графами, представленными ассоциативными списками смежности.
Раскрыть/скрыть текст библиотеки.
-- Библиотека для работы с графами, представленными ассо- -- циативными списками смежности. -- Ассоциативные списки смежности моделируются ассоциати- -- вным списком точечных пар следующего вида: -- -- [(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
(1)Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.
На следующем шаге мы рассмотрим построение остовного дерева связного графа с помощью поиска в глубину.
