Algorytmy i struktury danych · Rozdział 8

Hashing und Graphen

In einer Liste suchst du ein Element in O(n), in einem sortierten Array mit binärer Suche in O(log n). Eine Hashtabelle schafft es im Mittel in O(1). Danach geht es um Graphen: Knoten und Kanten, mit denen du Straßennetze, Freundschaften oder Netzwerke beschreibst, und um die Algorithmen, die darin Wege finden.

Die Idee des Hashings

Eine Hashtabelle ist ein Array von Fächern (engl. buckets). Eine Hashfunktion rechnet aus dem Schlüssel eine Zahl, und zahl % größe bestimmt das Fach. Zum Suchen rechnest du dieselbe Funktion noch einmal und schaust nur in dieses eine Fach, statt alle Elemente durchzugehen.

Eine einfache Hashfunktion für Strings:

1h = 02für jedes Zeichen c:  h = (h * 31 + c) % size

Eine gute Hashfunktion verteilt die Schlüssel gleichmäßig und liefert für gleiche Schlüssel immer dasselbe Ergebnis. Genau so arbeitet HashMap: Sie ruft hashCode() des Schlüssels auf und vergleicht im Fach mit equals. Deshalb müssen eigene Klassen als Schlüssel beide Methoden passend überschreiben.

Kollisionen und Lastfaktor

Landen zwei verschiedene Schlüssel im selben Fach, ist das eine Kollision. Sie lassen sich nicht vermeiden: Es gibt viel mehr mögliche Strings als Fächer. Die übliche Lösung ist Verkettung (engl. separate chaining): Jedes Fach ist eine Liste, kollidierende Schlüssel stehen darin hintereinander.

Wie voll die Tabelle ist, misst der Lastfaktor α = Anzahl Elemente / Anzahl Fächer. Bei gleichmäßiger Verteilung liegen in jedem Fach im Mittel α Elemente. Suchen, Einfügen und Löschen kosten dann im Mittel O(1 + α), also O(1), solange α klein bleibt. HashMap vergrößert ihr Array deshalb automatisch, sobald α über 0,75 steigt. Im schlechtesten Fall, wenn alle Schlüssel im selben Fach landen, wird daraus O(n).

1import java.util.*;2
3public class Main {4    static int hash(String key, int size) {5        int h = 0;6        for (int i = 0; i < key.length(); i++) {7            h = (h * 31 + key.charAt(i)) % size;8        }9        return h;10    }11
12    public static void main(String[] args) {13        int size = 7;14        List<List<String>> buckets = new ArrayList<>();15        for (int i = 0; i < size; i++) {16            buckets.add(new LinkedList<>());17        }18
19        String[] names = {"Tom", "Ana", "Max", "Eva", "Leo"};20        for (String name : names) {21            buckets.get(hash(name, size)).add(name);22        }23
24        for (int i = 0; i < size; i++) {25            System.out.println(i + ": " + buckets.get(i));26        }27        System.out.println("load factor: " + (double) names.length / size);28    }29}

Tom und Eva kollidieren in Fach 1. Bei 5 Elementen in 7 Fächern ist der Lastfaktor etwa 0,71.

Graphen speichern

Ein Graph besteht aus Knoten und Kanten. In einem ungerichteten Graphen gilt eine Kante in beide Richtungen, in einem gerichteten nur in eine. Haben Kanten eine Länge oder Kosten, heißt der Graph gewichtet. Die Knoten nummerierst du am einfachsten mit 0 bis n - 1.

Es gibt zwei übliche Darstellungen, mit n Knoten und m Kanten:

Adjazenzliste: Speicher O(n + m). Ob es die Kante a–b gibt und alle Nachbarn von a findest du in O(Grad von a).
Adjazenzmatrix: Speicher O(n²). Ob es die Kante a–b gibt, siehst du in O(1), alle Nachbarn von a kosten O(n).

Die Adjazenzliste (List<List<Integer>>) passt für die meisten Graphen, weil sie nur so viel Platz braucht, wie es Kanten gibt. Die Matrix (boolean[][]) lohnt sich bei sehr dichten Graphen oder wenn du oft einzelne Kanten prüfst.

1import java.util.*;2
3public class Main {4    public static void main(String[] args) {5        int n = 5;6        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}};7
8        // adjacency list: one list of neighbours per node9        List<List<Integer>> list = new ArrayList<>();10        for (int i = 0; i < n; i++) {11            list.add(new ArrayList<>());12        }13        // adjacency matrix: matrix[a][b] is true if there is an edge14        boolean[][] matrix = new boolean[n][n];15
16        for (int[] e : edges) {17            list.get(e[0]).add(e[1]);18            list.get(e[1]).add(e[0]);19            matrix[e[0]][e[1]] = true;20            matrix[e[1]][e[0]] = true;21        }22
23        System.out.println("neighbours of 1: " + list.get(1));24        System.out.println("edge 2-4? " + matrix[2][4]);25        System.out.println("edge 3-4? " + matrix[3][4]);26    }27}

Breitensuche und Tiefensuche

Beide besuchen alle Knoten, die vom Start aus erreichbar sind, jeden genau einmal. Ein boolean-Array merkt sich, wer schon besucht ist, sonst laufen sie in Kreisen.

Die Breitensuche (BFS) arbeitet mit einer Queue: erst alle Nachbarn, dann deren Nachbarn, Schicht für Schicht. Darum findet sie in einem ungewichteten Graphen den kürzesten Weg: Ein Knoten in Schicht k ist genau k Kanten vom Start entfernt.
Die Tiefensuche (DFS) geht erst so tief wie möglich und kehrt dann um. Sie lässt sich kurz rekursiv schreiben (der Aufrufstapel ersetzt den Stack) und eignet sich, um Komponenten zu finden oder einen Graphen vollständig zu durchlaufen.

Beide kosten mit einer Adjazenzliste O(n + m): Jeder Knoten kommt einmal dran, jede Kante wird von beiden Enden aus einmal angeschaut.

1import java.util.*;2
3public class Main {4    static List<List<Integer>> graph = List.of(5            List.of(1, 2), List.of(0, 3, 4), List.of(0, 4), List.of(1), List.of(1, 2));6
7    static List<Integer> bfs(int start) {8        List<Integer> order = new ArrayList<>();9        boolean[] visited = new boolean[graph.size()];10        Deque<Integer> queue = new ArrayDeque<>();11        visited[start] = true;12        queue.add(start);13        while (!queue.isEmpty()) {14            int v = queue.poll();15            order.add(v);16            for (int w : graph.get(v)) {17                if (!visited[w]) {18                    visited[w] = true; // mark when adding, not when taking out19                    queue.add(w);20                }21            }22        }23        return order;24    }25
26    static void dfs(int v, boolean[] visited, List<Integer> order) {27        visited[v] = true;28        order.add(v);29        for (int w : graph.get(v)) {30            if (!visited[w]) {31                dfs(w, visited, order);32            }33        }34    }35
36    public static void main(String[] args) {37        System.out.println("BFS: " + bfs(0));38        List<Integer> order = new ArrayList<>();39        dfs(0, new boolean[graph.size()], order);40        System.out.println("DFS: " + order);41    }42}

Kürzeste Wege mit Dijkstra

Haben Kanten verschiedene Längen, reicht die Breitensuche nicht: Der Weg mit den wenigsten Kanten ist nicht unbedingt der kürzeste. Der Algorithmus von Dijkstra löst das für Graphen ohne negative Gewichte:

dist[start] = 0, alle anderen „unendlich“.
Nimm den noch nicht fertigen Knoten mit dem kleinsten dist. Sein Abstand steht jetzt fest.
Prüfe seine Nachbarn: Ist der Weg über ihn kürzer, trage den neuen Abstand ein (Relaxieren).
Wiederhole, bis alle erreichbaren Knoten fertig sind.

Den Knoten mit dem kleinsten Abstand liefert eine PriorityQueue (ein Heap aus Kapitel 7). So kostet Dijkstra O((n + m) · log n).

1import java.util.*;2
3public class Main {4    public static void main(String[] args) {5        // neighbours as {node, length}6        List<List<int[]>> graph = List.of(7                List.of(new int[]{1, 4}, new int[]{2, 1}),8                List.of(new int[]{0, 4}, new int[]{2, 2}, new int[]{3, 1}),9                List.of(new int[]{0, 1}, new int[]{1, 2}, new int[]{3, 5}),10                List.of(new int[]{1, 1}, new int[]{2, 5}));11
12        int[] dist = new int[graph.size()];13        Arrays.fill(dist, Integer.MAX_VALUE);14        dist[0] = 0;15        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> Integer.compare(x[1], y[1]));16        queue.add(new int[]{0, 0});17
18        while (!queue.isEmpty()) {19            int[] current = queue.poll();20            int v = current[0];21            if (current[1] > dist[v]) {22                continue; // outdated entry23            }24            System.out.println("done: " + v + " at " + dist[v]);25            for (int[] edge : graph.get(v)) {26                int candidate = dist[v] + edge[1];27                if (candidate < dist[edge[0]]) {28                    dist[edge[0]] = candidate;29                    queue.add(new int[]{edge[0], candidate});30                }31            }32        }33        System.out.println(Arrays.toString(dist));34    }35}

Knoten 1 bekommt zuerst den Abstand 4 über die direkte Kante. Über Knoten 2 sind es nur 1 + 2 = 3. Der alte Eintrag {1, 4} liegt danach noch in der Queue und wird übersprungen.

Typowe błędy

Schlüssel mit == verglichen
In einer eigenen Hashtabelle prüft entry.key == key, ob es dasselbe Objekt ist, nicht ob die Strings gleich sind. Ein Schlüssel, der zur Laufzeit gebaut wurde, wird dann nicht gefunden. Vergleiche mit entry.key.equals(key). Aus demselben Grund müssen eigene Schlüsselklassen equals und hashCode gemeinsam überschreiben.
Zu spät als besucht markiert
Markierst du einen Knoten in der Breitensuche erst, wenn du ihn aus der Queue nimmst, kann ihn ein anderer Nachbar vorher noch einmal hineinstellen. Er wird dann doppelt besucht. Markiere ihn deshalb beim Hineinstellen:
```
1if (!visited[w]) {2    visited[w] = true;3    queue.add(w);4}
```
Falscher Algorithmus für den kürzesten Weg
Die Breitensuche zählt Kanten. In einem gewichteten Graphen liefert sie deshalb falsche Abstände, dort brauchst du Dijkstra. Dijkstra wiederum setzt voraus, dass kein Gewicht negativ ist: Ein Abstand, der einmal feststeht, darf später nicht mehr kleiner werden.