Breitensuche, Tiefensuche – und was das mit dem Dijkstra-Algorithmus zu tun hat

1️⃣ Die Tiefensuche (DFS)

Die Tiefensuche durchläuft einen Graphen, indem sie möglichst tief in eine Richtung geht, bevor sie zurückkehrt und andere Wege erkundet.

Beispielverhalten:

• Starte bei einem Knoten.
• Besuche einen seiner Nachbarn.
• Gehe weiter in die Tiefe, bis es nicht mehr weitergeht.
• Dann zurück und andere Pfade ausprobieren.
• fertig: wenn alle Pfade durchlaufen sind

Beispiel:

🔄 Ablauf:

Starte bei 1 ->4 -> 5 -> 6 -> 3 -> hier gibt es keinen Pfad zu 2, deswegen gehen wir rekursiv zur 1 zurück und dann zur 2

🧠 Laufzeit:

O(|V| + |E|) bei Verwendung von Adjazenzlisten

|V|=Anzahl der Knoten

|E|=Anzahl der Kanten

🧰 Datenstruktur:

Stack (LIFO) – LIFO (Last In, First Out): Beim LIFO-Prinzip wird das zuletzt eingefügte Element als erstes wieder entfernt – wie bei einem Stapel Bücher.

Beispiel:
Du stapelst Bücher aufeinander. Wenn du eins brauchst, nimmst du das oberste Buch, also das zuletzt abgelegte.

Du legst ab: A → B → C
Du nimmst heraus: C → B → A

def dfs(graph, start):
    visited = set() # Set zum Speichern der besuchten Knoten
    stack = [start] # Stack zum Nachverfolgen der Knoten, die noch zu besuchen sind (LIFO-Prinzip)
    # Solange der Stack nicht leer ist, durchlaufe den Graphen
    while stack:
        node = stack.pop()  # LIFO Letzter hinzugefügter Knoten wird zuerst verarbeitet - # Nimm den zuletzt hinzugefügten Knoten vom Stack (Tiefensuche)
        if node not in visited: # Wenn der Knoten noch nicht besucht wurde
            print(node)
            visited.add(node)   # Markiere den Knoten als besucht
           
            # Füge die Nachbarn des Knotens dem Stack hinzu – in umgekehrter Reihenfolge
            # So wird der erste Nachbar in der ursprünglichen Liste zuletzt besucht
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

🏁 Ergebnisbeispiel:

A → B → D → E → F → C

2️⃣ Die Breitensuche (BFS)

Die Breitensuche durchläuft einen Graphen Schicht für Schicht. Sie erkundet zunächst alle Nachbarn eines Knotens, bevor sie tiefer geht.

Beispielverhalten:

• Starte bei einem Knoten.
• Besuche alle direkten Nachbarn.
• Dann die Nachbarn der Nachbarn – usw.

🔄 Ablauf:

1 -> 4 , 2 -> 5 , 3 ->6

🧠 Laufzeit:

O(|V| + |E|) bei Adjazenzlisten

🧰 Datenstruktur:

Stack (LIFO) – Beim FIFO-Prinzip wird das zuerst eingefügte Element auch als erstes wieder entfernt – wie bei einer Warteschlange im Supermarkt.

Beispiel:
Du stehst in der Schlange an der Supermarktkasse. Die Person, die zuerst kam, wird auch zuerst bedient.

Du kommst an: A → B → C
Du wirst bedient: A → B → C

from collections import deque #deque ist eine effiziente doppelt verkettete Liste – ideal für FIFO-Warteschlangen

def bfs(graph, start):
    visited = set()  # Menge zur Speicherung der bereits besuchten Knoten
    queue = deque([start]) # Warteschlange für die Knoten, die besucht werden sollen (FIFO-Prinzip)

    while queue: # Solange es noch Knoten in der Warteschlange gibt
        node = queue.popleft()  # Nimm den ersten Knoten aus der Warteschlange (First In, First Out)
        if node not in visited: # Wenn der Knoten noch nicht besucht wurde
            print(node)
            visited.add(node) # Markiere den Knoten als besucht
            # Alle direkten Nachbarn, die noch nicht besucht wurden, in die Warteschlange einfügen
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')

🏁 Ergebnisbeispiel:

A → B → C → D → E → F

🧠 Zusammenfassung DFS und BFS:

🚦 Und was ist mit Dijkstra?

Der Dijkstra-Algorithmus ist eine Art „intelligente“ Breitensuche für gewichtete Graphen, bei der es darum geht, den kürzesten Pfad von einem Startknoten zu allen anderen zu finden.

🔧 Prinzip:

• Beginne beim Startknoten mit Distanz 0.
• Wähle den Knoten mit der aktuell kleinsten Distanz aus.
• Aktualisiere die Distanzen aller Nachbarn, falls der neue Weg kürzer ist.
• Wiederhole, bis alle Knoten verarbeitet wurden.

🎯 Ziel:

Dijkstra berechnet nicht nur den kürzesten Weg zu einem einzelnen Zielknoten, sondern er bestimmt standardmäßig die minimalen Distanzen zu allen erreichbaren Knoten.

🛠️ Beispiel:

Kürzesten Weg von Augsburg nach Hanau

Anfangsbedingungen: Startknoten: Augsburg (A) Distanz von A zu A = 0 Distanz zu allen anderen Knoten = ∞ Vorgänger: Keiner initial.

Knoten-Mapping für die Tabelle: A = Augsburg UL = Ulm M = München AA = Aalen S = Stuttgart N = Nürnberg MA = Mannheim WU = Würzburg F = Frankfurt am Main HA = Hanau

Tabelle für den Dijkstra-Algorithmus: Augsburg (A) nach Hanau (HA)

Initialisierung (Iteration 0): Startknoten A (Augsburg), Distanz=0, alle anderen ∞. Vorgänger sind noch leer. Warteschlange enthält alle Knoten mit ihren aktuellen Distanzen. Erledigt ist leer. Aktueller Knoten ist leer.

Iteration 1: Kleinste Distanz in Warteschlange ist A (0). Setze A als aktuellen Knoten. Besuche Nachbarn von A: UL (80), M (80).

Iteration 2: Kleinste Distanz in Warteschlange ist UL (80) oder M (80). Nehmen wir UL. Setze UL als aktuellen Knoten. Besuche Nachbarn von UL: A (schon erledigt), S (170), AA (155).

Iteration 3: Kleinste Distanz in Warteschlange ist M (80). Setze M als aktuellen Knoten. Besuche Nachbarn von M: N (195).

Iteration 4: Kleinste Distanz in Warteschlange ist AA (155). Setze AA als aktuellen Knoten. Besuche Nachbarn von AA: UL (schon erledigt), WU (295).

Iteration 5: Kleinste Distanz in Warteschlange ist S (170). Setze S als aktuellen Knoten. Besuche Nachbarn von S: UL (schon erledigt), MA (300).

Iteration 6: Kleinste Distanz in Warteschlange ist N (195). Setze N als aktuellen Knoten. Besuche Nachbarn von N: M (schon erledigt), WU (195 + 120 = 315). Aktueller Wert für WU ist 295, daher keine Aktualisierung.

Iteration 7: Kleinste Distanz in Warteschlange ist WU (295). Setze WU als aktuellen Knoten. Besuche Nachbarn von WU: AA (schon erledigt), N (schon erledigt), HA (295 + 110 = 405).

Iteration 8: Kleinste Distanz in Warteschlange ist MA (300). Setze MA als aktuellen Knoten. Besuche Nachbarn von MA: S (schon erledigt), F (300 + 90 = 390).

Iteration 9: Kleinste Distanz in Warteschlange ist F (390). Setze F als aktuellen Knoten. Besuche Nachbarn von F: MA (schon erledigt), HA (390 + 20 = 410). Aktueller Wert für HA ist 405, daher keine Aktualisierung.

Iteration 10: Kleinste Distanz in Warteschlange ist HA (405). Setze HA als aktuellen Knoten. Ziel erreicht! Der Algorithmus kann hier beendet werden.

Ergebnis:

Der kürzeste Weg von Augsburg (A) nach Hanau (HA) beträgt 405 km.

Pfad-Rekonstruktion (rückwärts von HA): HA <- WU (405 – 110 = 295) WU <- AA (295 – 140 = 155) AA <- UL (155 – 75 = 80) UL <- A (80 – 80 = 0)

Der Pfad ist: Augsburg (A) -> Ulm (UL) -> Aalen (AA) -> Würzburg (WU) -> Hanau (HA)

🧠 Laufzeit:

• O((V + E) · log V) mit Priority Queue (Heap)
• O(V²) mit Array oder unsortierten Liste

import heapq

def dijkstra(graph, start):
    # Schritt 1: Initialisierung aller Distanzen mit unendlich
    distances = {node: float('inf') for node in graph}
    distances[start] = 0 # Startknoten bekommt Distanz 0
    visited = set()  # Menge der besuchten Knoten

    # Priority Queue: (Entfernung, Knoten)
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)
         # Wenn der Knoten schon besucht wurde, überspringen
        if current_node in visited: # Wenn der Knoten schon besucht wurde, überspringen
            continue
        visited.add(current_node)  

        # Schritt 2: Nachbarn überprüfen
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight # Potenzielle neue Distanz
            # Wenn der neue Weg kürzer ist, aktualisieren
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances
    
graph = {
    'A': [('B', 1), ('C', 4), ('D', 7)],
    'B': [('E', 2)],
    'C': [('E', 3)],
    'D': [('F', 1)],
    'E': [('F', 4)],
    'F': []
}

distances = dijkstra(graph, 'A')
print("Kürzeste Distanzen von A:")
for node in sorted(distances):
    print(f"{node}: {distances[node]}")

🏁 Ergebnisbeispiel:

A: 0
B: 1
C: 4
D: 7
E: 3
F: 7

🧠 Fazit

• Wer DFS und BFS verstanden hat, kann Dijkstra viel leichter begreifen.
• Sie sind Teil derselben Familie: Graphen-Durchsuchungsalgorithmen.
• Die Wahl des Algorithmus hängt immer vom Problem ab: Struktur (DFS), kürzester Weg ohne Gewichte (BFS) oder kürzester Weg mit Gewichten (Dijkstra).
• Den kompletten Code kannst du unter https://colab.research.google.com/drive/1HyvsfwMGGY7pcT9RxpjkpMaqFYbgS4NU?usp=sharing ansehen