У мене є спрямований граф G, поданий як список списків суміжності:
newtype Graph Int = Graph [(Int, [Int])]
G має n вершин і m ребер. Я намагаюся реалізувати алгоритм BFS в Haskell, який працює в O (m) часу (можливо, амортизований), але найкращим рішенням я зміг придумати прогони в O (m * log n) і використовувати структуру даних з Data.Map модуль
Моя ідея лінійного рішення полягає в наступному: використовуйте структуру з Data.Sequence як ефективна FIFO чергу і робити все, як імператив BFS буде робити, але я застряг в точці, де я повинен відзначити вузлів, як відвідав.
Моє питання: чи можливо реалізувати BFS в Haskell (або будь-який інший чисто функціональний мова), який працює в O (m)? І якщо це не так, то який аргумент можна використовувати для доведення такої заяви?
Відповіді:
5 за відповідь № 1Я вважаю, що ваша проблема полягає в тому, що ви не можете реалізувати хорошу чергу.
Подивись на Data.Sequence - для черги з подвійним завершенням слід робити добре, тому що операції до кінця послідовності неймовірно швидкі. Додавання елемента до обох кінців є O(1) і видалення елемента з обох кінців O(1).
Як тільки ви маєте чергу, вона повинна виконувати так само добре, як і DFS.
Замість того, щоб використовувати Map Int [Int] Ви, ймовірно, можете піти з a Vector Int [Int] (якщо вершини є цілими числами з 1 до n)
Щоб позначити вузли як перевірені, ви можете використовувати IntSet.
Це має допомогти вам O(V + E).
bfs :: V.Vector [Int] -> Int -> [Int]
bfs graph start = go IS.empty graph $ S.singleton start
go :: IS.IntSet Int -> V.Vector [Int] -> S.Sequence Int -> [Int]
go seen graph queue =
case S.viewL queue of
S.EmptyL -> []
vertex S.:< rest = vertex:(go seen" graph queue")
where neighbors = filter (not . IS.member seen) (graph V.! vertex)
seen" = S.insert vertex seen
queue" = queue S.>< S.fromList neighbors
Зверніть увагу, що спосіб, у який ми будуємо цей список, абсолютно ледачий! Отже, якщо вам потрібно лише, наприклад, першу половину BFS, інше не обчислює.