Besøgt
I køen
Undersøgte kanter

  • Aktuel
  • I køen
  • Besøgt
  • Vej
Et klik på en knude sætter

Mere om bredde-først-søgning

Bredde-først-søgning (BFS)

Bredde-først-søgning udforsker en graf i ringe: først hver knude ved siden af starten, så hver knude to kanter væk, og så videre. Det sker med en kø: først ind, først ud. Klik på en knude for at starte fra den, vælg et mål, hvis du vil, og gå søgningen igennem trin for trin. Så ser du køen vokse og skrumpe, hver knude få sin afstand og en korteste vej dukke op. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Klik på en knude for at gøre den til start; skift klikket til Mål, og klik på en anden knude for at søge efter en korteste vej dertil. Tallet på hver knude er dens afstand fra starten, og rækken under grafen er køen. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

Sådan virker det

  1. Klik på en knude for at gøre den til start. Vil du søge efter en vej, så skift klikket til Mål, og klik på en anden knude.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst i søgningen.
  3. Følg køen under grafen og afstanden på hver knude. Ny graf laver en anden graf, du kan prøve.

Sådan virker bredde-først-søgning

Sæt startknuden i en kø med afstand 0. Gentag så: tag knuden forrest i køen, og se på hver af dens naboer. En nabo, der ikke er set endnu, får en afstand, der er én højere end den knude, du tog, husker den knude som vejen, den blev nået ad, og stiller sig bagerst i køen. Naboer, der er set før, springes over. Når køen er tom, har hver knude, der kan nås, sin afstand.

Hvorfor den finder korteste veje

Køen giver knuderne ud i den rækkefølge, de blev fundet, og knuderne findes ring for ring: alle knuder med afstand 1 kommer i køen før nogen med afstand 2, og så videre. Første gang en knude nås, er det altså ad en vej med færrest mulige kanter. Følger man de huskede knuder tilbage fra målet til starten, får man den vej. Det tæller kun kanter; når kanterne har forskellig længde, skal man bruge Dijkstras algoritme.

Ofte stillede spørgsmål

Hvad er bredde-først-søgning?

En måde at udforske en graf fra en startknude på: først besøges alle dens naboer, så deres naboer, og så videre, ring for ring. En kø holder knuderne i den rækkefølge, de blev fundet.

Finder bredde-først-søgning den korteste vej?

Ja, når alle kanter tæller lige meget: første gang BFS når en knude, har den brugt færrest mulige kanter. Har kanterne forskellig længde, så brug Dijkstras algoritme i stedet.

Hvad er forskellen på BFS og DFS?

Bredde-først-søgning bruger en kø og breder sig jævnt ud, ring for ring. Dybde-først-søgning bruger en stak (eller rekursion) og følger én vej så dybt som muligt, før den går tilbage. BFS finder korteste veje målt i kanter; det gør DFS ikke, men den er nyttig til at finde kredse og til topologisk sortering.

Hvor hurtig er bredde-først-søgning?

Den tager hver knude ud af køen én gang og ser på hver kant fra begge ender, så arbejdet vokser med antallet af knuder plus antallet af kanter.

Bliver min graf sendt nogen steder hen?

Nej. Grafen laves og gennemsøges i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor