Erinevus BFS ja DFS vahel

BFS vs DFS

Laiuse esimene otsing (tuntud ka kui BFS) on otsingumeetod, mida kasutatakse konkreetse graafi kõigi sõlmede laiendamiseks. Ta täidab selle ülesande, otsides iga lahenduse, et uurida ja laiendada neid sõlmi (või nendes sisalduvat järjestuste kombinatsiooni). Sellisena ei kasuta BFS heuristilist algoritmi (või algoritmi, mis otsib lahendust mitme stsenaariumi kaudu). Pärast kõigi sõlmede saamist lisatakse need järjekorda, mida nimetatakse järjekorda Esimene sisse, esimene välja. Neid sõlme, mida pole uuritud, “hoitakse” konteineris, millel on märge “avatud”; kui need on uuritud, veetakse nad konteinerisse, mille silt on suletud.

Esimene sügavusotsing (tuntud ka kui DFS) on otsingumeetod, mis tungib sügavamale otsingu lastesõlme, kuni eesmärk on saavutatud (või seni, kuni on olemas sõlme, millel pole muid permutatsioone või 'lapsi'). Pärast ühe eesmärgi leidmist tagasitulek eelmisele sõlmele, mis on lahendusega läinud, korratakse protsessi seni, kuni kõik sõlmed on edukalt otsitud. Sellisena on sõlmed jätkuvalt edasiseks uurimiseks kõrvale pandud - seda nimetatakse mitterekursiivseks rakendamiseks.

BFS-i funktsioonideks on ruumi ja aja keerukus, terviklikkus, täielikkuse tõestamine ja optimaalsus. Ruumi keerukus viitab otsingu sügavaimas astmes olevate sõlmede arvule. Aja keerukus osutab tegelikule ajakulule, mida kasutatakse iga tee uurimiseks, mille sõlme otsingus läbib. Täielikkus on sisuliselt otsing, mis leiab graafilt lahenduse olenemata sellest, milline graaf see on. Täielikkuse tõestuseks on madalaim tase, mille korral eesmärk leitakse sõlmes kindlal sügavusel. Lõpuks osutab optimaalsus BFS-i, mida ei kaaluta - see on graafik, mida kasutatakse ühiku astme maksumuse jaoks.

DFS on kõige loomulikum väljund, mis hõlmab kattepuud - see on puu, mis koosneb kõigist tippudest ja suunamata graafi mõnest servast. Selles moodustises jaguneb graafik kolme klassi: eesmised servad, suunates sõlmest alamsõlme; tagumised servad, suunates sõlmest varasemale sõlmele; ja risttalad, mis ei tee kumbagi neist.

Kokkuvõte:

1. BFS otsib graafiku igast lahendusest oma sõlmede laiendamiseks; DFS urdub sügaval lastesõlmes, kuni eesmärk on saavutatud.

2. BFS-i tunnused on ruumi ja aja keerukus, terviklikkus, täielikkuse tõestamine ja optimaalsus; DFS-i kõige loomulikum väljund on kolme klassi sirutuv puu: esiservad, tagumised servad ja ristiservad.