-- Функция построения остовного дерева;
-- 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)]