Zum Inhalt
wannacode

Graph: Adjazenzliste und Matrix

Kurz gesagt: Ein Graph ist eine Menge von Knoten und Kanten; im Programm speichert man ihn als Adjazenzliste mit O(V + E) Speicher oder als Adjazenzmatrix mit O(V²).

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).

String[] stops = {
    "Lager", "Bahnhof", "Markt", "Platz",
    "Park", "Kino", "Krankenhaus", "Stadion",
};
String[][] 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: Map<String, List<String>>. 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

Map<String, List<String>> graph = new HashMap<>();
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < stops.length; i++) {
    graph.put(stops[i], new ArrayList<>());
    index.put(stops[i], i);
}
int n = stops.length;
boolean[][] matrix = new boolean[n][n];
for (String[] street : streets) {
    String a = street[0], b = street[1];
    graph.get(a).add(b);
    graph.get(b).add(a);
    int i = index.get(a), j = index.get(b);
    matrix[i][j] = matrix[j][i] = true;
}
Schritt für Schritt, in Worten
  1. 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.
  2. 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].
  3. Lager – Markt: Markt kommt in der Liste von Lager nach Bahnhof. Die Reihenfolge in einer Liste ist die Reihenfolge der Straßen.
  4. Eine Straße in beide Richtungen wird zweimal eingetragen: in beiden Listen und in beiden Zellen. Darum ist die Matrix symmetrisch zur Diagonale.
  5. Markt – Park und Platz – Kino führen über den Fluss. Markt und Platz haben jetzt je drei Nachbarn, die anderen zwei.
  6. Die letzten Straßen am anderen Ufer. Jede Liste wächst nur um ihre wirklichen Straßen.
  7. 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 (String stop : stops) {
    System.out.println(stop + ": " + String.join(", ", graph.get(stop)));
}
for (boolean[] row : matrix) {
    StringBuilder line = new StringBuilder();
    for (boolean cell : row) line.append(cell ? "1 " : "0 ");
    System.out.println(line.toString().trim());
}
Ausgabe
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?

String[][] streets = {
    {"Markt", "Platz"}, {"Platz", "Kino"},
    {"Bahnhof", "Platz"},
};
Map<String, List<String>> graph = new HashMap<>();
for (String stop : stops) graph.put(stop, new ArrayList<>());
for (String[] street : streets) {
    graph.get(street[0]).add(street[1]);
    graph.get(street[1]).add(street[0]);
}
System.out.println(String.join(", ", graph.get("Platz")));
Antwort

Probier es aus

Ergänze

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

for (String[] street : streets) {
    int i = index.get(street[0]), j = index.get(street[1]);
    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.

int matrixLooks = 0, matrixFound = 0;
for (int i = 0; i < stops.length; i++) {
    for (int j = 0; j < stops.length; j++) {
        matrixLooks++;
        if (matrix[i][j]) matrixFound++;
    }
}
int listLooks = 0, listFound = 0;
for (String stop : stops) {
    listLooks++;
    for (String next : graph.get(stop)) {
        listLooks++;
        listFound++;
    }
}
System.out.println("Matrix: " + matrixLooks + " Blicke, " + matrixFound + " Nachbarn");
System.out.println("Liste: " + listLooks + " Blicke, " + listFound + " Nachbarn");
boolean inMatrix = matrix[index.get("Markt")][index.get("Park")];
boolean inList = graph.get("Markt").contains("Park");
System.out.println("Gibt es eine Straße Markt - Park? " + inMatrix + " " + inList);
Ausgabe
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)
Algorithmusn = 10n = 1.000n = 5.000n = 100.000
Matrix: die ganze Zeile jeder Kreuzung1001.000.00025.000.000≈ 10.000.000.000
Adjazenzliste: nur die echten Straßen364.87224.716498.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.
int matrixLooks = 0, matrixFound = 0;
for (int i = 0; i < stops.length; i++) {
    for (int j = 0; j < stops.length; j++) {
        matrixLooks++;
        if (matrix[i][j]) matrixFound++;
    }
}
int listLooks = 0, listFound = 0;
for (String stop : stops) {
    listLooks++;
    for (String next : graph.get(stop)) {
        listLooks++;
        listFound++;
    }
}
System.out.println("Matrix: " + matrixLooks + " Blicke, " + matrixFound + " Nachbarn");
System.out.println("Liste: " + listLooks + " Blicke, " + listFound + " Nachbarn");
boolean inMatrix = matrix[index.get("Markt")][index.get("Park")];
boolean inList = graph.get("Markt").contains("Park");
System.out.println("Gibt es eine Straße Markt - Park? " + inMatrix + " " + inList);

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“.

record Street(String to, int meters) {}


String[] lines = {
    "Lager Bahnhof 400",
    "Lager Markt 300",
    "Bahnhof Platz 500",
    // …
};
Map<String, List<Street>> graph = new HashMap<>();
for (String stop : stops) graph.put(stop, new ArrayList<>());
for (String line : lines) {
    String[] part = line.split(" ");
    int meters = Integer.parseInt(part[2]);
    graph.get(part[0]).add(new Street(part[1], meters));
    graph.get(part[1]).add(new Street(part[0], meters));
}
record Street ist der Nachbar zusammen mit der Länge. Die Zeile wird mit split zerlegt, und die Meter werden mit Integer.parseInt zur Zahl.
String text = graph.get("Markt").stream()
        .map(s -> s.to() + " " + s.meters() + " m")
        .collect(Collectors.joining(", "));
System.out.println("Markt" + ": " + text);
Ausgabe
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:

Map<String, List<String>> graph = new HashMap<>();
for (String stop : stops) graph.put(stop, new ArrayList<>());
for (String[] street : streets) {
    String a = street[0], b = street[1];
    graph.get(a).add(b);
    graph.get(b).add(b);
}
Ausgabe
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

  • HashMap behält die Reihenfolge ihrer Schlüssel nicht. Darum gehen die Programme über das Array stops, nicht über graph.keySet(). Brauchst du eine Reihenfolge, gibt es LinkedHashMap (Einfügereihenfolge) und TreeMap (sortierte Schlüssel).
  • Sind die Haltestellen nicht im Voraus bekannt, wird die Liste bei der ersten Straße angelegt: graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b).
  • boolean[] braucht ein Byte pro Zelle. BitSet hält ein Bit, achtmal weniger, aber 1,6 Milliarden Bit sind immer noch 200 MB.

Ü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:

String[] 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",
};
String[] oneWay = {
    "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):

Ausgabe
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?
2. Die App fragt: „Gibt es eine Straße zwischen Markt und Park?“ Was kostet die Frage?
3. Die Straße Bahnhof → Platz ist eine Einbahnstraße. Was steht in der Adjazenzliste?
4. Wann ist die Matrix die bessere Wahl?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·