Czego się nauczysz
Nauczysz się przeszukiwać graf wszerz, warstwa po warstwie, i liczyć tak najkrótszą drogę w grafie i na planszy z murami.
Po co ci to na maturze
Pytania o najkrótszą drogę w labiryncie, najmniejszą liczbę przesiadek albo znajomych znajomych sprowadzają się do przeszukiwania grafu warstwa po warstwie.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Wszerz, warstwa po warstwieNajpierw wszyscy sąsiedzi, potem sąsiedzi sąsiadów. Pilnuje tego kolejka.
- 1.2Najkrótsza drogaWarstwa to liczba krawędzi od startu. Poprzednicy pozwalają odtworzyć samą drogę.
- 1.3Przeszukiwanie wszerz na planszyPole to wierzchołek, sąsiedzi to wolne pola w czterech kierunkach.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.