Notizen

Breitensuche

tagsgraphentheorie

Sei ein Graph und . Die Breitensuche beginnt am Knoten . Folgender Status wird für jeden Knoten hinterlegt:

  • Weiß - Knoten wurde noch nicht erfasst
  • Grau - Knoten wurde gesehen, aber noch nicht verarbeitet
  • Schwarz - Knoten ist verarbeitet

Implementierung

Pseudocode

  • Algorithmus Breitensuche(, ):

    Initialisierung

    • Für jeden Knoten
      • .farbe = weiß
      • .dist =
      • .pred = NULL
    • .color = grau
    • .dist =
    • .pred = NULL

    Durchlaufen

    • Schlange
    • .enque()
    • Solange
      • = .dequeue()
      • Für jeden Knoten AdjList[]
        • Falls .color == weiß
          • .color = grau
          • .dist = .dist + 1
          • .pred =
          • .enqueue()
      • .color = schwarz

JavaScript

function bfs(graph, startNode) {
    let visited = new Set(); // Set um besuchte Knoten zu speichern
    let queue = [startNode]; // Queue für BFS
 
    // Solange die Queue nicht leer ist
    while (queue.length > 0) {
        let node = queue.shift(); // Entfernt das erste Element aus der Queue
 
        if (!visited.has(node)) {
            visited.add(node); // Markiere den Knoten als besucht
            console.log(node); // Bearbeitet den Knoten (hier einfach Ausgabe)
 
            // Füge alle Nachbarn des Knotens, die 
            // noch nicht besucht wurden, zur Queue hinzu
            graph[node].forEach(neighbor => {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            });
        }
    }
}

Beobachtungen

  • Die Werte in den Knoten entsprechen der Länge eines kürzesten Pfades vom Anfangsknoten zum jeweiligen Knoten
  • Die angegangenen Kanten lassen sich zum Breitensuchbaum verbinden

Laufzeit

  • Aufwand für die Initialisierung:
  • Ein Knoten wird maximal einmal in die Schlange eingefügt und maximal einmal wieder entnommen:
  • Aufwand für alle Knoten:
  • Jede Adjazenzliste eines Knoten wird maximal ein mal durchlaufen, insgesamt gibt es Einträge in allen Listen
  • Insgesamt ergibt sich damit die Laufzeit:

Backlinks