Informatică Algoritmi
Algoritmi grafuri bacalaureat informatica
Algoritmii pe grafuri pentru bacalaureat la informatică sunt metode de rezolvare a problemelor care implică noduri și muchii. Ei testează înțelegerea structurilor de date și a logicii de parcurgere. În examen, apar frecvent în subiecte care cer determinarea drumurilor sau a componentelor conexe.
Algoritmi esențiali de învățat
- Parcurgerea în lățime (BFS) Folosește o coadă pentru a explora nodurile pe niveluri, utilă pentru găsirea drumului minim într-un graf neponderat. Exemplu: de la nodul 1, vizitezi vecinii imediați, apoi vecinii acestora.
- Parcurgerea în adâncime (DFS) Folosește recursivitate sau stivă pentru a explora cât mai departe pe o ramură, bună pentru detectarea ciclurilor sau a componentelor conexe. Exemplu: mergi din nodul 1 până la un nod fără vecini nevizitați, apoi te întorci.
- Algoritmul lui Dijkstra Găsește drumul de cost minim de la un nod sursă la toate celelalte într-un graf cu ponderi nenegative. Folosește o coadă de priorități. Exemplu: pentru graf cu ponderi pe muchii, calculezi distanțele minime pas cu pas.
Exemplu de exercițiu rezolvat
- 1 Enunț Dat un graf neorientat cu 4 noduri (1,2,3,4) și muchiile (1,2), (2,3), (3,4). Determină dacă există drum de la nodul 1 la nodul 4 folosind BFS.
- 2 Rezolvare pas 1 Inițializezi o coadă cu nodul 1 și marchezi nodul 1 ca vizitat.
- 3 Rezolvare pas 2 Extragi nodul 1 din coadă, verifici vecinii: nodul 2. Adaugi nodul 2 în coadă și îl marchezi vizitat.
- 4 Rezolvare pas 3 Extragi nodul 2, verifici vecinii: nodul 3 (nodul 1 e deja vizitat). Adaugi nodul 3 în coadă.
- 5 Rezolvare pas 4 Extragi nodul 3, verifici vecinii: nodul 4. Găsești nodul 4, deci există drum. Rezultat: DA.
Exersează implementarea algoritmilor în cod (C++ sau Pascal) pentru a înțelege pașii și a evita erorile la examen.