Besökta
I kön
Kontrollerade kanter

  • Aktuell
  • I kön
  • Besökta
  • Väg
Ett klick på en nod väljer

Mer om bredden-först-sökning

Bredden-först-sökning (BFS)

Bredden-först-sökning utforskar en graf i ringar: först varje nod bredvid starten, sedan varje nod två kanter bort, och så vidare. Den gör det med en kö: först in, först ut. Klicka på en nod för att börja där, välj ett mål om du vill, och stega genom sökningen för att se kön växa och krympa, varje nod få sitt avstånd och en kortaste väg dyka upp. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Klicka på en nod för att göra den till start; byt klicket till Mål och klicka på en annan nod för att söka en kortaste väg dit. Talet på varje nod är dess avstånd från starten, och raden under grafen är kön. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Klicka på en nod för att göra den till start. Vill du söka en väg, byt klicket till Mål och klicka på en annan nod.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst i sökningen.
  3. Följ kön under grafen och avståndet på varje nod. Ny graf skapar en annan graf att prova.

Så fungerar bredden-först-sökning

Lägg startnoden i en kö med avstånd 0. Upprepa sedan: ta noden längst fram i kön och titta på var och en av dess grannar. En granne som inte har setts än får ett avstånd som är ett högre än noden du tog, minns den noden som vägen den nåddes från och ställer sig längst bak i kön. Grannar som redan setts hoppas över. När kön är tom har varje nod som går att nå sitt avstånd.

Varför den hittar kortaste vägar

Kön lämnar ut noder i den ordning de hittades, och noderna hittas ring för ring: alla noder på avstånd 1 köas före någon på avstånd 2, och så vidare. Första gången en nod nås, nås den alltså via en väg med så få kanter som möjligt. Följer man de sparade noderna bakåt från målet till starten får man den vägen. Det här räknar bara kanter; när kanterna har olika längd behövs Dijkstras algoritm.

Ofta ställda frågor

Vad är bredden-först-sökning?

Ett sätt att utforska en graf från en startnod genom att först besöka alla dess grannar, sedan deras grannar, och så vidare, ring för ring. En kö håller noderna i den ordning de hittades.

Hittar bredden-först-sökning den kortaste vägen?

Ja, när varje kant räknas lika: första gången BFS når en nod har den använt så få kanter som möjligt. Har kanterna olika längd, använd Dijkstras algoritm i stället.

Vad är skillnaden mellan BFS och DFS?

Bredden-först-sökning använder en kö och sprider sig jämnt, ring för ring. Djupet-först-sökning använder en stack (eller rekursion) och följer en väg så djupt det går innan den backar. BFS hittar kortaste vägar räknat i kanter; det gör inte DFS, men den är praktisk för att hitta cykler och för topologisk sortering.

Hur snabb är bredden-först-sökning?

Den tar ut varje nod ur kön en gång och tittar på varje kant från båda ändarna, så arbetet växer med antalet noder plus antalet kanter.

Skickas min graf någonstans?

Nej. Grafen skapas och genomsöks i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor