Mit Google fortfahren
Graphenalgorithmus: Graphen modellieren und lösen
Ein Graphenalgorithmus untersucht ein Netz aus Knoten und Kanten. Welches Verfahren passt, hängt von deiner Frage ab: Möchtest du erreichbare Knoten finden, einen kürzesten Weg berechnen oder alle Knoten günstig verbinden?
Auf dieser Seite modellierst du ein kleines Netz, stellst es als Adjazenzliste und Adjazenzmatrix dar und führst ausgewählte Algorithmen schrittweise aus.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Vom Sachproblem zum Graphen
Ein Stadtplan, ein Computernetz oder eine Gruppe miteinander verbundener Personen kann als Graph dargestellt werden.
Graph
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten. Knoten stehen für Objekte. Kanten beschreiben Beziehungen oder Verbindungen zwischen ihnen.
Bei einem Straßennetz können Kreuzungen die Knoten und Straßen die Kanten sein. Ein Kantengewicht kann zusätzlich eine Entfernung, Fahrzeit oder andere Kosten angeben.
Du musst entscheiden, ob die Kanten eine Richtung haben:
- Eine Straße, die in beide Richtungen befahrbar ist, kann in einem ungerichteten Straßennetz durch eine ungerichtete Kante modelliert werden.
- Eine Einbahnstraße wird in einem gerichteten Straßennetz durch eine gerichtete Kante modelliert.
In einem gerichteten Verkehrsgraphen fährt ein Zug zwischen A und B in beide Richtungen. Dafür brauchst du die Kanten A nach B und B nach A. Von B nach C fährt dagegen nur ein Shuttle ohne Rückfahrt. Deshalb gibt es dort nur die Kante B nach C.
So bleibt die Bedeutung aller Kanten einheitlich: Jede gerichtete Kante gibt genau eine erlaubte Fahrtrichtung an.
Den Graphen für Algorithmen darstellen
Ein Algorithmus benötigt eine systematische Darstellung der Nachbarschaften.
Adjazenzliste
Eine Adjazenzliste nennt für jeden Knoten seine Nachbarn. Bei einem gerichteten Graphen werden üblicherweise die direkt erreichbaren Nachfolger eingetragen.
Für den ungerichteten Graphen mit den Kanten A–B, A–C, B–D, C–D und D–E lautet die Adjazenzliste:
- A: B, C
- B: A, D
- C: A, D
- D: B, C, E
- E: D
Weil der Graph ungerichtet ist, erscheint jede Verbindung bei beiden Endknoten.
Eine Adjazenzmatrix besitzt für jedes mögliche Knotenpaar ein Feld. Bei einem ungerichteten, ungewichteten Graphen steht dort 1, wenn eine Kante vorhanden ist, sonst 0.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 0 |
| C | 1 | 0 | 0 | 1 | 0 |
| D | 0 | 1 | 1 | 0 | 1 |
| E | 0 | 0 | 0 | 1 | 0 |
Die Matrix ist symmetrisch: Steht bei D und E eine 1, steht auch bei E und D eine 1. Das liegt daran, dass die Kanten ungerichtet sind.
Eine Adjazenzmatrix benötigt Speicher für alle Knotenpaare. Eine Adjazenzliste benötigt dagegen im Wesentlichen Platz für die Knoten und vorhandenen Kanten.
Eine Adjazenzmatrix eignet sich für eine direkte Prüfung einzelner Kanten. Eine Adjazenzliste macht die vorhandenen Nachbarn eines Knotens schnell zugänglich und ist für dünne Graphen meist platzsparender.
Mit BFS und DFS den Graphen durchsuchen
Eine Traversierung besucht die erreichbaren Knoten nach einer festgelegten Strategie. Wegen möglicher Zyklen wird jeder bereits entdeckte Knoten markiert.
Breitensuche
Die Breitensuche, kurz BFS, untersucht zuerst alle direkten Nachbarn und danach die weiter entfernten Knoten. Sie verwendet eine Schlange: zuerst eingefügt, zuerst entnommen.
Für eindeutige Ergebnisse betrachten wir Nachbarn alphabetisch. BFS startet bei A im Beispielgraphen:
- Markiere A und lege A in die Schlange.
- Entnimm A; entdecke B und C.
- Entnimm B; entdecke D.
- Entnimm C; D ist bereits entdeckt.
- Entnimm D; entdecke E.
- Entnimm E; die Suche ist beendet.
Die Besuchsreihenfolge lautet A, B, C, D, E. Die Entfernungen in Kanten von A betragen für A bis E der Reihe nach 0, 1, 1, 2, 3.
In einem ungewichteten Graphen liefert BFS die kleinste Anzahl von Kanten vom Start zu jedem erreichbaren Knoten.
Tiefensuche
Die Tiefensuche, kurz DFS, verfolgt einen Weg möglichst weit und kehrt erst dann zum letzten Knoten mit einem unbesuchten Nachbarn zurück. Sie kann rekursiv oder mit einem Stapel umgesetzt werden.
Mit alphabetischer Nachbarwahl besucht eine rekursive DFS denselben Graphen ab A in der Reihenfolge A, B, D, C, E. Die Reihenfolge unterscheidet sich von BFS, obwohl beide Verfahren dieselben erreichbaren Knoten finden.
Eine Besuchsreihenfolge ist nur eindeutig, wenn auch die Reihenfolge der Nachbarn festgelegt ist. Eine andere zulässige Nachbarreihenfolge kann eine andere, ebenfalls korrekte DFS- oder BFS-Reihenfolge erzeugen.
Den passenden Wegealgorithmus wählen
Nicht jede Frage nach einem günstigen Weg kann mit demselben Verfahren gelöst werden.
| Voraussetzung | Passendes Verfahren | Ergebnis |
|---|---|---|
| alle Kanten gleich bewertet oder ungewichtet | BFS | kleinste Kantenzahl vom Start |
| nichtnegative Kantengewichte | Dijkstra | kleinste Gesamtkosten vom Start |
| negative Einzelkanten möglich | Bellman–Ford | kürzeste Wege und Prüfung auf erreichbare negative Zyklen |
Dijkstra verwaltet für jeden Knoten eine vorläufige Distanz. In jedem Schritt wird ein noch nicht abgeschlossener Knoten mit kleinster Distanz gewählt. Anschließend wird geprüft, ob Wege über diesen Knoten bekannte Distanzen verbessern.
Der gewichtete, ungerichtete Graph besitzt die Kanten A–B mit Gewicht 2, A–C mit 5, B–C mit 1, B–D mit 2 und C–D mit 4.
Start ist A:
- A erhält Distanz
0, alle anderen zunächst unendlich. - Über A erhält B die Distanz
2und C die Distanz5. - B ist als Nächstes an der Reihe. Über B verbessert sich C auf
2 + 1 = 3. D erhält2 + 2 = 4. - Über C ergäbe sich für D
3 + 4 = 7. Das ist schlechter als4, daher bleibt D unverändert.
Der kürzeste Weg von A nach D ist A–B–D mit Gesamtkosten 4. Die Vorgänger D ← B ← A ermöglichen die Rekonstruktion des Weges.
Dijkstra setzt nichtnegative Kantengewichte voraus. Bei negativen Einzelkanten ist Bellman–Ford eine mögliche Wahl; ein erreichbarer Zyklus mit negativem Gesamtgewicht verhindert einen endlichen kürzesten Weg.
Kürzester Weg oder minimaler Spannbaum?
Ein kürzester Weg verbindet einen Start mit einem Ziel möglichst günstig. Ein minimaler Spannbaum verfolgt ein anderes Ziel: Er verbindet alle Knoten eines zusammenhängenden, gewichteten Graphen mit minimalem Gesamtgewicht und ohne Zyklus.
Prim erweitert einen begonnenen Teilbaum wiederholt um eine günstigste Kante zu einem noch nicht enthaltenen Knoten. Kruskal betrachtet Kanten nach steigendem Gewicht und nimmt eine Kante nur auf, wenn kein Zyklus entsteht.
Im gewichteten Graphen aus dem Dijkstra-Beispiel wählt Kruskal zuerst B–C mit Gewicht 1. Danach können A–B und B–D mit Gewicht 2 aufgenommen werden.
Diese drei Kanten verbinden A, B, C und D ohne Zyklus. Ihr Gesamtgewicht ist 1 + 2 + 2 = 5.
Für den kürzesten Weg von A nach D waren dagegen nur die Kanten A–B und B–D wichtig. Der Wegealgorithmus und der Spannbaum beantworten also verschiedene Fragen.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Graphenalgorithmus
- Modellierung: Objekte werden Knoten, Beziehungen werden Kanten
- Darstellung: Adjazenzliste oder Adjazenzmatrix
- Traversierung: BFS sucht schichtweise, DFS sucht in die Tiefe
- Kürzeste Wege: BFS ungewichtet, Dijkstra nichtnegative Gewichte, Bellman–Ford negative Einzelkanten
- Vernetzung: Prim oder Kruskal erzeugen einen minimalen Spannbaum
- Kontrolle: Voraussetzungen, Besuchsmarkierungen und Problemziel prüfen
Abschluss-Check
Prüfe dich zum Schluss: Kannst du bei einer neuen Aufgabe zuerst Knoten, Kanten, Richtung und Gewichte benennen und erst danach den passenden Algorithmus auswählen? Dann trennst du Modellierung, Voraussetzung und Verfahren sauber voneinander.