MOKIP 19.10.2011
  1. Rozwiązanie zadania domowego - Aquapark z finału III OIG (kod: aqu.cpp)
  2. Wprowadzenie do grafów
  3. Algorytm BFS
    • implementacja
    • wykorzystanie do liczenia najkrótszej ścieżki z jednego wierzchołka do pozostałych wierzchołków
  4. Algorytm DFS
    • implementacja
    • badanie spójności grafu, wyznaczanie spójnych składowych
  5. Drzewo przeszukiwań DFS
    • numeracja pre- i post-order
    • liczenie wielkości poddrzewa
    • zapytania "czy i jest przodkiem j"
  6. Zadanka: