Johdatus BFS-algoritmiin

Jotta tietoja voidaan käyttää ja hallita tehokkaasti, se voidaan tallentaa ja järjestää erityisessä muodossa, jota kutsutaan tietorakenteeksi. Tietorakenteita, kuten pino, taulukko, linkitetty lista, jonot, puut ja kaaviot jne., On monia, lineaarisissa tietorakenteissa, kuten pino, taulukko, linkitetty lista ja jono, tiedot järjestetään lineaarisessa järjestyksessä, kun taas lineaariset tietorakenteet, kuten puut ja kaaviot, tiedot järjestetään hierarkkisesti, ei sarjassa. Kaavio on epälineaarinen tietorakenne, jolla on solmut ja reunat. Graafin solmuihin voidaan myös viitata kärkipisteinä, joiden lukumäärä on äärellinen, ja reunat ovat yhdyslinjat minkä tahansa kahden solmun välillä.

Yllä olevassa kuvaajassa tiput voidaan esittää muodossa V = (A, B, C, D, E) ja reunat voidaan määritellä

E = (AB, AC, CD, BE)

Mikä on BFS-algoritmi?

Yleensä on olemassa kaksi algoritmia, joita käytetään käyrän läpikulkemiseen. Ne ovat BFS (leveys ensimmäinen haku) ja DFS (syvyys ensimmäinen haku) algoritmeja. Graafin poikittaiskäynti käy tarkalleen kerran jokaisessa kärjessä tai solmussa ja reunassa, tarkkaan määriteltynä järjestyksessä. Lisäksi on erittäin tärkeää seurata vierailtuja kärkipisteitä, jotta samaa kärkeä ei kuljeta kahdesti. Breath First Search -algoritmissa liikkuminen alkaa valitusta solmasta tai lähdesolmusta ja poikittainen jatkuu suoraan lähdesolmuun kytkettyjen solmujen kautta. Yksinkertaisemmin sanottuna BFS-algoritmissa pitäisi ensin liikkua vaakatasossa ja kulkea nykyisen kerroksen läpi, minkä jälkeen siirrytään seuraavaan kerrokseen.

Kuinka BFS-algoritmi toimii?

Otetaan esimerkki alla olevasta kaaviosta.

Tärkeä käsillä oleva tehtävä on löytää lyhin polku kaaviosta kulkiessaan solmuja. Kun kuljemme graafin läpi, kärki siirtyy havaitsemattomasta tilasta löydettyyn tilaan ja lopulta tulee täysin löydetyksi. On huomattava, että on mahdollista juuttua jossain vaiheessa kulkiessaan kuvaajan läpi ja solmuun voidaan käydä kahdesti. Joten voimme käyttää menetelmää solmujen merkitsemiseksi sen jälkeen, kun se muuttaa löytämättömän tilan täysin löydetyksi.

Alla olevassa kuvassa voidaan nähdä, että solmut voidaan merkitä kaavioihin, kun ne havaitaan täysin merkitsemällä ne mustalla. Voimme aloittaa lähdesolmusta ja kun kulku etenee kunkin solmun läpi, ne voidaan merkitä tunnistettaviksi.

Läpikulku alkaa kärjestä ja kulkee sitten lähteville reunoille. Kun reuna menee tuntemattomaan kärkeen, se merkitään löydetyksi. Mutta kun reuna menee täysin löydettyyn tai havaittuun kärkeen, sitä ei huomioida.

Suunnatun kuvaajan kohdalla jokaista reunaa käydään kerran ja suuntaamatonta kuvaajaa varten se käydään kahdesti eli kerran käydessään kutakin solmua. Käytettävästä algoritmista päätetään sen perusteella, kuinka löydetyt huiput tallennetaan. BFS-algoritmissa jonoa käytetään, kun ensin löydetään vanhin kärkipiste ja etenee sitten kerrosten läpi lähtöpisteestä.

Vaiheet suoritetaan BFS-algoritmille

Seuraavat vaiheet suoritetaan BFS-algoritmille.

  • Aloitetaan tietyssä kuvaajassa kärkipisteestä, ts. Yllä olevassa kaaviossa se on solmu 0. Taso, jossa tämä kärki on läsnä, voidaan nimittää kerrokseksi 0.
  • Seuraava askel on löytää kaikki muut kärkipisteet, jotka ovat lähtöpisteen vieressä, ts. Solmu 0 tai päästä heti siitä. Sitten voimme merkitä nämä vierekkäiset huiput läsnä kerroksessa 1.
  • Samaan kärkeen on mahdollista tulla graafin silmukan takia. Joten meidän pitäisi matkustaa vain niihin kärkipisteisiin, joiden pitäisi olla läsnä samassa kerroksessa.
  • Seuraavaksi merkitään nykyisen kärkipisteen yläkärki. Sama on tehtävä kaikille kerroksen 1 kärkipisteille.
  • Seuraava askel on sitten löytää kaikki ne kärkipisteet, jotka ovat yhden reunan päässä kaikista kerroksen 1 kärkipisteistä. Nämä uudet kärjen sarjat ovat kerroksessa 2.
  • Yllä olevaa prosessia toistetaan, kunnes kaikki solmut ohitetaan.

Esimerkki:

Otetaan esimerkki alla olevasta kaaviosta ja ymmärretään, kuinka BFS-algoritmi toimii. Yleensä BFS-algoritmissa jonoa käytetään solmuttamaan jonot solmujen kulkiessa.

Yllä olevassa kaaviossa käydään ensin solmua 0 ja tämä solmu asetetaan jonoon seuraavaan jonoon:

Vierailun jälkeen solmulle 0 vierekkäiset solmut 0, 1 ja 2 asetetaan jonoon. Jono voidaan esittää seuraavasti:

Sitten jonon ensimmäiseen solmuun, joka on 2, käydään. Sen jälkeen kun solmua 2 on käyty, jono voidaan esittää seuraavasti:

Solmun 2 vierailun jälkeen 5 on jonossa ja koska solmulle 5 ei ole vierailemattomia naapurisolmuja, silti vaikka 5 on jonossa, mutta sitä ei käydä kahdesti.

Seuraavaksi jonon ensimmäinen solmu on 1, jota käydään. Naapurisolmut 3 ja 4 on jonossa. Jono on esitetty alla esitetyllä tavalla

Seuraavaksi jonon ensimmäinen solmu on 5, ja tälle solmulle ei ole enää vierailemattomia naapurisolmuja. Sama pätee solmuihin 3 ja 4, joille ei ole myöskään muita vierailemattomia naapurisolmuja.

Joten kaikki solmut ohitetaan ja lopulta jono tyhjenee.

johtopäätös

Leveyshakualgoritmissa on joitain suuria etuja, jotta sitä suositellaan. Yksi monista BFS-algoritmin sovelluksista on laskea lyhyin reitti. Sitä käytetään myös verkottumisessa naapurisolmujen löytämiseen ja se löytyy sosiaalisen verkostoitumisen sivustoista, verkkolähetyksistä ja roskien keräyksestä. Käyttäjien on ymmärrettävä vaatimus ja tietomallit voidakseen käyttää sitä parempaan suorituskykyyn.

Suositellut artikkelit

Tämä on opas BFS-algoritmiin. Tässä keskustellaan käsitteestä, työskentelystä, vaiheista ja esimerkistä suorituskyvystä BFS-algoritmissa. Voit myös käydä läpi muiden ehdotettujen artikkeleidemme saadaksesi lisätietoja -

  1. Mikä on ahne algoritmi?
  2. Säteiden jäljitysalgoritmi
  3. Digitaalisen allekirjoituksen algoritmi
  4. Mikä on Java Hibernate?
  5. Digitaalisen allekirjoituksen salaus
  6. BFS VS DFS | Kuusi tärkeintä eroa infografioiden kanssa

Luokka:

Suuri data