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

Smid en sten i en dam, og ringene breder sig jævnt ud. Bredde-først-søgning udforsker en graf på samme måde: først alt ét skridt fra starten, så alt to skridt væk, og så videre. Den enkle rækkefølge er grunden til, at den finder korteste veje.

En graf med knuder med bogstaver, farvet i ringe efter afstanden fra startknuden, med en kø af knuder tegnet nedenunder
En graf med knuder med bogstaver, farvet i ringe efter afstanden fra startknuden, med en kø af knuder tegnet nedenunder

Idéen

En graf er en mængde knuder forbundet af kanter: steder og veje, mennesker og venskaber, felter i en labyrint og åbningerne mellem dem. Bredde-først-søgning besvarer spørgsmålet: hvad kan jeg nå herfra, og i hvor få skridt? Den holder en kø af knuder, der endnu skal besøges. Når knuder tages forrest og nye sættes bagerst, behandles knuderne i den rækkefølge, de blev opdaget.

Trin for trin

Sæt starten i køen med afstand 0. Tag knuden forrest. For hver nabo, der ikke er set: noter dens afstand som én mere end den aktuelle knudes, husk den aktuelle knude som vejen, den blev nået ad, og sæt den bagerst i køen. Spring naboer over, der er set før. Gentag, indtil køen er tom, eller målet er nået.

Et eksempel

Tag en graf med kanterne A–B, A–C, B–D, C–D, C–E og D–F, og start i A. Når A tages ud af køen, findes B og C med afstand 1. B finder D med afstand 2. C finder, at D allerede er set, og E med afstand 2. D finder F med afstand 3. E og F finder intet nyt, og køen er tom. Følger man de huskede knuder tilbage fra F, får man F ← D ← B ← A, så en korteste vej fra A til F er A → B → D → F, tre kanter lang.

Hvorfor afstandene er rigtige

Hver knude med afstand 1 kommer i køen før nogen knude med afstand 2, hver knude med afstand 2 før nogen med afstand 3, og så videre, fordi en knudes naboer først sættes i køen, når knuden selv tages ud. Den første vej, der når en knude, har altså færrest kanter, og BFS behøver aldrig rette en afstand. Hver knude tages én gang, og hver kant ses fra begge ender, så arbejdet vokser med antallet af knuder plus antallet af kanter.

Historie og anvendelser

Konrad Zuse beskrev bredde-først-søgning i 1945 i sit arbejde med sproget Plankalkül, som først blev udgivet i 1972. Edward F. Moore genopfandt den i 1959 for at finde den korteste vej ud af en labyrint, og C. Y. Lee brugte den i 1961 til at trække ledninger på printplader. I dag finder den det færreste antal træk i gåder, graderne af adskillelse i sociale netværk, de sider, en webcrawler når først, og den nærmeste ledige celle i spil. Når kanterne har længder, er Dijkstras algoritme en generalisering af den.

Konrad Zuse (i midten, med briller) og Heinz Billing (til venstre) på udstillingen SYSTEMS ’91 i München. Zuse beskrev bredde-først-søgning i 1945, i arbejde med sit sprog Plankalkül, der først blev udgivet i 1972.
Konrad Zuse (i midten, med briller) og Heinz Billing (til venstre) på udstillingen SYSTEMS ’91 i München. Zuse beskrev bredde-først-søgning i 1945, i arbejde med sit sprog Plankalkül, der først blev udgivet i 1972.

Udforsk den

Åbn appen, og tryk på Trin. Den knude, der besøges, er fremhævet, knuder, der venter i køen, er blå, og besøgte knuder er grønne, hver med sin afstand. Køen vises under grafen med den forreste først. Skift klikket til Mål, og vælg en knude for at stoppe der og se den korteste vej, eller lav en ny graf med flere knuder og kanter.

Ofte stillede spørgsmål

Hvad er tidskompleksiteten af BFS?

O(V + E) for V knuder (vertices) og E kanter (edges): hver knude kommer ind i og ud af køen én gang, og hver kant undersøges fra begge ender. Den kræver O(V) ekstra hukommelse til køen og afstandene.

Hvorfor bruger BFS en kø?

Fordi først ind, først ud holder knuderne i den rækkefølge, de blev opdaget, og det er rækkefølgen efter afstand. Med en stak i stedet ville søgningen dykke i dybden først: det er dybde-først-søgning.

Kan BFS finde korteste veje i vægtede grafer?

Ikke generelt: den tæller kanter, ikke deres længder. Til vægtede grafer uden negative kanter bruger man Dijkstras algoritme. Er alle vægte 0 eller 1, virker en variant kaldet 0-1 BFS.

Hvor bruges BFS?

Til at løse gåder og labyrinter med færrest mulige træk, finde venners venner i sociale netværk, gennemsøge nettet niveau for niveau, sende broadcast i netværk og som byggesten i andre algoritmer, fx til at finde maksimale strømninger.

Er du klar til at prøve?

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

Prøv bredde-først-søgning