Innan vi tittar på skillnaderna mellan BFS och DFS bör vi först känna till BFS och DFS separat.
Vad är BFS?
BFS står för Utöka första sökningen . Det är också känt som nivåorderövergång . Ködatastrukturen används för Breadth First Search-genomgången. När vi använder BFS-algoritmen för övergången i en graf kan vi betrakta vilken nod som helst som en rotnod.
Låt oss betrakta grafen nedan för den första sökningen på bredden.
cassidy hutchinson utbildning
Anta att vi betraktar nod 0 som en rotnod. Därför skulle korsningen startas från nod 0.
När nod 0 har tagits bort från kön skrivs den ut och markeras som en besökt nod.
När nod 0 väl har tagits bort från kön, kommer de intilliggande noderna i nod 0 att infogas i en kö som visas nedan:
Nu kommer nod 1 att tas bort från kön; den skrivs ut och markeras som en besökt nod
När nod 1 väl har tagits bort från kön, kommer alla intilliggande noder i en nod 1 att läggas till i en kö. De intilliggande noderna i nod 1 är 0, 3, 2, 6 och 5. Men vi måste bara infoga obesökta noder i en kö. Eftersom noderna 3, 2, 6 och 5 är obesökta; därför kommer dessa noder att läggas till i en kö som visas nedan:
Nästa nod är 3 i en kö. Så nod 3 kommer att tas bort från kön, den skrivs ut och markeras som besökt som visas nedan:
När nod 3 väl har tagits bort från kön kommer alla intilliggande noder i nod 3 förutom de besökta noderna att läggas till i en kö. De intilliggande noderna för nod 3 är 0, 1, 2 och 4. Eftersom noderna 0, 1 redan är besökta och nod 2 finns i en kö; därför behöver vi bara infoga nod 4 i en kö.
hitta blockerade nummer på Android
Nu är nästa nod i kön 2. Så 2 skulle tas bort från kön. Den skrivs ut och markeras som besökt enligt nedan:
När nod 2 väl har tagits bort från kön kommer alla intilliggande noder i nod 2 förutom de besökta noderna att läggas till i en kö. De intilliggande noderna för nod 2 är 1, 3, 5, 6 och 4. Eftersom noderna 1 och 3 redan har besökts, och 4, 5, 6 redan har lagts till i kön; därför behöver vi inte infoga någon nod i kön.
Nästa element är 5. Så 5 skulle tas bort från kön. Den skrivs ut och markeras som besökt enligt nedan:
När nod 5 väl har tagits bort från kön kommer alla intilliggande noder i nod 5 förutom de besökta noderna att läggas till i kön. De intilliggande noderna av nod 5 är 1 och 2. Eftersom båda noderna redan har besökts; därför finns det ingen vertex som ska infogas i en kö.
Nästa nod är 6. Så 6 skulle tas bort från kön. Den skrivs ut och markeras som besökt enligt nedan:
När noden 6 väl har tagits bort från kön kommer alla intilliggande noder i nod 6 förutom de besökta noderna att läggas till i kön. De intilliggande noderna för nod 6 är 1 och 4. Eftersom nod 1 redan har besökts och nod 4 redan har lagts till i kön; därför finns det ingen vertex som ska infogas i kön.
Nästa element i kön är 4. Så 4 skulle tas bort från kön. Den skrivs ut och markeras som besökt.
När nod 4 väl har tagits bort från kön kommer alla intilliggande noder i nod 4 förutom de besökta noderna att läggas till i kön. De intilliggande noderna i nod 4 är 3, 2 och 6. Eftersom alla intilliggande noder redan har besökts; så det finns ingen vertex som ska infogas i kön.
array lista java
Vad är DFS?
DFS står för Depth First Search. Vid DFS-traversering används stackdatastrukturen, som fungerar enligt LIFO-principen (Last In First Out). I DFS kan traversering startas från vilken nod som helst, eller så kan vi säga att vilken nod som helst kan betraktas som en rotnod tills rotnoden inte nämns i problemet.
I fallet med BFS, elementet som tas bort från kön, läggs de intilliggande noderna till den borttagna noden till i kön. I kontrast, i DFS, elementet som tas bort från stacken, läggs endast en intilliggande nod till en raderad nod till i stacken.
Låt oss överväga diagrammet nedan för genomgången av Depth First Search.
Betrakta nod 0 som en rotnod.
Först infogar vi elementet 0 i stacken som visas nedan:
reagera inline stil
Noden 0 har två intilliggande noder, dvs 1 och 3. Nu kan vi bara ta en intilliggande nod, antingen 1 eller 3, för att korsa. Antag att vi betraktar nod 1; därför infogas 1 i en stack och skrivs ut som visas nedan:
Nu ska vi titta på de intilliggande hörnen av nod 1. De obesökta angränsande hörnen av nod 1 är 3, 2, 5 och 6. Vi kan betrakta vilken som helst av dessa fyra hörn. Anta att vi tar nod 3 och infogar den i stacken som visas nedan:
Betrakta de obesökta intilliggande hörn av nod 3. De obesökta angränsande hörn av nod 3 är 2 och 4. Vi kan ta någon av hörnen, dvs 2 eller 4. Antag att vi tar vertex 2 och infogar den i stapeln som visas nedan:
De obesökta intilliggande hörn av nod 2 är 5 och 4. Vi kan välja endera av hörnen, dvs 5 eller 4. Anta att vi tar vertex 4 och infogar i stacken som visas nedan:
Nu kommer vi att överväga de obesökta angränsande hörn av nod 4. Den obesökta angränsande hörn av nod 4 är nod 6. Därför infogas element 6 i stacken som visas nedan:
Efter att ha infogat element 6 i stacken kommer vi att titta på de obesökta angränsande hörnen av nod 6. Eftersom det inte finns några obesökta angränsande hörn av nod 6, så kan vi inte gå bortom nod 6. I detta fall kommer vi att utföra bakåtspårning . Det översta elementet, d.v.s. 6, skulle hoppa ut från stapeln som visas nedan:
Det översta elementet i stacken är 4. Eftersom det inte finns några obesökta intilliggande hörn kvar av nod 4; därför plockas nod 4 ut från stacken som visas nedan:
javascript trim delsträng
Det näst översta elementet i stacken är 2. Nu kommer vi att titta på de obesökta intilliggande hörnen av nod 2. Eftersom endast en obesökt nod, dvs. 5 är kvar, så skulle nod 5 skjutas in i stapeln ovanför 2 och skrivs ut enligt nedanstående:
Nu kommer vi att kontrollera de intilliggande hörnen av nod 5, som fortfarande är obesökta. Eftersom det inte finns någon vertex kvar att besöka, så skjuter vi element 5 från stapeln som visas nedan:
Vi kan inte flytta ytterligare 5, så vi måste utföra backtracking. Vid backtracking skulle det översta elementet plockas ut från stapeln. Det översta elementet är 5 som skulle hoppa ut från stacken, och vi går tillbaka till nod 2 som visas nedan:
Nu kommer vi att kontrollera de obesökta angränsande hörnen av nod 2. Eftersom det inte finns någon angränsande vertex kvar att besöka, så utför vi backtracking. I backtracking, skulle det översta elementet, dvs 2 hoppa ut från stacken, och vi flyttar tillbaka till nod 3 som visas nedan:
Nu kommer vi att kontrollera de obesökta angränsande hörnen av nod 3. Eftersom det inte finns någon intilliggande vertex kvar att besöka, så utför vi backtracking. I backtracking, skulle det översta elementet, dvs 3 hoppa ut från stacken och vi flyttar tillbaka till nod 1 som visas nedan:
Efter att ha poppat ut element 3 kommer vi att kontrollera de obesökta angränsande hörnen av nod 1. Eftersom det inte finns någon vertex kvar att besöka; därför kommer bakåtspårningen att utföras. I backtracking skulle det översta elementet, det vill säga 1, tas ut från stacken, och vi flyttar tillbaka till nod 0 som visas nedan:
Vi kommer att kontrollera de intilliggande hörnen av nod 0, som fortfarande är obesökta. Eftersom det inte finns någon intilliggande vertex kvar att besöka, så vi utför backtracking. I detta skulle bara ett element, det vill säga 0 kvar i stacken, tas ut från stacken som visas nedan:
Som vi kan observera i ovanstående figur att stacken är tom. Så vi måste stoppa DFS-genomgången här, och elementen som skrivs ut är resultatet av DFS-genomgången.
Skillnader mellan BFS och DFS
Följande är skillnaderna mellan BFS och DFS:
| BFS | DFS | |
|---|---|---|
| Fulla formen | BFS står för Breadth First Search. | DFS står för Depth First Search. |
| Metod | Det är en vertexbaserad teknik för att hitta den kortaste vägen i en graf. | Det är en kantbaserad teknik eftersom hörnen längs kanten utforskas först från start- till slutnoden. |
| Definition | BFS är en genomgångsteknik där alla noder på samma nivå utforskas först, och sedan går vi till nästa nivå. | DFS är också en genomgångsteknik där traversering startas från rotnoden och utforska noderna så långt som möjligt tills vi når noden som inte har några obesökta intilliggande noder. |
| Datastruktur | Ködatastruktur används för BFS-traverseringen. | Stackdatastruktur används för BFS-traverseringen. |
| Backtracking | BFS använder inte backtracking-konceptet. | DFS använder backtracking för att korsa alla obesökta noder. |
| Antal kanter | BFS hittar den kortaste vägen som har ett minsta antal kanter att korsa från källan till destinationspunkten. | I DFS krävs ett större antal kanter för att korsa från källpunkten till destinationspunkten. |
| Optimalitet | BFS-traversering är optimal för de hörn som ska sökas närmare källpunkten. | DFS-traversering är optimal för de grafer där lösningar är borta från källpunkten. |
| Fart | BFS är långsammare än DFS. | DFS är snabbare än BFS. |
| Lämplighet för beslutsträd | Det är inte lämpligt för beslutsträdet eftersom det kräver att man utforskar alla närliggande noder först. | Den är lämplig för beslutsträdet. Baserat på beslutet utforskar den alla vägar. När målet hittats stoppar det sin färd. |
| Minneseffektiv | Det är inte minneseffektivt eftersom det kräver mer minne än DFS. | Det är minneseffektivt eftersom det kräver mindre minne än BFS. |