Summary of Sor (queue)
Sor (Queue) Adatszerkezet: Teljes Útmutató Diákoknak
Gráfalgoritmusok: Szélességi Bejárás (BFS)
Üdvözöllek! Ebben a tananyagban a gráfalgoritmusok egy alapvető és rendkívül hasznos módszerét, a szélességi bejárást (Breadth-First Search, BFS) fogjuk megismerni. Képzeld el, hogy egy térképen a legrövidebb utat keresed két pont között, vagy egy közösségi hálón felkutatod az összes ismerősöd ismerősét. Ezekben az esetekben a BFS segíthet! Bár a téma elsőre bonyolultnak tűnhet, lépésről lépésre haladva megérted majd a működését és a benne rejlő lehetőségeket.
Mi az a Gráf?
Először is tisztázzuk, mi is az a gráf, hiszen enélkül nem érthetjük a gráfalgoritmusokat.
A gráf egy matematikai struktúra, amely objektumok közötti páros kapcsolatokat modellez. Egy gráfnak két fő alkotóeleme van: a csúcsok (nodes vagy vertices) és az élek (edges). Az élek kötik össze a csúcsokat.
Képzelj el egy várost (csúcsok) és az őket összekötő utakat (élek). Ez egy egyszerű gráf.
A Szélességi Bejárás (BFS) Alapjai
A BFS egy algoritmus, amelyet gráfok bejárására, vagyis a csúcsok és élek szisztematikus felkeresésére használnak. A lényege, hogy egy kiinduló csúcsból indulva rétegenként halad kifelé, mint a vízbe dobott kő hullámai. Először az összes közvetlen szomszédját vizsgálja meg, majd azok szomszédjait, és így tovább.
Hogyan működik a BFS?
A BFS algoritmus egy sort használ a működése során. Ennek a sornak a segítségével tartja nyilván, hogy mely csúcsokat kell még meglátogatnia. Lássuk a lépéseket:
- Indulás: Válasszunk ki egy tetszőleges kiinduló csúcsot. Jelöljük meg, mint látogatottat, és tegyük be a sorba.
- Feldolgozás: Amíg a sor nem üres:
- Vegyünk ki egy csúcsot a sor elejéről.
- Vizsgáljuk meg az összes még nem látogatott szomszédját.
- Minden ilyen szomszédot jelöljünk meg látogatottként, és tegyük be a sor végére.
- Befejezés: Amikor a sor kiürül, az algoritmus befejeződik. Ekkorra az összes elérhető csúcsot meglátogattuk.
Példa a BFS működésére
Képzeljünk el egy egyszerű gráfot a következő csúcsokkal és élekkel:
- Csúcsok: $A, B, C, D, E, F$
- Élek: $(A, B), (A, C), (B, D), (C, E), (D, F)$
Induljunk az $A$ csúcsból.
| Lépés | Sor állapota | Látogatott csúcsok | Megjegyzés |
|---|---|---|---|
| 1. | $[A]$ | $A$ | $A$ sorba kerül, látogatott. |
| 2. | $[B, C]$ | $A, B, C$ | $A$-t kivesszük. Szomszédai $B, C$. Őket sorba tesszük, látogatottá tesszük. |
| 3. | $[C, D]$ | $A, B, C, D$ | $B$-t kivesszük. Szomszédja $D$. $D$ sorba kerül, látogatottá tesszük. |
| 4. | $[D, E]$ | $A, B, C, D, E$ | $C$-t kivesszük. Szomszédja $E$. $E$ sorba kerül, látogatottá tesszük. |
| 5. | $[E, F]$ | $A, B, C, D, E, F$ | $D$-t kivesszük. Szomszédja $F$. $F$ sorba kerül, látogatottá tesszük. |
| 6. | $[F]$ | $A, B, C, D, E, F$ | $E$-t kivesszük. Nincs új, nem látogatott szomszédja. |
| 7. | $[]$ | $A, B, C, D, E, F$ | $F$-et kivesszük. Nincs új, nem látogatott szomszédja. A sor üres. |
Ahogy láthatjuk, az algoritmus az $A$ csúcsból kiindulva rétegenként haladt: először az első szinten lévő $B, C$ csúcsokat, majd a második szinten lévő $D, E$ csúcsokat, végül a harmadik szinten lévő $F$ csúcsot látogatta meg.
BFS alkalmazási területei
A BFS rendkívül sokoldalú algoritmus, és számos gyakorlati problémában felhasználható:
- Rövidtávú útvonalak keresése súlyozatlan gráfokban: Ahogy említettük, a BFS az optimális választás, ha a minimális számú éllel akarunk eljutni egy pontból egy másikba. Például, a legkevesebb átszállással történő utazás tömegközlekedésen.
- Elérhetőségi vizsgálat: Megállapítható vele, hogy
Sign up for the full summaryAlready have an account? Sign in
BFS Gráfbejárás
Klíčová slova: Sor adatszerkezet, Körkörös tömb, Gráfalgoritmusok
Klíčové pojmy: A BFS (szélességi bejárás) egy gráfalgoritmus csúcsok és élek szisztematikus bejárására., A BFS egy kiinduló csúcsból indulva rétegenként, távolság szerint növekvő sorrendben halad., Az algoritmushoz egy sort használunk a meglátogatandó csúcsok tárolására., Minden csúcsot csak egyszer látogatunk meg, és jelöljük, hogy már feldolgoztuk., Amikor egy csúcsot kiveszünk a sorból, annak még nem látogatott szomszédait tesszük be a sorba., A BFS garantálja a legrövidebb utat súlyozatlan gráfokban., Alkalmazható útvonalkeresésre, elérhetőségi vizsgálatokra és hálózatok elemzésére., A folyamat akkor ér véget, amikor a sor üres, és az összes elérhető csúcsot feldolgoztuk., A "hat lépés távolság" elmélet is BFS-sel modellezhető., A BFS alapvető eszköz a gráfelméleti problémák megoldásához.