Vizitate
În coadă
Muchii verificate

  • Curent
  • În coadă
  • Vizitate
  • Drum
Un clic pe un nod setează

Mai multe despre căutarea în lățime

Căutarea în lățime (BFS)

Căutarea în lățime explorează un graf în inele: mai întâi fiecare nod vecin cu startul, apoi fiecare nod aflat la două muchii distanță și așa mai departe. Face asta cu o coadă: primul intrat, primul ieșit. Faceți clic pe un nod pentru a porni de la el, alegeți o țintă dacă doriți și parcurgeți căutarea pas cu pas pentru a vedea cum crește și scade coada, cum își primește fiecare nod distanța și cum apare cel mai scurt drum. Apăsați Redare pentru a urmări căutarea sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Faceți clic pe un nod ca să devină start; comutați clicul pe Țintă și faceți clic pe alt nod pentru a căuta cel mai scurt drum până la el. Numărul de pe fiecare nod este distanța lui față de start, iar rândul de sub graf este coada. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Faceți clic pe un nod ca să devină start. Pentru a căuta un drum, comutați clicul pe Țintă și faceți clic pe alt nod.
  2. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde în căutare.
  3. Urmăriți coada de sub graf și distanța de pe fiecare nod. Graf nou creează alt graf de încercat.

Cum funcționează căutarea în lățime

Puneți nodul de start într-o coadă, cu distanța 0. Apoi repetați: luați nodul din fața cozii și examinați fiecare vecin al său. Un vecin care nu a fost încă văzut primește o distanță cu unu mai mare decât nodul luat, reține acel nod ca drumul prin care a fost atins și intră la capătul cozii. Vecinii văzuți deja sunt săriți. Când coada este goală, fiecare nod care poate fi atins are distanța sa.

De ce găsește cele mai scurte drumuri

Coada dă nodurile în ordinea în care au fost găsite, iar nodurile sunt găsite inel cu inel: toate nodurile la distanța 1 intră în coadă înaintea oricărui nod la distanța 2 și așa mai departe. Așadar, prima dată când un nod este atins, e atins pe un drum cu cel mai mic număr posibil de muchii. Urmând nodurile reținute înapoi, de la țintă la start, se obține acel drum. Se numără doar muchiile; când muchiile au lungimi diferite, e nevoie de algoritmul lui Dijkstra.

Întrebări frecvente

Ce este căutarea în lățime?

Un mod de a explora un graf pornind de la un nod de start: se vizitează mai întâi toți vecinii lui, apoi vecinii acestora și așa mai departe, inel cu inel. O coadă păstrează nodurile în ordinea în care au fost găsite.

Găsește căutarea în lățime cel mai scurt drum?

Da, când toate muchiile contează la fel: prima dată când BFS atinge un nod, a folosit cel mai mic număr posibil de muchii. Pentru muchii cu lungimi diferite, folosiți în schimb algoritmul lui Dijkstra.

Care este diferența dintre BFS și DFS?

Căutarea în lățime folosește o coadă și se extinde uniform, inel cu inel. Căutarea în adâncime folosește o stivă (sau recursivitate) și urmează un drum cât de adânc se poate înainte de a se întoarce. BFS găsește cele mai scurte drumuri în muchii; DFS nu, dar este utilă pentru găsirea ciclurilor și pentru sortarea topologică.

Cât de rapidă este căutarea în lățime?

Scoate fiecare nod din coadă o singură dată și examinează fiecare muchie de la ambele capete, deci munca crește cu numărul de noduri plus numărul de muchii.

Este graful meu trimis undeva?

Nu. Graful este creat și parcurs în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor