Informatică Algoritmi
Grafuri in informatica bacalaureat
Grafurile sunt structuri matematice formate din noduri și muchii, utilizate în informatică pentru modelarea relațiilor. La bacalaureat, acestea apar în probleme de parcurgere, drumuri minime sau conexitate. Sunt esențiale pentru înțelegerea algoritmilor de rețea.
Definiții de bază
- Noduri și muchii Nodurile sunt puncte care reprezintă entități, iar muchiile sunt legături între ele. Ex: într-o rețea socială, nodurile sunt persoane, muchiile sunt prietenii.
- Graf orientat vs. neorientat Într-un graf neorientat, muchiile nu au direcție. Într-un graf orientat, muchiile sunt săgeți cu direcție specifică.
- Gradul unui nod Numărul de muchii incidente cu un nod. Pentru grafuri orientate, se distinge gradul interior și exterior.
Algoritmi comuni la bacalaureat
- 1 Parcurgerea în lățime (BFS) Explorează nodurile nivel cu nivel, începând de la un nod sursă. Folosește o coadă.
- 2 Parcurgerea în adâncime (DFS) Explorează cât mai departe pe o ramură înainte de a reveni. Folosește o stivă sau recursivitate.
- 3 Algoritmul lui Dijkstra Găsește drumurile minime de la un nod sursă la toate celelalte, pentru grafuri cu costuri nenegative.
Exersează probleme cu grafuri din subiecte vechi de bacalaureat pentru a înțelege aplicațiile practice.