Nauka / Struktury danych, drzewa i grafy

Struktury danych, drzewa i grafy

Tablice, listy, stos, kolejka, drzewa, grafy; reprezentacja hierarchii przez tablicę przełożonych.

Rozszerzony

Teoria, wzory i przykłady

Podstawowe struktury

  • stos (LIFO) — push/pop, np. nawiasowanie, rekurencja,
  • kolejka (FIFO) — enqueue/dequeue, np. BFS,
  • lista, tablica, słownik (mapa) — dostęp po kluczu w średnim O(1)O(1).

Drzewa

Drzewo ukorzenione: każdy wierzchołek poza korzeniem ma dokładnie jednego rodzica. Hierarchię (np. korporacja) zapisujemy jako tablicę rodziców: rodzic[i] = numer bezpośredniego przełożonego pracownika i.

Typowe obliczenia na tablicy rodziców:

  • liczba bezpośrednich podwładnych pracownika x = ile razy x występuje w tablicy rodziców,
  • pracownicy niebędący przełożonymi to liście = numery, które nie występują w tablicy rodziców,
  • liczba przełożonych pracownika (głębokość w drzewie): gl[i]=gl[rodzic[i]]+1\text{gl}[i]=\text{gl}[\text{rodzic}[i]]+1 — jeśli rodzic zawsze ma mniejszy numer, wystarcza jeden przebieg od i=2i=2 w górę,
  • wszyscy podwładni — suma po poddrzewie (przebieg od końca: dodajemy rozmiar dziecka do rodzica).

Przykładowa korporacja z 8 pracownikami: pracownik 2 ma 3 bezpośrednich podwładnych (3, 5, 6) i 4 wszystkich (dodatkowo 7).

Grafy

Graf = wierzchołki + krawędzie. Reprezentacja: macierz sąsiedztwa lub listy sąsiedztwa. Przeszukiwanie DFS (stos/rekurencja) i BFS (kolejka) w O(V+E)O(V+E); BFS znajduje najkrótsze ścieżki w grafie nieważonym.

Łatwe zadania

Średnie zadania

Trudne zadania

Gotowy na sprawdzian z działu?
Wygeneruj krótki test z tego działu w generatorze.
Test działowy