Ik begrijp de verschillen tussen DFS en BFS, maar ik zou graag willen weten wanneer het praktischer is om de ene boven de andere te gebruiken?

Kan iemand voorbeelden geven van hoe DFS BFS zou overtreffen en vice versa?

Antwoord 1, autoriteit 100%

Dat hangt sterk af van de structuur van de zoekboom en het aantal en de locatie van oplossingen (ook wel gezochte items genoemd).

• Als je weet dat een oplossing niet ver van de wortel van de boom ligt, a
  breedte eerst zoeken (BFS) is misschien beter.

• Als de boom erg diep is en oplossingen zeldzaam zijn, zoek dan eerst op diepte
  (DFS) kan extreem lang duren, maar BFS kan sneller zijn.

• Als de boom erg breed is, heeft een BFS mogelijk te veel geheugen nodig, dus het
  misschien helemaal onpraktisch.

• Als oplossingen vaak voorkomen maar zich diep in de boom bevinden, zou BFS dat kunnen zijn
  onpraktisch.

• Als de zoekboom erg diep is, moet u de zoekopdracht beperken
  diepte voor diepte eerst zoeken (DFS), hoe dan ook (bijvoorbeeld met
  iteratieve verdieping).

Maar dit zijn slechts vuistregels; je zult waarschijnlijk moeten experimenteren.

Een ander probleem is parallellisme: als je BFS wilt parallelliseren, heb je een gedeelde datastructuur tussen threads nodig, wat een slechte zaak is. DFS is misschien gemakkelijker te distribueren, zelfs tussen verbonden machines als u niet aandringt op de exacte volgorde van het bezoeken van de knooppunten.

Antwoord 2, autoriteit 45%

Diepte eerst zoeken

Diepte-eerst-zoekopdrachten worden vaak gebruikt in simulaties van games (en game-achtige situaties in de echte wereld). In een typisch spel kun je een van de verschillende mogelijke acties kiezen. Elke keuze leidt tot verdere keuzes, die elk leiden tot verdere keuzes, enzovoort in een steeds groter wordende boomvormige grafiek van mogelijkheden.

Bijvoorbeeld in spellen als schaken, boter-kaas-en-eieren als je beslist welke zet je gaat doen, kun je je een zet in je hoofd voorstellen, dan de mogelijke reacties van je tegenstander, dan je reacties, enzovoort. U kunt beslissen wat u moet doen door te kijken welke zet tot het beste resultaat leidt.

Slechts enkele paden in een spelboom leiden naar je overwinning. Sommige leiden tot een overwinning door je tegenstander, wanneer je zo’n einde bereikt, moet je een back-up maken of teruggaan naar een vorig knooppunt en een ander pad proberen. Zo verken je de boom tot je een pad vindt met een succesvolle afloop. Dan zet je de eerste stap op dit pad.

Breedte eerst zoeken

De breedte-eerste zoekopdracht heeft een interessante eigenschap: het vindt eerst alle hoekpunten die één rand verwijderd zijn van het startpunt, dan alle hoekpunten die twee randen verwijderd zijn, enzovoort. Dit is handig als u het kortste pad probeert te vinden van het beginpunt naar een bepaald punt. U start een BFS en wanneer u het opgegeven hoekpunt vindt, weet u dat het pad dat u tot nu toe hebt getraceerd, het kortste pad naar het knooppunt is. Als er een korter pad was, had de BFS het al gevonden.

Breedth-first search kan worden gebruikt voor het vinden van buurknooppunten in peer-to-peer-netwerken zoals BitTorrent, GPS-systemen om locaties in de buurt te vinden, sociale netwerksites om mensen op de opgegeven afstand te vinden en dergelijke.

Antwoord 3, autoriteit 30%

Leuke uitleg van
http://www.programmerinterview.com/index.php/data-structures/dfs -vs-bfs/

Een voorbeeld van BFS

Hier is een voorbeeld van hoe een BFS eruit zou zien. Dit is zoiets als Level Order Tree Traversal waar we WACHTRIJ zullen gebruiken met de ITERATIEVE benadering (meestal zal RECURSION eindigen met DFS). De cijfers vertegenwoordigen de volgorde waarin de knooppunten worden benaderd in een BFS:

Bij een eerste diepgaande zoekactie begin je bij de wortel en volg je een van de takken van de boom zo ver mogelijk totdat het knooppunt dat je zoekt is gevonden of je een bladknooppunt raakt (een knooppunt zonder kinderen ). Als je een bladknoop raakt, dan ga je verder met zoeken bij de dichtstbijzijnde voorouder met onontdekte kinderen.

Een voorbeeld van DFS

Hier is een voorbeeld van hoe een DFS eruit zou zien. Ik denk dat postordertraversal in binaire boom eerst vanaf het Leaf-niveau zal werken. De cijfers vertegenwoordigen de volgorde waarin de knooppunten worden benaderd in een DFS:

Verschillen tussen DFS en BFS

Als je BFS en DFS vergelijkt, is het grote voordeel van DFS dat het veel lagere geheugenvereisten heeft dan BFS, omdat het niet nodig is om alle onderliggende aanwijzers op elk niveau op te slaan. Afhankelijk van de gegevens en wat u zoekt, kan DFS of BFS voordelig zijn.

Als je bijvoorbeeld een stamboom geeft als iemand in de stamboom zoekt naar iemand die nog in leven is, dan zou het veilig zijn om aan te nemen dat die persoon onderaan in de stamboom zou staan. Dit betekent dat een BFS er erg lang over zou doen om dat laatste niveau te bereiken. Een DFS zou het doel echter sneller vinden. Maar als iemand op zoek was naar een familielid dat heel lang geleden stierf, dan zou die persoon dichter bij de top van de boom zijn. Dan zou een BFS meestal sneller zijn dan een DFS. De voordelen van beide variëren dus, afhankelijk van de gegevens en wat u zoekt.

Nog een voorbeeld is Facebook; Suggestie voor Vrienden van Vrienden. We hebben directe vrienden nodig voor suggesties waar we BFS kunnen gebruiken. Misschien vinden we het kortste pad of detecteren we de cyclus (met behulp van recursie), we kunnen DFS gebruiken.

Antwoord 4, autoriteit 13%

Breadth First Search is over het algemeen de beste aanpak wanneer de diepte van de boom kan variëren en u slechts een deel van de boom hoeft te doorzoeken voor een oplossing. Het vinden van het kortste pad van een beginwaarde naar een eindwaarde is bijvoorbeeld een goede plaats om BFS te gebruiken.

Diepte eerst zoeken wordt vaak gebruikt wanneer u de hele stamboom moet doorzoeken. Het is gemakkelijker te implementeren (met behulp van recursie) dan BFS en vereist minder status: terwijl BFS vereist dat u de hele ‘frontier’ opslaat, vereist DFS alleen dat u de lijst met bovenliggende knooppunten van het huidige element opslaat.

Antwoord 5, autoriteit 8%

DFS is ruimtebesparender dan BFS, maar kan onnodig diep gaan.

Hun namen zijn veelzeggend: als er een grote breedte is (d.w.z. een grote vertakkingsfactor), maar een zeer beperkte diepte (bijvoorbeeld een beperkt aantal “bewegingen”), dan kan DFS de voorkeur hebben boven BFS.

Op IDDFS

Er moet worden vermeld dat er een minder bekende variant is die de ruimte-efficiëntie van DFS combineert, maar (cumulatief) de niveau-volgorde-bezoeking van BFS, de iteratieve verdieping diepte-eerst zoeken. Dit algoritme bezoekt enkele knooppunten opnieuw, maar het draagt ​​alleen bij aan een constante factor van asymptotisch verschil.

Antwoord 6, autoriteit 5%

Als je deze vraag als programmeur benadert, valt één factor op: als je recursie gebruikt, is diepte-eerst zoeken eenvoudigerte implementeren, omdat je geen aanvullende gegevensstructuur met de knooppunten die nog moeten worden onderzocht.

Hier is diepte-eerst zoeken naar een niet-georiënteerde grafiek als u ‘reeds bezochte’ informatie opslaat in de knooppunten:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(neighbor) # Visit each neighbor if not already visited

Als u reeds bezochte informatie opslaat in een aparte gegevensstructuur:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(neighbor, visited)             # then visit the neighbor
dfs(origin, set())

Vergelijk dit met breed zoeken, waarbij u een aparte gegevensstructuur moet onderhouden voor de lijst met knooppunten die u nog moet bezoeken, wat er ook gebeurt.

Antwoord 7, autoriteit 4%

Een belangrijk voordeel van BFS zou zijn dat het kan worden gebruikt om het kortste pad tussen twee willekeurige knooppunten in een ongewogen grafiek te vinden.
Terwijl we geen DFS kunnen gebruiken voor hetzelfde.

Antwoord 8, autoriteit 2%

Het volgende is een uitgebreid antwoord op wat je vraagt.

In eenvoudige bewoordingen:

Breadth First Search (BFS)-algoritme, van zijn naam “Breadth”, ontdekt alle buren van een knooppunt via de buitenranden van het knooppunt en vervolgens ontdekt het de niet-bezochte buren van de eerder genoemde buren via hun buitenranden, enzovoort , totdat alle knooppunten die bereikbaar zijn vanuit de oorspronkelijke bron zijn bezocht (we kunnen doorgaan en een andere oorspronkelijke bron nemen als er nog niet-bezochte knooppunten zijn, enzovoort). Daarom kan het worden gebruikt om het kortste pad (als dat er is) van een knooppunt (oorspronkelijke bron) naar een ander knooppunt te vinden als de gewichten van de randen uniform zijn.

Depth First Search (DFS)-algoritme, van zijn naam “Depth”, ontdekt de niet-bezochte buren van het meest recent ontdekte knooppunt x via de buitenste randen. Als er geen niet-bezochte buur is vanaf het knooppunt x, gaat het algoritme terug om de niet-bezochte buren van het knooppunt te ontdekken (via de buitenste randen) van waaruit knooppunt x werd ontdekt, enzovoort, totdat alle knooppunten die bereikbaar zijn vanuit de oorspronkelijke bron zijn bezocht (we kunnen doorgaan en een andere originele bron nemen als er nog niet-bezochte knooppunten zijn, enzovoort).

Zowel BFS als DFS kunnen onvolledig zijn. Als de vertakkingsfactor van een knooppunt bijvoorbeeld oneindig is, of erg groot voor de bronnen (geheugen) om te ondersteunen (bijv. bij het opslaan van de knooppunten die vervolgens moeten worden ontdekt), dan is BFS niet compleet, ook al kan de gezochte sleutel zich op een afstand bevinden van enkele randen van de oorspronkelijke bron. Deze oneindige vertakkingsfactor kan het gevolg zijn van oneindige keuzes (naburige knooppunten) van een bepaald knooppunt om te ontdekken.
Als de diepte oneindig is, of erg groot voor de bronnen (geheugen) die moeten worden ondersteund (bijvoorbeeld bij het opslaan van de knooppunten die vervolgens moeten worden ontdekt), dan is DFS niet compleet, ook al kan de gezochte sleutel de derde buur van de oorspronkelijke bron zijn. Deze oneindige diepte kan het gevolg zijn van een situatie waarin er, voor elk knooppunt dat het algoritme ontdekt, ten minste een nieuwe keuze (naburig knooppunt) is die nog niet eerder is bezocht.

Daarom kunnen we besluiten wanneer we de BFS en DFS moeten gebruiken. Stel dat we te maken hebben met een hanteerbare beperkte vertakkingsfactor en een hanteerbare beperkte diepte. Als het gezochte knooppunt ondiep is, d.w.z. bereikbaar na enkele randen van de oorspronkelijke bron, dan is het beter om BFS te gebruiken. Aan de andere kant, als het gezochte knooppunt diep is, d.w.z. bereikbaar na veel randen van de oorspronkelijke bron, dan is het beter om DFS te gebruiken.

Als we bijvoorbeeld in een sociaal netwerk willen zoeken naar mensen die dezelfde interesses hebben van een specifieke persoon, kunnen we BFS van deze persoon als originele bron toepassen, omdat deze mensen meestal zijn directe vrienden of vrienden van vrienden dwz een of twee randen ver.
Aan de andere kant, als we willen zoeken naar mensen die totaal verschillende interesses hebben van een specifieke persoon, kunnen we DFS van deze persoon als een originele bron toepassen, omdat deze mensen meestal erg ver van hem verwijderd zullen zijn, dwz vriend van vriend van vriend …. dwz te veel randen ver.

Toepassingen van BFS en DFS kunnen ook variëren vanwege het zoekmechanisme in elk ervan. We kunnen bijvoorbeeld BFS gebruiken (ervan uitgaande dat de vertakkingsfactor beheersbaar is) of DFS (ervan uitgaande dat de diepte beheersbaar is) wanneer we alleen de bereikbaarheid van het ene knooppunt naar het andere willen controleren zonder informatie waar dat knooppunt zich kan bevinden. Beiden kunnen ook dezelfde taken oplossen, zoals het topologisch sorteren van een grafiek (als dat het geval is).
BFS kan worden gebruikt om het kortste pad te vinden, met eenheidsgewichtsranden, van een knoop (oorspronkelijke bron) naar een andere. Terwijl DFS kan worden gebruikt om alle keuzes uit te putten vanwege de aard van de diepte, zoals het ontdekken van het langste pad tussen twee knooppunten in een acyclische grafiek. Ook DFS, kan worden gebruikt voor cyclusdetectie in een grafiek.

Uiteindelijk, als we oneindige diepte en oneindige vertakkingsfactor hebben, kunnen we Iterative Deepening Search (IDS) gebruiken.

Antwoord 9

Voor BFS kunnen we een Facebook-voorbeeld nemen. We ontvangen suggesties om vrienden toe te voegen van het FB-profiel van een ander ander vriendenprofiel. Stel dat A->B, terwijl B->E en B->F, dus A een suggestie krijgt voor E en F. Ze moeten BFS gebruiken om tot het tweede niveau te lezen.
DFS is meer gebaseerd op scenario’s waarin we iets willen voorspellen op basis van gegevens die we van bron tot bestemming hebben. Zoals al gezegd over schaken of sudoku.
Zodra ik hier iets anders heb, geloof ik dat DFS moet worden gebruikt voor het kortste pad, omdat DFS eerst het hele pad zal bestrijken, dan kunnen we het beste beslissen. Maar aangezien BFS de aanpak van greedy zal gebruiken, lijkt het misschien de kortste weg, maar het uiteindelijke resultaat kan verschillen.
Laat me weten of ik het verkeerd heb begrepen.

Antwoord 10

Sommige algoritmen zijn afhankelijk van bepaalde eigenschappen van DFS (of BFS) om te werken. Het Hopcroft- en Tarjan-algoritme voor het vinden van 2-verbonden componenten maakt bijvoorbeeld gebruik van het feit dat elk reeds bezocht knooppunt dat DFS tegenkomt zich op het pad van root naar het momenteel verkende knooppunt bevindt.

Antwoord 11

Ik denk dat het afhangt van de problemen waarmee u wordt geconfronteerd.

1. kortste pad op eenvoudige grafiek -> vriendjes
2. alle mogelijke resultaten -> dfs
3. zoek op grafiek (behandel boom, martix ook als grafiek) -> dfs
   ….

Antwoord 12

Volgens de eigenschappen van DFS en BFS.
Bijvoorbeeld wanneer we het kortste pad willen vinden.
we gebruiken meestal bfs, het kan de ‘kortste’ garanderen.
maar dfs kan alleen garanderen dat we vanaf dit punt dat punt kunnen bereiken, kan niet de ‘kortste’ garanderen.

Antwoord 13

Omdat Depth-First Searches een stapel gebruiken terwijl de knooppunten worden verwerkt, wordt backtracking geleverd met DFS. Omdat Breadth-First Searches een wachtrij gebruiken, geen stapel, om bij te houden welke knooppunten worden verwerkt, is backtracking niet voorzien in BFS.

Antwoord 14

Als de boombreedte erg groot is en de diepte laag, gebruik dan DFS omdat de recursiestapel niet overloopt. Gebruik BFS als de breedte laag en de diepte erg groot is om door de boom te gaan.

Antwoord 15

Dit is een goed voorbeeld om aan te tonen dat BFS in bepaalde gevallen beter is dan DFS. https://leetcode.com/problems/01-matrix/

Als ze correct zijn geïmplementeerd, zouden beide oplossingen cellen moeten bezoeken die een grotere afstand hebben dan de huidige cel +1.
Maar DFS is inefficiënt en bezocht herhaaldelijk dezelfde cel, wat resulteert in O(n*n)-complexiteit.

Bijvoorbeeld

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,