Informatică Programare
Algoritmi grafuri C++
Algoritmii pentru grafuri în C++ rezolvă probleme de parcurgere, drumuri minime sau conexitate. Grafurile sunt reprezentate cu liste de adiacență sau matrice de adiacență. Exemple comune includ BFS și Dijkstra.
Reprezentări graf
- Matrice de adiacență int adj[100][100]; pentru grafuri dense, O(n²) spațiu.
- Liste de adiacență vector<int> adj[100]; pentru grafuri rare, O(n+m) spațiu.
- Exemplu numeric Pentru 3 noduri cu muchii (1,2) și (2,3): adj[1]={2}, adj[2]={1,3}.
Algoritmi esențiali
- 1 Pas 1: BFS Parcurgere în lățime pentru drumuri minime în grafuri neponderate.
- 2 Pas 2: DFS Parcurgere în adâncime pentru detectare componente conexe.
- 3 Pas 3: Dijkstra Algoritm pentru drumuri minime în grafuri ponderate cu costuri pozitive.
Alege reprezentarea în funcție de densitatea grafului, exersează BFS pe probleme practice.