BFS Python
Bredde-første søk er fenomenet med å krysse hver node av grafen eller et tre, så hver node er krysset av to deler. Den ene er den 'besøkte' delen, og den andre er den 'ikke-besøkte' delen. Dette betyr at dette søket tar sikte på å nå hver node av grafen.
BFS pseudokode og algoritme
- Det første trinnet er å sette en hvilken som helst første kildeknute i køen bakfra.
- Lag den besøkte listen eller matrisen, og legg deretter nodene i den.
- Bruk en stundsløyfe for å sjekke at køen ikke er tom, og fortsett deretter å fjerne elementer i den besøkte listen.
- Alle de fjerne varene er merket som besøkte, og fjerner nå også naboene som ikke er besøkt fra køen.
Applikasjoner av BFS
- Det brukes til GPS -navigasjon.
- Den brukes til å finne banen.
- Den brukes til å bygge indeksen etter søkeindeks.
- Implementering av BFS.
Eksempel 1
Vi introduserer først grafen; Vi ønsker å ha verdiene som skal krysses. Hver node inneholder videre verdiene. For eksempel, her, vil den første nummer 5 koble seg til de to nodene 3 og 7. Tilsvarende er alle andre tall koblet til andre noder for å danne en graf. Etter å ha definert grafen, vil vi inneholde to array heltall datatyper for å lagre de numeriske verdiene til grafen som skal besøkes. Mens den andre inkluderer de nodene som ligger ved siden av de som blir besøkt.
Besøkt = []Kø = []
Begge matriser er tomme når du starter bredde-første søk. Men gradvis inneholder disse matriser verdiene til nodene som vi har beskrevet i grafen.
Etter å ha introdusert to matriser, vil vi definere en funksjon for å få tilgang til og søke i alle nodene linjemessig. Denne funksjonen tar verdiene til den besøkte matrisen, grafen og den tredje er noden. Inne i funksjonen vil vi legge til verdier i begge matriser, som beskrevet i algoritmen; Først legges verdiene inn i 'køen'; Når den besøkes, blir den aktuelle noden deretter overført til den besøkte køen. Så foreløpig vil denne funksjonen legge til verdiene i matriser ved å bruke en vedleggsfunksjon for hver matrise. Denne funksjonen inneholder nodene som en parameter i den.
Besøkte.vedlegg (node)Kø.vedlegg (node)
Etter det vil vi nå få tilgang til og besøke nodene gjennom en tilnærming. Denne måten å få tilgang til nodene ligner på tilgang til matriser fordi vi alltid bruker en løkke for å besøke hver indeks iterativt. Når det.
Dette mens Loop direkte vil målrette køen fordi nodene først blir lagt til i køen og deretter til det besøkte matrisen. Så verdiene vil bli trukket ut gjennom POP () -funksjonen og vil bli lagret i respektive variabler.
M = kø. Pop (0)Denne verdien vises på samtalen til utskriftsfunksjonen. Når verdiene fra køen blir trukket ut, vil denne verdien bli brukt til å lokalisere naboene som skal legges inn i køen. Så vi vil bruke til Loop her for å tildele hver nabo til enden av grafen. Tilstanden som brukes her er at hvis verdien ikke er i den besøkte matrisen, betyr det at den ikke har blitt åpnet tidligere, så vil den besøkte matrisen bli lagt til av disse nye verdiene (naboen) gjennom vedleggsfunksjonen. Og på samme måte vil køen også få de nye naboens verdi.
Besøkte. Vedlegg (nabo)
Funksjonssamtalen blir gjort sammen med den besøkte matrisen, hele grafen og noden som en parameter.
BFS (besøkte, graf, '5')
Etter å ha brukt denne koden, kan du se den aktuelle utdataene gjennom den resulterende konsollen ved å bruke utførelsesknappen øverst på verktøylinjen.
Du kan se at hele veien vil få tilgang til gjennom nodene. En ting kan observeres her: Alle disse startnodene vises bare fordi hver gang før utskriftsfunksjonen blir poppet ut fra køen fra køen.
Eksempel 2
Dette eksemplet fungerer på samme teknikk: å søke inne i grafen eller et tre. Men her har vi brukt tilnærmingen til OOP (objektorientert programmering) i Python ved å bruke klassesystemet. Så først vil vi importere noen funksjoner fra Collections Library. Disse funksjonene inkluderer "Standarddict" som inneholder ordboken på Python -språket.
Når vi beveger oss mot klassen, først definerer vi klassenavnet, og inne i klassen, her er konstruktøren. Siden konstruktører er de funksjonene som utføres automatisk når vi lager objektet for klassen. Formålet med klassen er nødvendig for å få tilgang til klassefunksjonene. Vi vil også lage objektet for grafklassen senere i artikkelen. Først er konstruktøren definert her for å initialisere listen tatt som en graf.
DefaultDict (liste)
“Er” som brukes til å lagre grafen i standardordboken.
Etter det brukes en funksjon her, 'lagt til' for å legge til den nye noden eller kanten i grafen. Nodene er også kjent som kanter og er representert av 'u,.I kontrast er avstanden mellom kantene representert av toppunktet og er nevnt av 'V.'Så inne i funksjonen vil grafen bli underholdt med nye noder gjennom appendfunksjonen.
Selv.graf [u]. vedlegg (v)Her har vi også brukt en funksjon for å vise BFS på en graf. Til å begynne med er alle nodene erklært som de ikke blir besøkt. I den første fasen av å søke, vil vi erklære statusen som falsk.
Besøkt = [falsk] * (maks (selv.graf) + 1)Tilsvarende initialiseres køen som null på opprettelsestidspunktet.
Kø = []La oss nå snakke om kildeknuten, som er den første; Vi vil legge den inn i det besøkte matrisen og trekke den ut fra køen som vi gjorde i det første eksemplet.
Kø.vedlegg (er)Besøkt [s] = sant
Nå brukes en stundsløyfe til å avgjøre alle nodene fra køen og vil deretter skrive ut verdien.
S = kø.pop (0)Etter det vil alle tilstøtende naboens noder bli trukket ut fra køen; Hvis noen node allerede er besøkt, vil dette bli lagt inn i den besøkte køen. Hvis pålevering brukes til å sjekke om noden ikke er besøkt allerede, legg den deretter fra køen og skriv den inn i den besøkte matrisen.
G = graf () er på en eller annen måte en måte å opprettholde konstruktøren, og dette objektet brukes videre til å kalle den ekstra funksjonen sammen med naboverdiene.
Konklusjon
Artikkelen 'BFS-Python' inneholder en kort beskrivelse av bredde-første søk i grafen for å krysse hver node. Denne søkingsprosessen gjøres ved å ha to lister som inneholder de besøkte og uvisede noder i dem. Vi har utdypet konseptet ved å legge til to elementære eksempler i guiden.