Informatică Programare
Algoritmi pe grafuri C++
Algoritmii pe grafuri în C++ rezolvă probleme legate de structuri de date graf, cum ar fi găsirea drumurilor, componentele conexe sau arborele de acoperire minim, utilizând reprezentări precum liste de adiacență sau matrice de adiacență. Acești algoritmi sunt esențiali în domenii precum rețelele de calculatoare sau optimizarea rutelor.
Reprezentarea grafurilor în C++
- Matrice de adiacență O matrice bidimensională unde elementul [i][j] indică dacă există muchie între nodurile i și j. Exemplu: pentru un graf cu 3 noduri, matricea poate fi {{0,1,0},{1,0,1},{0,1,0}}.
- Liste de adiacență Un vector de liste sau liste înlănțuite, unde fiecare poziție i stochează nodurile adiacente lui i. Exemplu: vector<vector<int>> adj; adj[0] = {1}; adj[1] = {0,2};
- Alegerea reprezentării Matricea este rapidă pentru verificarea existenței muchiilor, dar consumă multă memorie; listele sunt eficiente pentru grafuri rare.
Algoritmi comuni pe grafuri
- 1 Pasul 1: Parcurgerea în lățime (BFS) Folosește o coadă pentru a explora nodurile nivel cu nivel. Exemplu: pentru a găsi drumul cel mai scurt într-un graf neponderat.
- 2 Pasul 2: Parcurgerea în adâncime (DFS) Folosește recursivitate sau o stivă pentru a explora cât mai adânc posibil înainte de a reveni. Exemplu: pentru a detecta cicluri sau componente conexe.
- 3 Pasul 3: Algoritmul lui Dijkstra Găsește drumurile cele mai scurte într-un graf cu ponderi nenegative, folosind o coadă de priorități. Exemplu: pentru rute într-o rețea de drumuri.
Exersează implementând BFS și DFS pe grafuri mici reprezentate cu liste de adiacență, apoi treci la algoritmi mai complecși ca Dijkstra.