Mam skierowany graf G podany jako lista list sąsiadów:
newtype Graph Int = Graph [(Int, [Int])]
G ma n wierzchołków i m krawędzi. Próbuję zaimplementować algorytm BFS w Haskell, który działa w czasie O (m) (może amortyzowany), ale najlepsze rozwiązanie mogłem uruchomić w O (m * log n) i użyć struktury danych Data.Map moduł.
Mój pomysł rozwiązania liniowego jest następujący: Użyj struktury z Data.Sequence tak wydajna kolejka FIFO i rób wszystko, co zrobiłby imperatyw BFS, ale utknąłem w punkcie, w którym muszę oznaczyć węzły jako odwiedzone.
Moje pytanie brzmi: czy możliwe jest zaimplementowanie BFS w Haskell (lub innym czysto funkcjonalnym języku), który działa w O (m)? A jeśli nie, to jakiego argumentu możesz użyć, aby udowodnić takie stwierdzenie?
Odpowiedzi:
5 dla odpowiedzi № 1Zakładam, że twój problem polega na tym, że nie możesz wdrożyć dobrej kolejki.
Spojrzeć na Data.Sequence - powinno być dobrze dla kolejki z podwójnym zakończeniem, ponieważ operacje pod koniec sekwencji są niezwykle szybkie. Dodawanie elementu do dowolnego końca jest O(1) i usunięcie elementu z dowolnego końca jest O(1).
Gdy masz kolejkę, powinna działać równie dobrze jak DFS.
Zamiast używać a Map Int [Int] prawdopodobnie możesz uciec Vector Int [Int] (jeśli twoje wierzchołki są liczbami całkowitymi z 1 do n)
Aby zaznaczyć węzły jako zaznaczone, możesz użyć IntSet.
To powinno cię dostać 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
Zauważ, że sposób, w jaki budujemy tę listę, jest całkowicie leniwy! Jeśli więc potrzebowałbyś tylko na przykład pierwszej połowy BFS, nie obliczyłby reszty.