Vermeiden von Duplikaten in der Breitensuche

Question

Für Bildungszwecke habe ich vor kurzem allgemeine Algorithmen in Haskell implementiert. Zur Zeit stecke ich auf Breathth-First Search fest. Dies ist meine Implementierung mit Knoten als nur ganze Zahlen der Einfachheit halber dargestellt wird:

import qualified Data.Map as M 
import qualified Data.List as L 

type Node = Int 
type Graph = M.Map Node [Node] 

-- Returns list of nodes adjacent to n in graph g 
adjacent :: Node -> Graph -> [Node] 
adjacent n g = M.findWithDefault [] n g 

-- Returns graph g with all instances of n removed 
rip :: Node -> Graph -> Graph 
rip n g = M.delete n (M.map (L.delete n) g) 

bfs :: Node -> Graph -> [Node] 
bfs n g = [n] ++ _bfs [n] g 

_bfs :: [Node] -> Graph -> [Node] 
_bfs (n:ns) g = 
    if not (M.null g) then 
     let layer = adjacent n g in 
      layer ++ _bfs (ns ++ layer) (rip n g) 
    else n:ns 
_bfs [] g = [] 

(Es gibt auch andere Funktionen für die grafische Darstellung tatsächlich konstruieren, aber ich ließ sie der Kürze halber out)

Das Ergebnis des Aufrufs bfs wäre ein richtiger Breiten ersten Durchlauf des Graphen, wenn nicht für die Tatsache, dass einige Diagramme produzieren Duplikate, wie diese:

(das Ergebnis von bfs 1 g für g = Dieser Graph ist [1,2,3,4,4,5,6,7,7,7])

Meine aktuelle Lösung kocht in _bfs-L.nub $ layer ++ _bfs (ns ++ layer) (rip n g) die entsprechende Zeile an veränderte nach unten, aber das scheint unglaublich hackish, und ich bin nicht sicher, ob es eine richtige Breite beginn produzieren werde Durchquerung. Abgesehen davon, n:ns für Duplikate vor dem Einfügen ständig zu überprüfen (was schrecklich ineffizient klingt), habe ich keine anderen Ideen.

Wie kann ich _bfs (oder mehr) umschreiben, so dass es per Definition keine Duplikate erzeugt?

Answer 1

Sie sollten eine Reihe von besuchten Knoten anstelle von verwenden.

Zuerst nimmt lineare Zeit in der Anzahl der verbleibenden Kanten, die die gesamte Breite zuerst Traversal quadratisch macht.

Zweitens, die No-Duplikate Traversal ist nicht praktikabel mit . Momentan werden doppelte Knoten hinzugefügt, da dieselben Knoten von mehreren Knoten der aktuellen Traversierungsgrenze aus besucht werden können. Die Wiederholungen können nicht einfach mit gelöscht werden, da sie den Knoten vollständig aus dem Graphen entfernt, aber wir brauchen immer noch den Knoten, um die Traversierung fortzusetzen.

Hier ist ein Beispiel mit einem in einem State Monade gesetzt besucht (was hier schön ist, da wir die Traversal Grenze von Grenze aufbauen können, und filterM von Control.Monad ist praktisch für, na ja, besuchten Knoten Ausfiltern):

import qualified Data.IntMap.Strict as IM 
import qualified Data.IntSet as IS 

import Control.Monad 
import Control.Monad.State.Strict 

type Node = Int 
type Graph = IM.IntMap [Node] 

bfs :: Node -> Graph -> [Node] 
bfs n g = evalState (go [n]) (IS.singleton n) where 

    go :: [Node] -> State IS.IntSet [Node] 
    go [] = return [] 
    go ns = do 
     ns' <- flip filterM ((g IM.!) =<< ns) $ \n' -> do 
      notVisited <- gets (IS.notMember n') 
      when notVisited $ modify (IS.insert n') 
      return notVisited 
     (ns++) `fmap` go ns' 

-- your example graph 
graph :: Graph 
graph = IM.fromList $ [ 
     (1, [2, 3]) 
    , (2, [1, 4]) 
    , (3, [1, 4]) 
    , (4, [2, 5, 3, 6]) 
    , (5, [4, 7]) 
    , (6, [4, 7]) 
    , (7, [5, 6])] 

main = print $ bfs 1 graph -- [1, 2, 3, 4, 5, 6, 7] 

Hier ist eine Implementierung des gleichen Algorithmus ohne State statt foldr mit entlang der aktualisierten besuchten Satz weitergeben müssen:

bfs' :: Node -> Graph -> [Node] 
bfs' start graph = go [start] (IS.singleton start) where 

    go :: [Node] -> IS.IntSet -> [Node] 
    go [] _  = [] 
    go ns visited = ns ++ go ns' visited' where 

     newNodes = [n' | n <- ns, n' <- graph IM.! n] 

     step n (acc, visited) 
      | IS.member n visited = (acc, visited) 
      | otherwise = (n:acc, IS.insert n visited) 

     (ns', visited') = foldr step ([], visited) newNodes 

Answer 2

Sie müssen sich erinnern, welche Knoten Sie bisher durchlaufen haben und diese Informationen weitergeben. Und verwenden Sie eine Datenstruktur mit einem effizienten Testbetrieb für Mitglieder. Ein guter Kandidat wäre Set, oder wenn Sie nur Int für Knoten verwenden, dann IntSet.