Tablica mieszająca, BFS, DFS i Dijkstra w Javie

Tablica mieszająca to tablica kubełków (buckets). Funkcja mieszająca (funkcja skrótu) zamienia klucz na liczbę, a liczba % rozmiar wyznacza kubełek. Przy wyszukiwaniu liczysz tę samą funkcję jeszcze raz i zaglądasz tylko do tego jednego kubełka, zamiast przechodzić wszystkie elementy.

Prosta funkcja mieszająca dla napisów:

1h = 02dla każdego znaku c:  h = (h * 31 + c) % size

Dobra funkcja mieszająca rozkłada klucze równomiernie i dla równych kluczy zawsze daje ten sam wynik. Dokładnie tak działa HashMap z kolekcji Javy: wywołuje hashCode() klucza, a w kubełku porównuje przez equals. Dlatego własne klasy używane jako klucze muszą odpowiednio nadpisać obie metody.

Jeśli dwa różne klucze trafią do tego samego kubełka, jest to kolizja. Kolizji nie da się uniknąć: możliwych napisów jest dużo więcej niż kubełków. Typowym rozwiązaniem jest metoda łańcuchowa (separate chaining): każdy kubełek jest listą, a kolidujące klucze stoją w niej jeden za drugim.

To, jak pełna jest tablica, mierzy współczynnik wypełnienia α = liczba elementów / liczba kubełków. Przy równomiernym rozkładzie w każdym kubełku leży średnio α elementów. Wyszukiwanie, wstawianie i usuwanie kosztują wtedy średnio O(1 + α), czyli O(1), dopóki α pozostaje małe. Dlatego HashMap automatycznie powiększa swoją tablicę, gdy tylko α przekroczy 0,75. W najgorszym przypadku, gdy wszystkie klucze trafią do tego samego kubełka, robi się z tego 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 i Eva kolidują w kubełku 1. Przy 5 elementach w 7 kubełkach współczynnik wypełnienia wynosi około 0,71.

Graf składa się z wierzchołków i krawędzi. W grafie nieskierowanym krawędź działa w obie strony, w skierowanym tylko w jedną. Jeśli krawędzie mają długość albo koszt, graf nazywa się ważonym. Wierzchołki najłatwiej ponumerować od 0 do n - 1.

Są dwie typowe reprezentacje, przy n wierzchołkach i m krawędziach:

• Lista sąsiedztwa: pamięć O(n + m). To, czy istnieje krawędź a–b, i wszystkich sąsiadów a znajdziesz w O(stopień a).
• Macierz sąsiedztwa: pamięć O(n²). To, czy istnieje krawędź a–b, widzisz w O(1), wszyscy sąsiedzi a kosztują O(n).

Lista sąsiedztwa (List<List<Integer>>) pasuje do większości grafów, bo potrzebuje tylko tyle miejsca, ile jest krawędzi. Macierz (boolean[][]) opłaca się przy bardzo gęstych grafach albo gdy często sprawdzasz pojedyncze krawędzie.

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}

Oba algorytmy odwiedzają wszystkie wierzchołki osiągalne ze startu, każdy dokładnie raz. Tablica typu boolean zapamiętuje, kto już był odwiedzony, bo inaczej chodziłyby w kółko.

• Przeszukiwanie wszerz (BFS) działa z kolejką: najpierw wszyscy sąsiedzi, potem ich sąsiedzi, warstwa po warstwie. Dlatego w grafie nieważonym znajduje najkrótszą drogę: wierzchołek w warstwie k jest dokładnie k krawędzi od startu.
• Przeszukiwanie w głąb (DFS) idzie najpierw tak głęboko, jak się da, a potem zawraca. Da się je krótko zapisać rekurencyjnie (stos wywołań zastępuje stos) i nadaje się do znajdowania spójnych składowych albo przejścia całego grafu.

Z listą sąsiedztwa oba kosztują O(n + m): każdy wierzchołek jest przetwarzany raz, a każda krawędź oglądana raz z każdego końca.

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}

Jeśli krawędzie mają różne długości, przeszukiwanie wszerz nie wystarcza: droga z najmniejszą liczbą krawędzi nie musi być najkrótsza. Algorytm Dijkstry rozwiązuje to dla grafów bez ujemnych wag:

1. dist[start] = 0, wszystkie inne „nieskończoność”.
2. Weź jeszcze nieukończony wierzchołek z najmniejszym dist. Jego odległość jest teraz ostateczna.
3. Sprawdź jego sąsiadów: jeśli droga przez niego jest krótsza, wpisz nową odległość (relaksacja).
4. Powtarzaj, aż wszystkie osiągalne wierzchołki będą ukończone.

Wierzchołek z najmniejszą odległością podaje PriorityQueue, czyli kopiec. Dzięki temu Dijkstra kosztuje 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}

Wierzchołek 1 dostaje najpierw odległość 4 przez bezpośrednią krawędź. Przez wierzchołek 2 to tylko 1 + 2 = 3. Stary wpis {1, 4} leży potem nadal w kolejce i zostaje pominięty.