Grafikon bejárása
A grafikon bejárása azt jelenti, hogy minden csúcsot és élt pontosan egyszer kell meglátogatni egy kútban -definiált sorrend. Bizonyos gráfalgoritmusok használatakor meg kell győződnie arról, hogy a gráf minden csúcsát pontosan egyszer keresi fel. A csúcsok meglátogatásának sorrendje fontos, és függhet a megoldott algoritmustól vagy kérdéstől.
Egy bejárás során fontos, hogy kövesse nyomon, melyik csúcsot kereste fel. A csúcsok követésének legelterjedtebb módja azok megjelölése.
Breadth First Search (BFS)
A grafikonok áthaladásának számos módja van. A BFS a leggyakrabban alkalmazott megközelítés.
A BFS egy bejáró algoritmus, ahol el kell kezdenie a bejárást egy kiválasztott csomópontból (forrás vagy kezdő csomópont), és a grafikont rétegenként át kell haladnia, feltárva ezzel a szomszédos csomópontokat (csomópontokat, amelyek közvetlenül kapcsolódnak a forrás csomópontokhoz). Ezután a következő szintű szomszéd csomópontok felé kell haladnia.
Ahogy a BFS név is sugallja, a grafikont szélesen kell haladnia az alábbiak szerint:
- először vízszintesen és látogassa meg az aktuális réteg összes csomópontját
- Ugrás a következő rétegre
Vegye figyelembe a következő ábrát. 
Az 1. réteg csomópontjai közötti távolság viszonylag kisebb, mint a 2. réteg csomópontjai közötti távolság. Ezért a BFS-ben meg kell haladnia az 1. réteg összes csomópontját, mielőtt áttérne a 2. réteg csomópontjaira.
Gyermekcsomópontok bejárása
A grafikon ciklusokat tartalmazhat, amelyek a grafikon áthaladása közben ismét ugyanahhoz a csomóponthoz vezethetnek. Az ugyanazon csomópont újbóli feldolgozásának elkerülése érdekében használjon egy logikai tömböt, amely a csomópontot a feldolgozás után megjelöli. Miközben meglátogatja a csomópontokat a grafikon rétegében, tárolja azokat úgy, hogy hasonló sorrendben haladjon át a megfelelő gyermek csomópontokon.
A folyamat megkönnyítése érdekében használjon egy várólistát a csomópont tárolásához, és jelölje meg “meglátogatottként”, amíg az összes szomszédja (közvetlenül hozzá kapcsolódó csúcs) meg nem jelenik. A sor a First In First Out (FIFO) várakozási módot követi, ezért a csomópont szomszédait abban a sorrendben keressük fel, ahogyan a csomópontba beillesztették őket, vagyis először azt a csomópontot látogatják meg, amelyet először beszúrtak, és így tovább.
Pszeudokód
Utazási folyamat 
A bejárás a forráscsomóponttól indul, és az s-t nyomja a sorban. s “látogatottként” lesz jelölve.
Első iteráció
- s a sorból kerül ki
- s azaz az 1. és 2. szomszédjait bejárják
- Az 1. és a 2., amelyeket korábban nem tettek meg, áthaladnak. Ezek a következők lesznek:
- a várólistába tolva
- az 1. és a 2. helyet meglátogatottként megjelölik
Második iteráció
- 1 kiugrik a sorból
- 1 azaz 3 és 3 szomszédok bejárják
- s figyelmen kívül hagyják, mert “meglátogatottként” jelölik
- 3, amelyet korábban még nem tettek meg, átjárják. Ez:
- a sorba tolva
- meglátogatottként megjelölt
harmadik iteráció
- 2 kiugrik a sorból
- 2, azaz s, 3 és 4 szomszédjait bejárják
- 3 és s figyelmen kívül hagyják, mert “meglátogatottként” vannak megjelölve
- A 4-et, amelyet korábban nem tettek meg, bejárják. Ez:
- a sorba tolva
- meglátogatottként megjelölt
negyedik iteráció
- 3 kiugrik a sorból
- A 3, azaz 1, 2 és 5 szomszédok áthaladnak
- Az 1 és 2 figyelmen kívül maradnak, mert “meglátogatottként” vannak megjelölve
- Az 5, amelyet korábban nem tettek meg, bejárják. Ez:
- a sorba tolva
- Meglátogatottként megjelölt
Ötödik ismétlés
- 4 kerül ki a sorból
- 4-es, azaz 2-es szomszédok áthaladnak
- A 2-t figyelmen kívül hagyják, mert azt már “meglátogatottként” jelölik
Hatodik iteráció
- 5 kiugrik a sorból
- 5, azaz 3 szomszédja áthalad
- 3 figyelmen kívül hagyja, mert már “meglátogatottként” megjelölt
A sor üres, és kijön a hurokból. Az összes csomópontot bejárta a BFS használatával.
Ha a grafikon összes éle azonos súlyú, akkor a BFS segítségével meg lehet találni a csomópontok közötti minimális távolságot is egy grafikonon.
Példa
Ahogy ebben a diagramban is, kezdje a forrás csomópontját, hogy megtalálja a forrás közötti távolságot csomópont és 1. csomópont. Ha nem követi a BFS algoritmust, akkor a forrás csomópontról a 2. csomópontra, majd az 1. csomópontra léphet. Ez a megközelítés kiszámítja a forrás csomópont és az 1. csomópont közötti távolságot 2-ként, míg a minimum a távolság valójában 1. A minimális távolság helyesen kiszámítható a BFS algoritmus használatával.
Komplexitás
A BFS időbeli összetettsége O (V + E), ahol V a csomópontok száma és E az élek száma.
Alkalmazások
1. Hogyan lehet meghatározni az egyes fák egyes csomópontjainak szintjét?
Amint a BFS-ben tudod, bölcsen haladsz. A BFS segítségével meghatározhatja az egyes csomópontok szintjét is.
Megvalósítás
Ez a kód hasonló a BFS-kódhoz, csak a következő különbséggel:
szint] = szint + 1;
Ebben a kódban az egyes csomópontok meglátogatása közben a csomópont szintjét a szülőcsomópont szintjének növekedésével állítják be. Így határozzák meg az egyes csomópontok szintjét.
2 . 0-1 BFS
Ez a típusú BFS a grafikon két csomópontja közötti legrövidebb távolság megkeresésére szolgál, feltéve, hogy a grafikon éleinek súlya 0 vagy 1. Ha alkalmazza a ebben a cikkben hibás eredményt kap a 2 csomópont közötti optimális távolságról.
Ebben a megközelítésben egy logikai tömböt nem használunk a csomópont megjelölésére, mert az optimális távolság állapotát ellenőrizzük, amikor látogasson el minden csomópontra. A csomópont tárolásához kettős végű sor kerül felhasználásra. 0-1 BFS-ben, ha az él súlya = 0, akkor a csomópont a dequeue elé tolódik. Ha az él súlya = 1, akkor a csomópont a dequeue hátuljára tolódik.
Megvalósítás
A Q kettős végű sor. A távolság egy tömb, ahol a távolság tartalmazza a kezdő csomópont és a v csomópont közötti távolságot. Kezdetben a forrás csomóponttól az egyes csomópontokig meghatározott távolság végtelen.
Értsük meg ezt a kódot a következő ábrával:
A grafikon szomszédsági listája a következő lesz:
Itt az “s” -et 0-nak vagy forráscsomópontnak tekintjük.
0 – > 1 – > 3 – > 2
élek.első = 1, élek.második = 1
élek.első = 3, élek.második = 0
élek.első = 2, élek.second = 1
1 – > 0 – > 4
edge.first = 0, élek.second = 1
élek.first = 4 , edge.second = 0
2 – > 0 – > 3
edge.first = 0 , élek.second = 0
élek.first = 3, élek.second = 0
3 – > 0 – > 2 – > 4
él.első = 0, élek.second = 0
élek.első = 2, élek.second = 0
élek.első = 4, élek.second = 0
4 – > 1 – > 3
élek.első = 1, élek.second = 0
élek.első = 3, edge.second = 0
Ha a BFS algoritmust használja, akkor az eredmény hibás lesz, mert megmutatja az optimális távolság s között és az 1., s és a 2. csomópont mint 1. Ennek oka az, hogy meglátogatja s gyermekeit, és kiszámolja s és gyermekei közötti távolságot, amely 1. A tényleges optimális távolság mindkét esetben 0.
Feldolgozás
A forrás csomóponttól kezdve, azaz 0-tól kezdve 1, 2 és 3 felé mozog. Mivel az él súlya 0 és 1, valamint 0 és 2 között 1, , 1 és 2 a sor hátsó részébe tolódik. Mivel azonban az él súlya 0 és 3 között 0, a 3 a sor elejére tolódik. A távolság ennek megfelelően a távolság tömbben marad.
Ezután a 3 kiugrik a sorból, és ugyanezt a folyamatot alkalmazzák a szomszédaira is, és így tovább.