Informatică Programare
Algoritmi de parcurgere grafuri C++
Algoritmii de parcurgere grafuri în C++ vizitează nodurile într-o anumită ordine, folosind structuri de date ca cozi sau stive. Principalii algoritmi sunt BFS (parcurgere în lățime) și DFS (parcurgere în adâncime). Exemplu: BFS folosește o coadă și explorează vecinii nivel cu nivel, iar DFS folosește recursivitate sau o stivă.
BFS (Breadth-First Search)
- 1 Pasul 1: Inițializare Reprezentați graful cu liste de adiacență (vector<vector<int>>). Creați o coadă queue<int> și un vector visited pentru a marca nodurile vizitate.
- 2 Pasul 2: Parcurgere Adăugați nodul de start în coadă și marcați-l visited. Cât timp coada nu e goală, extrageți front, procesați nodul, și adăugați vecinii nevizitați în coadă.
- 3 Pasul 3: Exemplu numeric Pentru un graf cu nodurile 0-1-2 conectate, start la 0: coada devine [0], apoi [1,2], afișând ordinea 0,1,2. Complexitate O(V+E).
DFS (Depth-First Search)
- Implementare recursivă Definiți o funcție dfs(int nod) care marchează nodul visited și apelează recursiv pentru fiecare vecin nevizitat. Exemplu: dfs(0) pentru graful anterior afișează 0,1,2 sau altă ordine în adâncime.
- Implementare iterativă cu stivă Folosiți stack<int>. Puneți nodul de start pe stivă. Cât timp stiva nu e goală, extrageți top, procesați, și adăugați vecinii nevizitați. Asigură o parcurgere similară.
- Aplicații BFS e util pentru drumuri minime în grafuri neponderate, DFS pentru detectare cicluri sau sortare topologică. Ambele necesită memorie O(V).
Alege BFS pentru căutare în lățime și DFS pentru explorare în adâncime, testând pe grafuri mici pentru înțelegere.