Informatică Algoritmi
Algoritmi de cautare in grafuri
Algoritmii de căutare în grafuri sunt metode pentru a explora nodurile și muchiile în scopul găsirii unui nod specific sau a verificării proprietăților. Cei mai utilizați sunt parcurgerea în lățime (BFS) și parcurgerea în adâncime (DFS). Aceștia stau la baza multor aplicații, de la rețele sociale la sisteme de navigație.
Parcurgerea în lățime (BFS)
- 1 Principiu Explorează toți vecinii unui nod înainte de a trece la următorul nivel. Folosește o coadă pentru a menține ordinea.
- 2 Pași algoritmici 1. Începe de la un nod sursă, marchează-l vizitat, adaugă-l în coadă. 2. Extrage primul nod din coadă, vizitează toți vecinii nevizitați, adaugă-i în coadă. 3. Repetă până când coada este goală.
- 3 Aplicație Găsește drumul cel mai scurt în grafuri neponderate. Ex: găsirea distanței minime între orașe.
Parcurgerea în adâncime (DFS)
- 1 Principiu Explorează cât mai departe de-a lungul unei ramuri înainte de a reveni. Folosește o stivă sau recursivitate.
- 2 Pași algoritmici 1. Începe de la un nod, marchează-l vizitat. 2. Pentru fiecare vecin nevizitat, apelează recursiv DFS. 3. Revine când nu mai există vecini nevizitați.
- 3 Aplicație Detectează cicluri în grafuri sau explorează toate posibilitățile. Ex: rezolvarea labirinturilor.
Comparație și utilizare
- Complexitate Ambele au complexitate O(V+E), unde V este numărul de noduri, E numărul de muchii.
- Alegerea algoritmului Folosește BFS pentru drumuri minime, DFS pentru explorare completă sau detectare de cicluri.
- Exemplu practic Într-o rețea de prietenii, BFS găsește cea mai scurtă lanț de cunoștințe, DFS explorează toate conexiunile unei persoane.
Implementează ambii algoritmi în pseudocod sau un limbaj de programare pentru a înțelege diferențele.