Breedte-eerst zoeken

De breedte traversal algoritme maakt de route van een grafiek op een iteratieve wijze met een wachtrij. Het kan bijvoorbeeld worden gebruikt voor de verbinding van een grafiek te bepalen.

Principe

Dit algoritme verschilt van de diepe traversal algoritme dat, van een top S, voor het eerst een lijst van de S buren vervolgens verkennen op een rijtje. Deze manier van werken maakt dus een wachtrij waar hij neemt de eerste top en laatst nog niet verkend zijn buren.

Wanneer het algoritme wordt toegepast op een grafiek, de hoekpunten reeds bezocht worden gemerkt om te voorkomen dat dezelfde vertex wordt meerdere malen onderzocht. In het bijzondere geval van een boom, is het niet nodig.

Stappen van het algoritme:

  • Doe de start knooppunt in de rij.
  • Verwijder de voorkant van de wachtrij knooppunt voor onderzoek.
  • Doe alle onderzochte buren in de wachtrij.
  • Als de wachtrij niet leeg terug naar stap 2.

Opmerking: het gebruik van een stapel in plaats van een wachtrij zetten dit algoritme in een diepte-eerst traversal algoritme.

Voorbeeld

Op de volgende grafiek, dit algoritme werkt dan als volgt:

Het onderzoekt de pieken in de volgorde A, B, C, E, D, F, G, anders dan de diepe traversal algoritme dat strekt in deze volgorde: A, B, D, F, C, G, E .

Pseudo-code

Ingewikkeldheid

De complexiteit van de tijd in het slechtste geval is de orde van E + V sinds elke rand en elk hoekpunt kan worden bezocht.

Toepassingen

Het pad breedte verkent alle hoekpunten bereikbaar vanaf de eerste hoekpunt. Het berekent de aangesloten componenten van de grafiek met lineaire complexiteit.

Verder werd in deze natuurlijk de pieken worden onderzocht door toenemende afstand tot de top. Dankzij deze eigenschap kunnen we het algoritme de eenvoudigste pad lossen: bereken de kortste weg tussen twee hoekpunten in een grafiek ongewogen.