2016-07-30 11 views
1

Ich verwende BFS, um verbundene Komponenten zu finden. Ich habe beschlossen, es mit einem Set zu implementieren, um besuchte Knoten zu verfolgen. Das Problem bei diesem Ansatz besteht darin, dass ein Scheitelpunkt der Warteschlange zweimal hinzugefügt werden kann. Also habe ich gerade die Warteschlange gewechselt. Ich interessiere mich nicht für Besuchsordnung, alle Knoten werden einmal besucht und der Algorithmus funktioniert gut. Das ist natürlich kein klassisches BFS mehr: der Auftrag ist gebrochen.Breitensuche mit Set statt Warteschlange

Pseudocode:

Set visited; 
Set to_visit; 
visited.insert(start) 
to_visit.insert(start) 
while (to_visit is not empty){ 
    current = to_visit.first 
    to_visit.delete(current) 
    for each neighbour of current { 
     isNew = visited.insert(neighbour) 
     if (isNew) { 
      to_visit.insert(neighbour) 
     } 
    } 
} 

Ich bin mir ziemlich sicher, ich bin nicht der erste, der „erfunden“ es. Ich frage mich: Wie heißt diese I-dont-care-first-Suche?

Antwort

1

Wie konnte es zweimal zur Warteschlange hinzugefügt werden? Sie müssen sicherstellen, dass Elemente in der Warteschlange eindeutig sind, wenn Vertexe Objekte sind add Flag "visited = false", wenn Sie versuchen, Vertex in die Warteschlange einzufügen, markieren Sie zuerst Flag und nur weiter, wenn es falsch ist, dann ändern Sie es in wahr.

Wenn Eckpunkte nur Zahlen sind, erstellen Sie ein boolesches Array, das Flags für jeden Eckpunkt darstellt.

Pseudocode:

queue= [] 
set = [0,0,0,0,0....,0] 
queue.push(firstVertex) 

while(!queue.isEmpty()) 
{ 
    vertex curr = queue.pop() 

    if(set[curr] == 1) //already visited 
    { 
      continue; 
    } 
    set[curr] = 1; 
    foreach(child of curr) 
    { 
      queue.push(child); 
    } 
} 

Sie können auch Flagge von true/false Anzahl der Komponente ändern.

+0

Vielen Dank, ich weiß über ordnungsgemäße Implementierung von BFS. Eigentlich mache ich das selbe, behalte aber die Eindeutigkeit der Queue per Set bei. Und in meiner Implementierung wird ein Scheitelpunkt besucht, wenn _really_ besucht wurde, nicht wenn er zur Warteschlange hinzugefügt wurde. – ov7a

+0

Ja, mit set sollte es auch funktionieren, ändern Sie einfach isVisited zu mySet [Vertex] = 1 oder etwas? Aber die Reihenfolge ist immer noch dieselbe. Ich sehe dein Problem! Sie können am Anfang eine if-Anweisung hinzufügen und prüfen, ob curr bereits besucht wurde oder nicht. Ich ändere meinen Pseudocode zu deiner Idee. –

+0

'if (set [curr] == 1)' manipuliert die Komplexität des Algorithmus. Ein Eckpunkt kann mehr als einmal betrachtet werden. – ov7a

Verwandte Themen