< visszalépésSzélességi bejárás

Elmélet

A szélességi bejárás stratégiája

Egy tetszőleges összefüggő gráf összes csúcspontját bejárjuk egy start csúcsból. Először végigmegyünk a start csúcs összes szomszédján, majd ezeknek is bejárjuk az összes szomszédját. A kezdőcsúcstól távolodva a távolság növekvő sorrendjében járjuk be a csúcsokat. Addig fut az algoritmus, amíg a gráf összes csúcsát be nem jártuk.

A szélességi bejárás algoritmusa

A szélességi bejárás algoritmusa megadja a gráf csúcsait a kezdőcsúcstól való távolságuk növekvő sorrendjében, meghatározza a gráfhoz tartozó legrövidebb elérési utakat mutató feszítőfát. Ezt a 8. ábrán kék színű élek jelölik.

Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései Mélységi bejárás végrehajtásának lépései

A távolság szerinti elérés biztosításához egy sor adatszerkezetet fogunk használni.

Szélességi bejárás struktogramja
Szélességi bejárás struktogramja

  • Q: Ebben a sorban tároljuk az algoritmus által felfedezett, de be nem bejárt csúcsokat.
  • ECsúcsok: Ebben a halmazban tároljok azokat a csúcsokat, amelyeket már bejártunk.
  • ∀ v ∈ Szomszéd(u): A ciklus végig iterál v csúcs összes szomszédján.
  • ¬Eleme-e(ECsúcsok, u): Akkor igaz, ha az adott v csúcs nincs benne ECsúcsok halmazban, különben hamis.
  • Hba(ECsúcsok, u): A metódus megegyezik a Halmaz-ba(ECsúcsok, 𝑣) metódussal. A v csúcs bekerül az ECsúcsok halmazba.

Az alkalmazás nem indult el, mert a böngészője nem támogatja Java NPAPI technológiáját!

Az alkalmazás asztali verzióját a letöltés gombra kattintva érheti el!

letöltés
Letöltés