Bevezetés a BFS algoritmusba
Az adatok hatékony elérése és kezelése érdekében azokat speciális formátumban lehet tárolni és megszervezni, az úgynevezett adatstruktúrát. Sok adatszerkezet létezik, mint például Verem, Tömb, Összekapcsolt Lista, Sorok, Fák és Grafikonok stb. Lineáris adatszerkezetekben, például Verem, Tömb, Összekapcsolt Lista és Sor, az adatok lineáris sorrendben vannak elrendezve, míg a nem lineáris adatszerkezetek, például a fák és a grafikonok, az adatok hierarchikusan vannak elrendezve, nem sorrendben. A grafikon nemlineáris adatszerkezet, amelynek csomópontjai és szélei vannak. A Grafikon csomópontjaira csúcsokként is hivatkozhatunk, amelyek száma véges, és az élek a két csomópont közötti összekötő vonalak.
A fenti grafikonon a csúcsok V = (A, B, C, D, E), az élek pedig
E = (AB, AC, CD, BE)
Mi a BFS algoritmus?
Általában két algoritmust használunk egy grafikon áthaladásához. Ezek BFS (szélesség első keresés) és DFS (mélység első keresés) algoritmusok. A grafikon keresztezése pontosan egyszer meglátogat minden csúcsot vagy csomópontot és élt, egy jól meghatározott sorrendben. Ezenkívül nagyon fontos nyomon követni a meglátogatott csúcsokat, hogy ugyanaz a csúcs ne kerüljön kétszer át. A Breath First Search algoritmusban az áthaladás egy kiválasztott csomóponttól vagy forráscsomóponttól indul, és az áthaladás a forráscsomóponthoz közvetlenül kapcsolódó csomópontokon keresztül folytatódik. Egyszerűbben fogalmazva: a BFS algoritmusban először vízszintesen kell mozgatni és át kell mozgatni az aktuális réteget, majd ezt követően a következő rétegre kell mozgatni.
Hogyan működik a BFS algoritmus?
Vegyük például az alábbi ábra.
A fontos feladat az, hogy megtaláljuk a legrövidebb utat egy gráfban, miközben áthaladunk a csomópontokon. Ha egy grafikonon haladunk keresztül, akkor a csúcs felfedezetlen állapotból felfedezett állapotba megy, és végül teljesen felfedezhetővé válik. Meg kell jegyezni, hogy egy bizonyos időben elakadhat, miközben áthalad egy grafikonon, és egy csomópont kétszer meglátogatható. Tehát alkalmazhatunk egy módszert a csomópontok megjelölésére, miután a felfedezetlenség állapotát teljesen felfedezésre változtatta meg.
Az alábbi képen láthatjuk, hogy a csomópontok meg lehet jelölni a grafikonokban, amikor azok feketével megjelölve teljesen felfedeződnek. A forrás csomóponttól kezdhetjük, és ahogy az áthaladás minden csomóponton halad tovább, meg lehet jelölni azonosításukra.
A mozgás egy csúcsról indul, majd a kimenő élek felé halad. Amikor egy él felfedezetlen csúcsra megy, akkor azt felfedezettként jelölik. De ha egy él egy teljesen felfedezett vagy felfedezett csúcshoz megy, akkor azt figyelmen kívül hagyják.
Egy irányított gráf esetén az egyes éleket egyszer meglátogatjuk, és az irányítatlan gráfok esetén kétszer, azaz egyszer meglátogatjuk az egyes csomópontok meglátogatásakor. Az alkalmazandó algoritmust a felfedezett csúcsok tárolásának módja alapján határozzuk meg. A BFS algoritmusban a várólistát kell használni, ahol először a legrégebbi csúcsot fedezik fel, majd a kiindulási csúcsról a rétegeken átterjednek.
A BFS algoritmushoz lépéseket hajtanak végre
Az alábbi lépéseket egy BFS algoritmussal hajtjuk végre.
- Egy adott gráfban kezdjük egy csúcsról, azaz a fenti diagramban ez a 0 csomópont. A szintet, amelyben ez a csúcs van jelen, 0 rétegként lehet megnevezni.
- A következő lépés az összes többi csúcs megtalálása, amelyek a kiindulási csúcshoz szomszédosak, azaz a 0 csomópont vagy közvetlenül elérhetők tőle. Ezután megjelölhetjük ezeket a szomszédos csúcsokat, hogy az 1. rétegben legyenek jelen.
- Ugyanazon csúcshoz érhetõ el a grafikon hurokja. Tehát csak azokra a csúcsokra kell utaznunk, amelyeknek ugyanabban a rétegben kell lennie.
- Ezután megjelöljük az aktuális csúcs szülőcsúcsát, amelyen vagyunk. Ugyanezt kell végrehajtani az 1. réteg minden csúcsán.
- Ezután a következő lépés az összes csúcs megtalálása, amelyek egy szélektől távol vannak az 1. rétegben lévő csúcsoktól. Ezek az új csúcsok a 2. rétegben találhatók.
- A fenti eljárást addig ismételjük, amíg az összes csomópont át nem halad.
Példa:
Vegyük például az alábbi ábra és megértsük, hogyan működik a BFS algoritmus. Általában egy BFS algoritmusban a csomópontok sorba állítását használják a csomópontok áthaladása közben.
A fenti grafikonban először meglátogatjuk a 0 csomópontot, és ezt a csomópontot az alábbi sorba helyezzük:
A 0 csomópont meglátogatása után a szomszédos 0, 1 és 2 csomópont sorba kerül. A sor a következőképpen ábrázolható: 
Ezután a sor első első csomópontját, amely 2-es, meglátogatjuk. A 2. csomópont meglátogatása után a sor az alábbiak szerint ábrázolható:
A 2. csomópont meglátogatása után az 5 sorba kerül, és mivel az 5. csomóponthoz nincsenek meglátogathatatlan szomszédos csomópontok, még akkor is, ha az 5 be van állítva a sorba, de kétszer nem látogatja meg.
Ezután a sor első csomópontja 1, amelyet meglátogatunk. A szomszédos 3 és 4 csomópontok sorba kerülnek. A sor bemutatása az alábbiak szerint történik
Ezután a sor első csomópontja 5, és ehhez a csomóponthoz nincs több meg nem látott szomszédos csomópont. Ugyanez vonatkozik a 3. és a 4. csomópontra, amelyekre nincsenek még nem látott szomszédos csomópontok.
Tehát az összes csomópont áthalad és végül a sor kiürül.
Következtetés
A szélesség-keresési algoritmusnak nagyszerű előnyei vannak annak ajánlására. A BFS algoritmus számos alkalmazásának egyike a legrövidebb út kiszámítása. Emellett a hálózatépítésben szomszédos csomópontok keresésére is felhasználható, és megtalálható a közösségi hálózati oldalakon, a hálózati sugárzáson és a szemétgyűjtésen. A felhasználóknak meg kell érteniük a követelményt és az adatmintát, hogy a jobb teljesítmény érdekében felhasználhassák.
Ajánlott cikkek
Ez egy útmutató a BFS algoritmushoz. Itt tárgyaljuk a BFS algoritmusban a teljesítmény fogalmát, működését, lépéseit és példáját. A további javasolt cikkeken keresztül további információkat is megtudhat -
- Mi az a kapzsi algoritmus?
- Ray Tracing algoritmus
- Digitális aláírás algoritmus
- Mi a Java Hibernate?
- Digitális aláírás titkosítás
- BFS VS DFS | A 6 legfontosabb különbség az infographicsnál