Informatică Algoritmi
Probleme de informatica cu grafuri simple
Problemele cu grafuri în informatică implică structuri de noduri și muchii pentru a modela relații. Ele sunt frecvente în concursuri și aplicații reale, cum ar fi rețele sociale sau rute. Două probleme simple sunt parcurgerea în lățime (BFS) și găsirea drumului minim.
Parcurgerea în lățime (BFS)
- 1 Pasul 1 Pornești de la un nod sursă și îl vizitezi, apoi adaugi vecinii săi nevizitați într-o coadă.
- 2 Pasul 2 Extragi nodul din coadă, vizitezi vecinii săi nevizitați și îi adaugi în coadă. Repeti până când coada e goală.
- 3 Exemplu numeric Pentru un graf cu nodurile 1-2-3 (1 conectat la 2 și 3), BFS de la 1: vizitează 1, apoi 2, apoi 3.
Drumul minim între două noduri
- 1 Pasul 1 Folosești BFS pentru grafuri neponderate: fiecare muchie are costul 1. BFS găsește drumul cu cele mai puține muchii.
- 2 Pasul 2 Pentru grafuri ponderate, algoritmul lui Dijkstra calculează costul minim folosind o coadă de priorități.
- 3 Exemplu numeric Într-un graf cu nodurile A-B-C (A-B cost 1, B-C cost 2), drumul minim de la A la C are costul 3 (A→B→C).
Începe cu grafuri mici și desenează nodurile pentru a vizualiza pașii algoritmilor.