Informatică Algoritmi
Grafuri bac informatica
Grafurile la bacalaureatul la informatică sunt structuri matematice formate din noduri și muchii, folosite pentru a modela relații între obiecte. Se reprezintă de obicei cu matrice de adiacență sau liste de adiacență.
Tipuri de grafuri
- Neorientat Muchiile nu au direcție; dacă există muchia (A,B), se poate merge de la A la B și invers.
- Orientat Muchiile au direcție; muchia (A,B) permite doar deplasarea de la A la B.
- Ponderat Fiecărei muchii i se atribuie o valoare (cost sau distanță).
Algoritmi comuni
- Parcurgere în lățime (BFS) Explorează nodurile nivel cu nivel, folosind o coadă; util pentru găsirea drumului minim în grafuri neponderate.
- Parcurgere în adâncime (DFS) Explorează cât mai departe pe o ramură înainte de a reveni, folosind recursivitate sau stivă.
- Dijkstra Găsește drumul de cost minim de la un nod sursă la toate celelalte, pentru grafuri ponderate cu costuri nenegative.
Învață reprezentările grafurilor și exersează algoritmii cu exemple practice pentru bac.