Forskjellen mellom BFS og DFS
Share
BFS vs DFS
Bredde første søk (også kjent som BFS) er en søkemetode som brukes til å utvide alle nodene til en bestemt graf. Den oppnår denne oppgaven ved å søke hver eneste løsning for å undersøke og utvide disse nodene (eller en kombinasjon av sekvenser deri). Som sådan bruker en BFS ikke en heuristisk algoritme (eller en algoritme som søker etter en løsning gjennom flere scenarier). Etter at alle noder er oppnådd, blir de lagt til i en kø som kalles First In, First Out-køen. De noder som ikke har blitt utforsket, er "lagret" i en beholder merket "åpen"; Når de er utforsket, transporteres de til en beholder merket "lukket".
Dybde Første søk (også kjent som DFS) er en søkemetode som burver dypere inn i et barnsnode i et søk til et mål er nådd (eller til det er en node uten andre permutasjoner eller "barn"). Etter at et mål er funnet, søker søket tilbake til en tidligere node som har gått med en løsning, og gjentar prosessen til alle noder har blitt søkt etter. Som sådan fortsetter noder å bli avsatt for videre leting - dette kalles ikke-rekursiv implementering.
Funksjonene i BFS er plass- og tidskompleksitet, fullstendighet, fullstendighetsbevis og optimalitet. Mellomkompleksitet refererer til andelen av antall noder på det dypeste nivået av et søk. Tids kompleksitet refererer til den faktiske mengden tid som brukes til å vurdere hver bane en knut vil ta i et søk. Fullstendighet er i hovedsak et søk som finner en løsning i en graf uansett hvilken type graf det er. Beviset om fullstendigheten er det grunne nivået der et mål er funnet i en knutepunkt med en bestemt dybde. Til slutt refererer optimitet til en BFS som ikke er vektet - det er en graf som brukes til engangspris.
En DFS er den mest naturlige utgangen ved hjelp av et spennende tre - som er et tre som består av alle hjørner og noen kanter i en ikke-rettet graf. I denne formasjonen er grafen delt inn i tre klasser: Fremoverkanter, peker fra en node til en barnekode; bakkanter, peker fra en knute til en tidligere knutepunkt; og kryss kanter, som ikke gjør en av disse.
Sammendrag:
1. En BFS søker hver eneste løsning i en graf for å utvide nodene; en DFS burrows dypt inne i en barneknude til et mål er nådd.
2. Funksjonene til en BFS er plass og tidskompleksitet, fullstendighet, fullstendighetsbevis og optimalitet; Den mest naturlige utgangen for en DFS er et spennende tre med tre klasser: fremkanter, bakkanter og krysskanter.
