Graphen in Python: Adjazenzliste und Matrix im Vergleich

Problem

Die Tabelle, die nicht passt

Eine Kurierfirma hält das Straßennetz der Stadt in einer Tabelle: eine Zeile und eine Spalte für jede Kreuzung, und die Zelle enthält 1, wenn es zwischen den beiden eine Straße gibt. Als die Firma in einem Stadtteil mit 300 Kreuzungen arbeitete, hatte die Tabelle 90.000 Zellen, und niemand beschwerte sich.

Dann übernahm die Firma die ganze Stadt: 40.000 Kreuzungen. Die Tabelle wurde 40.000 × 40.000 = 1,6 Milliarden Zellen groß. Selbst mit einem Byte pro Zelle sind das 1,6 GB, und der Server stürzte bei jedem Laden der Karte ab.

Am ärgerlichsten ist, dass fast alles in der Tabelle 0 ist. Von einer Kreuzung gehen drei oder vier Straßen ab, nicht 40.000. Wie behältst du nur die Straßen, die es gibt?

Die Idee

Haltestellen und Straßen: ein Graph

Die Lieferkarte wird durch zwei Dinge beschrieben: Haltestellen (Kreuzungen, Lager, Adressen) und die Straßen dazwischen. So etwas heißt Graph. Die Haltestellen sind seine Knoten, die Straßen seine Kanten. Die Zahl der Knoten schreibt man V, die der Kanten E.

Ungerichteter Graph: Die Straße gilt in beide Richtungen. Gibt es einen Weg vom Bahnhof zum Platz, gibt es auch einen zurück.
Gerichteter Graph: Einbahnstraßen. Eine Kante Bahnhof → Platz gibt keinen Weg Platz → Bahnhof.
Gewichteter Graph: Jede Kante trägt eine Zahl: Länge in Metern, Minuten, einen Preis in €.

Hier ist unsere Stadt: 8 Haltestellen und 9 Straßen in beide Richtungen. Der Fluss teilt sie in zwei Teile, die zwei Brücken verbinden. So kommt der Graph aus dem System der Firma: eine Liste der Haltestellen und eine Liste der Straßen (ein Namenspaar pro Zeile).

stops = [
    "Lager", "Bahnhof", "Markt", "Platz",
    "Park", "Kino", "Krankenhaus", "Stadion",
]
streets = [
    ("Lager", "Bahnhof"), ("Lager", "Markt"),
    ("Bahnhof", "Platz"), ("Markt", "Platz"),
    ("Markt", "Park"), ("Platz", "Kino"),
    ("Kino", "Krankenhaus"), ("Park", "Stadion"),
    ("Krankenhaus", "Stadion"),
]

Dieselbe Stadt brauchst du im ganzen Modul: für den kürzesten Weg, für die Inseln nach einer gesperrten Brücke und später für Dijkstra.

Die Idee

Zwei Arten, ihn zu speichern

Adjazenzmatrix. Du nummerierst die Haltestellen von 0 bis V − 1. Die Tabelle ist V × V, und die Zelle [i][j] sagt, ob es eine Straße von i nach j gibt. Das ist die Tabelle aus dem Problem.

Adjazenzliste. Für jede Haltestelle behältst du nur die Liste ihrer Nachbarn. Im Code ist das ein Dictionary von einem Namen auf eine Liste: ein dict von Name auf Liste. Es gibt keine leeren Plätze: Eine Straße, die es nicht gibt, kostet nichts.

Beide werden aus derselben Liste von Straßen gebaut, in derselben Schleife.

Sieh es dir an

Eine Straße, zwei Einträge

graph = {stop: [] for stop in stops}
index = {stop: i for i, stop in enumerate(stops)}
matrix = [[False] * len(stops) for _ in stops]
for a, b in streets:
    graph[a].append(b)
    graph[b].append(a)
    i, j = index[a], index[b]
    matrix[i][j] = matrix[j][i] = True

Schritt für Schritt, in Worten

Acht Haltestellen, noch keine Straßen. Jede bekommt eine leere Liste und eine Nummer: ihre Zeile und Spalte in der 8 × 8-Matrix, die nur aus Nullen besteht.
Die erste Straße, Lager – Bahnhof: Bahnhof kommt in die Liste von Lager, und Lager in die Liste von Bahnhof. In der Matrix werden zwei Zellen zu 1: [0][1] und [1][0].
Lager – Markt: Markt kommt in der Liste von Lager nach Bahnhof. Die Reihenfolge in einer Liste ist die Reihenfolge der Straßen.
Eine Straße in beide Richtungen wird zweimal eingetragen: in beiden Listen und in beiden Zellen. Darum ist die Matrix symmetrisch zur Diagonale.
Markt – Park und Platz – Kino führen über den Fluss. Markt und Platz haben jetzt je drei Nachbarn, die anderen zwei.
Die letzten Straßen am anderen Ufer. Jede Liste wächst nur um ihre wirklichen Straßen.
9 Straßen: 18 Einträge in den Listen, 64 Zellen in der Matrix, davon 46 Nullen. Bei 40 000 Kreuzungen sind das etwa 120 000 Einträge gegen 1,6 Milliarden Zellen.

Das ganze Programm gibt die Listen und die Matrix aus:

for stop in stops:
    print(stop + ": " + ", ".join(graph[stop]))
for row in matrix:
    print(" ".join("1" if cell else "0" for cell in row))

Lager: Bahnhof, Markt
Bahnhof: Lager, Platz
Markt: Lager, Platz, Park
Platz: Bahnhof, Markt, Kino
Park: Markt, Stadion
Kino: Platz, Krankenhaus
Krankenhaus: Kino, Stadion
Stadion: Park, Krankenhaus
0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
0 1 1 0 0 1 0 0
0 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0

Die Liste jeder Haltestelle hat die Reihenfolge, in der die Straßen kamen. Die Matrix ist symmetrisch: Zeile 2 und Spalte 2 sind gleich, weil jede Straße in beide Richtungen gilt.

Probier es aus

Sag die Ausgabe voraus

Drei Straßen rund um den Platz, in anderer Reihenfolge. Was gibt das Programm aus?

streets = [
    ("Markt", "Platz"), ("Platz", "Kino"),
    ("Bahnhof", "Platz"),
]
graph = {stop: [] for stop in stops}
for a, b in streets:
    graph[a].append(b)
    graph[b].append(a)
print(", ".join(graph["Platz"]))

Antwort

Markt, Kino, Bahnhof

Bahnhof, Markt, Kino

Bahnhof, Kino, Markt

Probier es aus

Ergänze

Eine Straße in beide Richtungen muss in beide Zellen geschrieben werden:

for a, b in streets:
    i, j = index[a], index[b]
    matrix[i][j] =  = True

Die Idee

Was es kostet

Die drei Fragen, die die Kurier-App ständig stellt, kosten unterschiedlich viel:

	Matrix	Adjazenzliste
Speicher	V² Zellen	V Listen und 2E Einträge: O(V + E)
Gibt es eine Straße zwischen a und b?	eine Zelle: O(1)	ein Gang über die Nachbarn von a: O(Nachbarn)
Wer sind die Nachbarn von a?	die ganze Zeile: O(V)	nur die Nachbarn: O(Nachbarn)

Das Programm geht in beiden Varianten über die Nachbarn jeder Haltestelle und zählt jeden Blick: in der Matrix jede Zelle, in der Liste jede Haltestelle und jeden Eintrag.

matrix_looks = matrix_found = 0
for i in range(len(stops)):
    for j in range(len(stops)):
        matrix_looks += 1
        if matrix[i][j]:
            matrix_found += 1
list_looks = list_found = 0
for stop in stops:
    list_looks += 1
    for nxt in graph[stop]:
        list_looks += 1
        list_found += 1
print(f"Matrix: {matrix_looks} Blicke, {matrix_found} Nachbarn")
print(f"Liste: {list_looks} Blicke, {list_found} Nachbarn")
in_matrix = matrix[index["Markt"]][index["Park"]]
in_list = "Park" in graph["Markt"]
print(f"Gibt es eine Straße Markt - Park? {in_matrix} {in_list}")

Matrix: 64 Blicke, 18 Nachbarn
Liste: 26 Blicke, 18 Nachbarn
Gibt es eine Straße Markt - Park? True True

Bei 8 Haltestellen ist der Unterschied klein. Lass dasselbe auf einer Gitterstadt mit n Kreuzungen laufen, jede mit ihrem rechten und ihrem unteren Nachbarn verbunden:

Matrix: die ganze Zeile jeder Kreuzung O(n²)
Adjazenzliste: nur die echten Straßen O(n)

Algorithmus	n = 10	n = 1.000	n = 5.000	n = 100.000
Matrix: die ganze Zeile jeder Kreuzung	100	1.000.000	25.000.000	≈ 10.000.000.000
Adjazenzliste: nur die echten Straßen	36	4.872	24.716	498.734

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

matrix_looks = matrix_found = 0
for i in range(len(stops)):
    for j in range(len(stops)):
        matrix_looks += 1
        if matrix[i][j]:
            matrix_found += 1
list_looks = list_found = 0
for stop in stops:
    list_looks += 1
    for nxt in graph[stop]:
        list_looks += 1
        list_found += 1
print(f"Matrix: {matrix_looks} Blicke, {matrix_found} Nachbarn")
print(f"Liste: {list_looks} Blicke, {list_found} Nachbarn")
in_matrix = matrix[index["Markt"]][index["Park"]]
in_list = "Park" in graph["Markt"]
print(f"Gibt es eine Straße Markt - Park? {in_matrix} {in_list}")

Bei 1000 Kreuzungen macht die Matrix 1.000.000 Blicke und die Liste 4.872. Bei 5000 ist die Matrix schon bei 25.000.000, die Liste bei 24.716. Diese Zahlen sind auch der Speicher: Die Matrix hält n² Zellen, die Liste so viele Einträge, wie sie Blicke macht.

Darum werden Stadtkarten, soziale Netzwerke und Abhängigkeiten zwischen Paketen als Adjazenzlisten gespeichert. Das sind dünne Graphen: E liegt in der Größenordnung von V, nicht von V².

Genauer, für Neugierige

Die Matrix gewinnt, wenn der Graph dicht ist: Fast jeder ist mit fast jedem verbunden, zum Beispiel eine Tabelle der Entfernungen zwischen 50 Lagern. Dann sind V² Zellen keine Verschwendung, und „Gibt es eine Kante?“ ist eine Zelle. Es gibt auch einen Mittelweg: Eine Adjazenzliste mit einer Menge (set) statt einer Liste beantwortet „Gibt es eine Straße?“ im Mittel in O(1), zum Preis von mehr Speicher pro Eintrag.

Die Idee

Richtung und Länge

Im echten System hat eine Straße eine Länge, und manche Straßen sind Einbahnstraßen. Die Adjazenzliste hält dann ein Paar: wohin und wie viele Meter. Das System schickt sie als Text, eine Straße pro Zeile: „von nach Meter“.

lines = [
    "Lager Bahnhof 400",
    "Lager Markt 300",
    "Bahnhof Platz 500",
    # …
]
graph = {stop: [] for stop in stops}
for line in lines:
    a, b, meters = line.split()
    graph[a].append((b, int(meters)))
    graph[b].append((a, int(meters)))

Der Nachbar und die Länge sind ein Tupel (b, meters). split() zerlegt die Zeile in drei Teile, und int macht aus den Metern eine Zahl.

text = ", ".join(f"{to} {meters} m" for to, meters in graph["Markt"])
print("Markt" + ": " + text)

Markt: Lager 300 m, Platz 350 m, Park 600 m

Eine Einbahnstraße ist nur das erste add: b kommt in die Liste von a, nicht umgekehrt. In der Matrix wird nur [i][j] gefüllt, und sie ist nicht mehr symmetrisch. In einer gewichteten Matrix hält die Zelle die Länge, und eine fehlende Straße ist ein besonderer Wert, zum Beispiel unendlich.

Probier es aus

Finde den Fehler

Ein Kollege baut die Adjazenzliste. Das Programm gibt aus:

graph = {stop: [] for stop in stops}
for a, b in streets:
    graph[a].append(b)
    graph[b].append(b)

Lager: Bahnhof, Markt
Bahnhof: Bahnhof, Platz
Markt: Markt, Platz, Park
Platz: Platz, Platz, Kino
Park: Park, Stadion
Kino: Kino, Krankenhaus
Krankenhaus: Krankenhaus, Stadion
Stadion: Stadion, Stadion

Der Bahnhof ist sein eigener Nachbar, und das Lager fehlt in seiner Liste. Welche Zeile hat den Fehler?

Wähle die Zeile mit dem Fehler.

Genauer

Wie es in den anderen Sprachen ist

Falle: [[False] * n] * n macht n Verweise auf dieselbe Zeile. Änderst du matrix[0][1], ändert sich Spalte 1 in jeder Zeile. Darum wird die Matrix mit [[False] * n for _ in range(n)] gebaut.
Jede Zelle einer Liste ist ein Verweis (8 Byte), auch wenn der Wert False ist. Eine 40.000 × 40.000 große Matrix aus Listen sind allein für die Verweise etwa 12,8 GB. Für numerische Tabellen gibt es bytearray oder die Arrays von NumPy.
collections.defaultdict(list) legt die leere Liste bei der ersten Straße selbst an: graph[a].append(b) ohne die Schleife davor.

Übung

Straßen und Meter

Löse die Aufgabe in deinem Editor.

Die Straßen einer Haltestelle. Das System schickt die Straßen in beide Richtungen als Zeilen „von nach Meter“ und die Einbahnstraßen getrennt:

lines = [
    "Lager Bahnhof 400",
    "Lager Markt 300",
    "Bahnhof Platz 500",
    "Markt Platz 350",
    "Markt Park 600",
    "Platz Kino 450",
    "Kino Krankenhaus 300",
    "Park Stadion 500",
    "Krankenhaus Stadion 250",
]

one_way = [
    "Bahnhof Markt 650",
    "Stadion Kino 550",
]

Baue den gewichteten Graphen: Die Straßen in beide Richtungen kommen in beide Listen, die Einbahnstraßen nur in die Liste der ersten Haltestelle. Gib für jede Haltestelle aus, wie viele Straßen von ihr abgehen und wie viele Meter sie zusammen lang sind, und am Ende die Haltestelle mit den meisten Straßen (bei Gleichstand die erste in der Reihenfolge):

Lager: 2 Straßen, 700 m
Bahnhof: 3 Straßen, 1550 m
Markt: 3 Straßen, 1250 m
Platz: 3 Straßen, 1300 m
Park: 2 Straßen, 1100 m
Kino: 2 Straßen, 750 m
Krankenhaus: 2 Straßen, 550 m
Stadion: 3 Straßen, 1300 m
Meiste Straßen: Bahnhof (3)

Weitere Aufgaben

Sackgassen. Gib die Haltestellen aus, von denen nur eine Straße abgeht.
Matrix mit Metern. Baue eine Matrix, in der die Zelle die Länge der Straße ist oder -1, wenn es keine Straße gibt, und gib sie aus.
Die andere Richtung. Baue aus dem Graphen mit den Einbahnstraßen den umgekehrten: Jede Kante a → b wird zu b → a. Welchen der beiden brauchst du, wenn du fragst „Von welchen Haltestellen kommt man zum Krankenhaus?“

Test

Teste dich

1. Die Stadt hat 40.000 Kreuzungen, und von jeder gehen etwa 3 Straßen ab. Wie viele Zellen hat die Adjazenzmatrix?60.000: eine für jede Straße1,6 Milliarden: 40.000 × 40.000120.000: eine für jedes Ende einer Straße

2. Die App fragt: „Gibt es eine Straße zwischen Markt und Park?“ Was kostet die Frage?Eine Zelle in der Matrix, ein Gang über die Nachbarn von Markt in der ListeDie ganze Zeile in der Matrix, einen Schritt in der ListeEinen Schritt in beiden

3. Die Straße Bahnhof → Platz ist eine Einbahnstraße. Was steht in der Adjazenzliste?Jeder steht in der Liste des anderenKeinerPlatz steht in der Liste von Bahnhof, aber Bahnhof nicht in der Liste von Platz

4. Wann ist die Matrix die bessere Wahl?Wenn die Stadt groß und dünn besetzt istWenn der Graph dicht ist und du oft fragst „Gibt es eine Kante zwischen diesen beiden?“Immer, weil sie schneller ist

Graph: Adjazenzliste und Matrix

Cookies