BFS and DFS

DFS VS BFS:

Both of dfs and bfs are graph traversal algorithm.(tree is also a kind of graph)

BFS hocche breadth first search or level order searching. 1 / \ 2 5 / \ / \ 3 4 6 7

ai graph er jonno bfs hobe 1,2,5,3,4,6,7. prothome 1 k access kora hobe,then 2,5 k and aivabe cholte thakbe.bfs a first a akta vertex theke suru korte hocche not necessary j root thekei suru korte hobe.then oi vertex er sathe jei vertex gula add ache edge dara segula detect korte hobe.then prottek ta k abar expand korte hobe.thats like an explotion.

Algorithm ta aivabe kaj kore: ->take a vertex ->related vertex gula find koro ->expand korte thakbo same process a

mone rakte hobe akta vertex expand kora mane kintu tar kaj ses r amra already oi vertex ta visit o kore felsi(visit na korle expand korlam kivabe?).

Tahole ai bepar ta kintu clear j jei vertex ta age ase tar expand kora vertex gula bose tar pichone;er mane hocche uporer graph a jmn first a 1 k expand kore 2 r 5 paisi tahole amra jei data structure ta nibo sekhane surute bosbe 1,r tar pore bosbe 2 tarpor 5,abar jkhn 2 k expand korbo tkhn structure tar obostha hobe 1,2,5,3,4. jehute 1 k expand kora ses hoye gesilo tai 1 kintu 2,5 bosanor somoi r lagbei na, abar jkhn 2 k expand kore 3,4 bosalam tahole kintu 2 r lagbei na.tahole prothome bad gelo 1, tarpor 2,r tader expand kora vertex gula ase boslo akdom pichoner dike.Khub sohoj kore bolte gele age jara astese tarai age vagtese,notun kew asle pichone pathai dissi.Tahole aita akta queue chara r kisui na.tai bfs ta store korte amader lagbe "queue" namer data structure.

Upore lagbei na likha mane ai na j amra queue theke data ta urai dibo.Tahole akta jinis clear j bfs a amader vertex gula store kore rakha lage expand korar jonno.ai karone bola hoi j bfs besi memory consume kore.BFS besi memory consume korlew er upokaritaw ache.segula hocche:

->BFS guarantee dei solution khuje pawar ->Sobcheye minimum distance a solution return kore(1 er besi solution thakleo) ->DFS er moto ojotha loop a chokkhor kate na(DFS a details liksi)

sudhu upokarita janlei hobe?opokaritaw jante hobe.Opokarita na thakle DFS er dorkar ta ki? opokaritar solo kola purno kore besi memory khaye agei liksi,er arekta opokarita hocche jkhn solution ta largest distance a thake.jehutu level dhore dhore jai BFS tai solution ta jodi thake akdom seser level a taile solution paite paite barota baje jai.

Time complexity: Jei koi jaigai porsi sekhane time complexity ullok kora hoise O(V+E) jekhane V hocche vertex and E hocche Edge.kono kono jaigai O(n) o deksi jar mane hocche n ta vertex or node jai boli visit kora hoi worst case a.Quora te porsi j jkhn graph ta hoi sparse mane edge kom node besi tkhn aita hoye jai O(V) r jkhn dense hoi mane edge besi tokhon hoi O(E).GeeksforGeeks a bola hoiche j jodi graph ta(tree a likha ache) amn hoi j aita besi balanced(prottek node ai child balaance kora jmn binary tree te 2 ta kore thake) tahole bfs er time besi lage.kaorn tkhn level order a node besi visit kora lage.r jodi tree ta unbalanced hoi tahole depth a node bare jai tkhn DFS a besi time lage.

DFS: Depth first Serach er algorithm ta airokom: 1 / \ 2 5 / \ / \ 3 4 6 7

(1,2,3,4,5,6,7) ->select a node(1 here) ->er sathe ache 2,5 ->jekono akta nibo,normally 2(5 akhn nibona) ->then 2 theke 3(4 akhn nibona) ->3 theke jawar r kono rasta nai so back to 2 ->2 theke r kothai jawa jai? 4 a ->4 theke r kothaw jawar rasta nai,so back to 2 again ->2 er sob node visit kora ses,so back to 1, ->1 er r kono edge ache? ache 5 ->go to 5 ->5 er edge 6..6 er kisu nai,back to 5,5 to 7,7 er kisu nai,back to 5,5 er edge visit ses,back to 1,1 er o r kisu baki nai.DONE.

So basically it is a pre order traversal(root->left->right)

aikhane taile kon data structure use korbo? kheyal korle dekha jabe j kono node jkhn ses hoye jai othoba tar sob related node visit kora hoye jai abar back kore take tar ager node a fire jaite hoi.tar maneta ki?oi ager node ta obossoi kothaw store kore rakte hobe.Amar graph a 3,4 visit sese kintu abar 2 te back jaite hoiche,2 theke abar 1 a jaite hoise ,taile beparta ki daralo?prothome gelo 2,then 1.tar mane amader toh 1 k age store korte hobe then 2 k,kaorn prothome 3,4 jkhn ses tkhn kothai fire jabo? 2 te then 2 theke 1 a.Bujhai jasse j stack use korte hobe.FIFO rule follow j hocche babumosai aikhane.1 babaji age aseo pore j accessed hocche.

ai karonei DFS a amader memory kom lage,karon amader toh node gula store korte hocchena,khali ghuraghuri ses hole kon jaigai back korte hobe ta stack a joami raklei hobe.

Memory toh bachai dilam.Kintu er abar disadvantages o ache vaya.

dhori amder graph er result(dhorlam 7) jeita amra find kortesi. 7 ache dan dike.Akhn jodi amader bam baser subtree ta huge hoi taile seita visit kortei onek time kate jabe.R time katayei kono laver lav hobe na.solution toh nai e oikhane.Othocho matro r akta node dan pase visit korlei naki ans ta pawa jaito.Afsos!tokhon mone hoi isss keno j bfs er level order ta use korlamna.

arekta koster bepar porlam j DFS naki solution khuje pabe kina tar kono guarantee nai?aita mormantik.Abar duita ba tar besi jodi solution thake taw naki minimum solution ta khujte parena.Duplicate solution thakle taw naki bujte parena.ato boka ai DFS ta.tobe DFS er ki kono valo gun e nai?nai? nai...nai ...nai?

acheeeeeee........

jodi kono solution bepok govire thake,kitabi vasai maximum distance, thaole DFS khub kajer jinis.Karon taw toh simple DFS a akdom govie porjonto jawa hoi tai solution taw ase druto.durer solution khujte j BFS er barota baje jai ta agei bolsi. arekta adv. hocche jodi sob rastai e solution thake jmn maze a tahole DFS use korai valo.

Kokhn konta use korbo?