Czego się nauczysz
Poznasz graf, czyli punkty połączone liniami, i dwa sposoby zapisania go w programie: macierz sąsiedztwa i listę sąsiedztwa.
Po co ci to na maturze
Plik z parami miast połączonych drogą albo osób, które się znają, to graf. Zanim program odpowie na pytanie o drogi czy znajomych, musi go zapisać tak, żeby szybko znajdować sąsiadów.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Wierzchołki i krawędziePunkty i połączenia między nimi. Stopień to liczba połączeń jednego punktu.
- 1.2Macierz sąsiedztwaTablica n na n: jedynka w M[a][b] znaczy, że a i b są połączone.
- 1.3Lista sąsiedztwaDla każdego wierzchołka lista jego sąsiadów. Tyle wpisów, ile końców krawędzi.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.