Vodič · Algoritmi · Grafovi i stabla
Grafovi i stabla – vodič kroz lekcije
Graf je skup čvorova povezanih granama: mapa gradova, mreža računara, lavirint, raspored zadataka. Grafovi su najzastupljenija tema na okružnom i državnom takmičenju i na SIO.
Vodič ide od zapisivanja grafa i obilazaka BFS i DFS, preko stabala i DAG-ova, do najkraćih puteva, minimalnih stabala i naprednih algoritama. Svaka lekcija ima kompletne programe u C++-u i zadatke sa rešenjima.
- 7–8. razred i srednja škola
- C++
- Priprema za takmičenja
1 Osnove i pretrage
Pojmovi, zapisivanje grafa i dva osnovna obilaska – temelj svih ostalih algoritama.
Uvod u grafove
Čvorovi i grane, matrica i lista susedstva, matrica kao graf.
Otvori lekciju →BFS i DFS
Pretraga u širinu i dubinu, udaljenosti, komponente povezanosti.
Otvori lekciju →Zadatak: Broj ostrva
BFS u matrici, povezane oblasti.
Otvori lekciju →Zadatak: Najkraći put u lavirintu
BFS sa rekonstrukcijom puta.
Otvori lekciju →2 Stabla
Graf bez ciklusa: obilazak, podstabla, prečnik i binarna stabla.
3 Usmereni grafovi bez ciklusa (DAG)
Redosled zadataka sa zavisnostima i dinamičko programiranje po grafu.
4 Najkraći putevi
Kada grane imaju dužine: od jednog čvora i između svih parova.
5 Minimalna razapinjuća stabla
Najjeftinije povezivanje svih čvorova.
6 Napredne teme
Za državno takmičenje i SIO.
Predloženi redosled
- Uvod u grafove
- BFS i DFS
- Zadatak: Broj ostrva
- Zadatak: Najkraći put u lavirintu
- Stabla
- Binarna stabla i BST
- Topološko sortiranje
- Otkrivanje ciklusa
- Najduži put u DAG-u
- DP na DAG-u
- Dijkstrin algoritam
- Bellman-Ford i Floyd-Warshall
- Primov algoritam
- Kruskalov algoritam
- Eulerovi putevi
- Mostovi i artikulacioni čvorovi
- Komponente jake povezanosti
Korisni spoljni resursi
- CSES Problem Set – odeljci „Graph Algorithms“ i „Tree Algorithms“
- VisuAlgo – Graph Traversal – animacije BFS, DFS, Dijkstre, MST algoritama
- USACO Guide – plan učenja grafova po nivoima (engleski)
- Petlja – zadaci na srpskom sa automatskom proverom
Mapa učenja — Grafovi i stabla
Ova stranica predstavlja put kroz lekcije o grafovima i stablima za pripremu
za takmičenja iz informatike (SIO, okružno, državno).
Izaberi smer koji ti odgovara ili prati putanju od početka do kraja.
□ Osnove i pretrage
- Grafovi — BFS i DFS (osnove)
- Topološko sortiranje
- Otkrivanje ciklusa u usmerenim grafovima
- Najduži put u DAG-u (DP + topološki poredak)
- Zadatak: Broj ostrva (BFS u matrici)
- Zadatak: Najkraći put u lavirintu (BFS)
↔️ Najkraći putevi (Shortest Paths)
- Dijkstra — najkraći put u grafu
- Bellman-Ford i Floyd-Warshall
- Red sa prioritetom (priority_queue) – potreban za Dijkstru
- Najkraći/ najduži / broj putanja u DAG-u
Preporuka redosleda: Dijkstra → Bellman-Ford → Floyd-Warshall → DAG primene
□ Napredne tehnike (za više nivoe takmičenja)
- Eulerovi putevi i ciklusi
- Mostovi i artikulisani čvorovi (Tarjan)
- SCC — Komponente jake povezanosti
- DP na DAG-ovima — primene i takmičarska rešenja
⭐ Ove lekcije su preporuka za pripreme za: okružno, državno, SIO.
□ Predložen redosled za 8. razred → SIO
- BFS i DFS
- Topološko sortiranje
- Dijkstra
- Bellman-Ford / Floyd-Warshall
- Prim + Kruskal (MST)
- Najduži put u DAG / DP tehnike
- Eulerovi putevi
- Mostovi i artikulacije
- SCC (Kosaraju / Tarjan)
□ Učenik može da se vraća i vodi svojim tempom.