ustify"> throws AlgorithmException
{
Collection lt; Path gt; result= new ArrayList lt; gt; ();
WorldVertex tail=path. tail ();
Collection lt; WorldEdge gt; edges=getWorld (). getOutEdges (tail);
for (WorldEdge edge: edges)
{
Pair lt; WorldVertex gt; endpoints=getWorld (). getEndpoints (edge); nextVertex=endpoints. getFirst () == tail?
endpoints. getSecond (): endpoints. getFirst ();
if (nextVertex. getMark () == WorldElement. MarkType. Visited)
continue ;
result. add (path. addElementToCopy (edge, nextVertex));
}
return result;
}
@ Override
protected void safeAbort ()
{
}
}
Haskell
Пошук в ширину. Рішення не претендує на лаконічність, але працює.
Спочатку виробимо раціональну схему подання графа. Будемо зберігати граф як список списків цілих (кортежі і рядки ні до чого!). Кожна вершина графа буде списком вершин, з якими дана вершина пов'язана. Так наприклад, у графі [[1,2,5],.]
нульова вершина пов'язана з першою, другою і п'ятою. Вершини зручно нумерувати з нуля. Нехай число вершин графа=n
Нам знадобиться три службових списку:
que - для черги (спочатку порожній);
pth - для відновлення шляху (список довжини n з нулів. У позиції стартовою вершини - 1);
chk - для відмітки відвідувань вершини (список довжини n з нулів).
Алгоритм складається з наступних кроків:
) покласти стартову вершину в чергу que
) якщо черга que порожня - кінець
) взяти перший елемент черги que (k); помістити в que все ще не відвідані вершини, пов'язані з k і позначити їх як відвідані; занести k в список pth в позиції з номерами вершин, пов'язаних з k-й;
) перейти на п.1
Після роботи алгоритму в списку pth знаходиться інформація про шляхи. Якщо потрібно знайти шлях з стартовою вершини (з якою пропрацював алгоритм, описаний вище), в яку або вершину j, то чинимо так:
) вважаємо i=j
) беремо i-й елемент списку pth. Приєднуємо i до результату Якщо i-й елемент == - 1 - кінець
) вважаємо i=i-му елементу pth
) перейти до Програмний 1
Після роботи цього алгоритму результат буде дорівнює шляху з стартовою вершини в задану.
Тепер реалізуємо це на HASKELL:
занесення до списку chk в позицію n значення m
mark :: [Int] - gt; Int - gt; Int - gt; [Int] chk n m | (n == 0)=m: (tail chk)
| otherwise=(head chk): (mark (tail chk) (n - 1) m)
додати у хвіст черги que всі вершини графа g,
пов'язані з вершиною n і ще не відвідані
newV :: [[Int]] - gt; Int - gt; [Int] - gt; [Int] - gt; [Int] gn chk que=(filter ( x - gt; (chk !! x) == 0) (g !! n))
Занести в список pth значення n в позиції,
номери яких перераховані в списку f
setP :: [Int] - gt; Int - gt; [Int] - gt; [Int] pth n []=pthpth n (f: fs)=setP (mark pth fn) n fs
Обхід в ширину графа g з вершини, попередньо
вміщеній в чергу que :: [[Int]] - gt; [Int] - gt; [Int] - gt; [Int] - gt; [Int] g [] chk pth=pth g que chk pth=(bfs g (tq ++ nV) (setP chk 1 nV) (setP pth hq nV)) tq=(tail que); hq=(head que); nV=(newV g hq chk tq);
Відновлення шляху з стартовою вершини в задану
showPath :: [Int] - gt; Int - gt; [Int] pth n | (pth !! n) == negate 1=[n]
| otherwise=n: (showPath pth (pth !! n))
Парадна функція. Бере граф g і дві вершини n і m
повертає шлях з n в m
bfs :: [[Int]] - gt; Int - gt; Int - gt; [Int] gnm=reverse $ showPath (bfs 'g [n] (mark chk n 1) pth) mchk=(take k (repeat 0)); pth=(mark chk n (negate 1)); k=length g
обов'язкову перевірку: gt; bfs [[1,2], [0,2,3,4], [0,1,5,6], [1], [1], [2], [2...
