Test maturalny:  Grafy i drzewa

Graf

Struktura danych: zbiór wierzchołków V i krawędzi E ⊆ V × V.

Skierowany / nieskierowany. Ważony / nieważony.

Macierz sąsiedztwa

Tablica n×n, gdzie M[u][v] = 1, gdy krawędź istnieje.

Pamięć O(n²). Sprawdzenie krawędzi O(1).

Lista sąsiedztwa

Tablica list — dla każdego wierzchołka lista sąsiadów.

Pamięć O(n + m). Najczęstsza reprezentacja.

BFS

Breadth-First Search — przeszukiwanie wszerz z kolejką FIFO.

Najkrótsza ścieżka w grafie nieważonym.

DFS

Depth-First Search — przeszukiwanie w głąb (rekurencyjnie lub stos).

Topologiczne sortowanie, cykle.

Drzewo

Graf acykliczny spójny — n wierzchołków i n − 1 krawędzi.

Korzeń, węzły, liście.

BST

Binary Search Tree — drzewo binarne, w którym klucze w lewym poddrzewie węzła są mniejsze od jego klucza, a w prawym — większe.

Wstawianie O(log n) średnio, O(n) najgorzej.

Przechodzenie drzewa

Pre-order (V-L-P), in-order (L-V-P), post-order (L-P-V).

BST in-order daje rosnący ciąg.

Dijkstra

Algorytm najkrótszych ścieżek od źródła — krawędzie nieujemne.

Z kopcem priorytetowym O((n + m) log n).

Bellman-Ford

Algorytm najkrótszych ścieżek — dopuszcza krawędzie ujemne, wykrywa cykle ujemne.

Złożoność O(n·m).

MST

Minimum Spanning Tree — drzewo rozpinające o minimalnej sumie wag.

Algorytmy: Kruskal, Prim, Boruvka.

Union-Find

Struktura zbiorów rozłącznych — operacje find i union w prawie O(1).

Używana w Kruskalu do sprawdzania cykli.

1. 1 Poznaj dwie reprezentacje grafu: macierz sąsiedztwa dla grafów gęstych (m bliskie n²) i listy sąsiedztwa dla rzadkich.
2. 2 Ćwicz BFS i DFS ręcznie na małych grafach (5–8 wierzchołków): zapisuj stan kolejki albo stosu po każdym kroku.
3. 3 Drzewo BST ćwicz przez cztery operacje: wstawianie, wyszukiwanie, usuwanie i przechodzenie in-order, które wypisuje klucze rosnąco.
4. 4 Przed użyciem algorytmu Dijkstry sprawdź, czy wagi krawędzi są nieujemne.
5. 5 Algorytm Kruskala ćwicz ze strukturą zbiorów rozłącznych, algorytm Prima — z kolejką priorytetową. Oba dają drzewo o tej samej sumie wag.
6. 6 Liczbę dróg w grafie skierowanym bez cykli wygodnie liczyć rekurencyjnie z zapamiętywaniem wyników.
7. 7 Pamiętaj o proporcjach: pierwszeństwo mają algorytmy wymienione w podstawie programowej, a grafy są uzupełnieniem.

Powiązane tematy

Te działy łączą się z tematem „Grafy i drzewa” – przećwicz je w Quizie.