Forskellen mellem BFS og DFS

BFS vs DFS

Breadth First Search (også kendt som BFS) er en søgemetode, der bruges til at udvide alle noder i en bestemt graf. Det udfører denne opgave ved at søge i hver enkelt løsning for at undersøge og udvide disse knuder (eller en kombination af sekvenser deri). Som sådan bruger en BFS ikke en heuristisk algoritme (eller en algoritme, der søger efter en løsning gennem flere scenarier). Når alle noder er opnået, føjes de til en kø, der kaldes First In, First Out køen. De noder, der ikke er blevet udforsket, 'gemt' i ​​en container markeret med 'åben'; når de først er blevet udforsket, transporteres de til en container mærket 'lukket'.

Deepth First Search (også kendt som DFS) er en søgemetode, der graver sig dybere ned i et barneknudepunkt i en søgning, indtil et mål er nået (eller indtil der er en knude uden nogen andre permutationer eller 'børn'). Når der er fundet et mål, søges backtracks til en tidligere knude, der er gået med en løsning, hvor processen gentages, indtil alle noder er blevet søgt med succes. Som sådan fortsættes knudepunkter til side for yderligere efterforskning - dette kaldes ikke-rekursiv implementering.

Funktionerne i BFS er rum- og tidskompleksitet, fuldstændighed, bevis på fuldstændighed og optimalitet. Rumkompleksitet henviser til andelen af ​​antallet af knudepunkter på det dybeste niveau af en søgning. Tidskompleksitet henviser til den faktiske mængde 'tid', der bruges til at overveje hver sti, en knude vil tage i en søgning. Fuldstændighed er i det væsentlige en søgning, der finder en løsning i en graf uanset hvilken type graf det er. Beviset for fuldstændighed er det laveste niveau, på hvilket et mål findes i en knude på en bestemt dybde. Endelig henviser optimalitet til en BFS, der ikke er vægtet - det er en graf, der bruges til enheds-trin-omkostninger.

En DFS er den mest naturlige output ved hjælp af et spændende træ - som er et træ bestående af alle hjørner og nogle kanter i en ikke-rettet graf. I denne formation er grafen opdelt i tre klasser: Fremadkanter, der peger fra en knude til en barneknudepunkt; bagkanter, der peger fra en knude til en tidligere knude; og tværkanter, som ikke gør en af ​​disse.

Resumé:

1. En BFS søger efter hver eneste løsning i en graf for at udvide sine knudepunkter; en DFS graver dybt inde i en børneknude, indtil et mål er nået.

2. Funktionerne i en BFS er rum- og tidskompleksitet, fuldstændighed, bevis på fuldstændighed og optimalitet; den mest naturlige output for et DFS er et spændende træ med tre klasser: forkanter, bagkanter og tværkanter.