BFS och DFS är de krypteringsmetoder som används för att söka i en graf. Grafgräns är processen att besöka alla noder i grafen. En graf är en grupp av Vertices 'V' och Edges 'E' som kopplar till vertikalerna.
Jämförelsediagram
| Grunder för jämförelse | BFS | DFS |
|---|---|---|
| Grundläggande | Vertex-baserad algoritm | Edge-baserad algoritm |
| Datastruktur används för att lagra noderna | Kö | Stack |
| Minneskonsumtion | Ineffektiv | Effektiv |
| Strukturen av det konstruerade trädet | Bred och kort | Smal och lång |
| Traversing mode | Äldsta unvisited vertices utforskas först. | Vertikaler längs kanten utforskas i början. |
| optimalitet | Optimal för att hitta det kortaste avståndet, inte i kostnad. | Inte optimalt |
| Ansökan | Undersöker bifogad graf, ansluten komponent och kortaste väg som finns i en graf. | Undersöker tvåkantig ansluten graf, starkt ansluten graf, acyklisk graf och topologisk ordning. |
Definition av BFS
Breddens första sökning (BFS) är den traverseringsmetod som används i diagram. Den använder en kö för att lagra de besökta vertikalerna. I den här metoden ligger betoningen på gradernas hörn, en toppunkt väljs först då den besöks och markeras. Spetsarna intill det besökta vertexet besöks och lagras därefter i köen i följd. På samma sätt behandlas de lagrade vertikalerna en efter en, och deras intilliggande vertikaler besöks. En nod utforskas fullständigt innan du besöker någon annan nod i grafen, det vill säga det går först genom de grundaste oförtäckta noderna.
Exempel
Vi har en graf vars vinklar är A, B, C, D, E, F, G. Med tanke på A som utgångspunkt. Stegen som ingår i processen är:
- Vertex A expanderas och lagras i köen.
- Vertikalerna B, D och G efterföljare av A, expanderas och lagras i köen medan Vertex A avlägsnas.
- Nu avlägsnas B vid den främre änden av köen tillsammans med lagring av dess efterföljande hörn E och F.
- Vertex D är vid den främre änden av köen borttagen, och dess anslutna nod F är redan besökt.
- Vertex G avlägsnas från kön, och den har efterträdare E som redan har besökts.
- Nu tas E och F bort från kön, och dess efterföljande vertex C går över och lagras i kön.
- Äntligen tas C bort och köen är tom vilket betyder att vi är färdiga.
- Den genererade utgången är - A, B, D, G, E, F, C.
BFS kan vara användbar för att hitta om grafen har anslutna komponenter eller ej. Och det kan också användas för att detektera en tvåpartig graf .
Ett diagram är bipartitärt när graferna är delade i två ojämna satser; inga två intilliggande vertikaler skulle ligga i samma uppsättning. En annan metod för att kontrollera en tvåpartsgraf är att kontrollera förekomsten av en udda cykel i grafen. En tvåpartig graf får inte innehålla udda cyklar.
BFS är också bättre att hitta den kortaste vägen i grafen kan ses som ett nätverk.
Definition av DFS
Fördjupningsmetod för djupet första sökning (DFS) använder stapeln för att lagra de besökta vertikalerna. DFS är den kantbaserade metoden och arbetar på rekursivt sätt där vinklarna undersöks längs en bana (kant). Utforskningen av en nod upphävs så snart en annan oexplorerad nod hittas och de djupaste oförtäckta noderna kryssas framförallt. DFS kryssar / besöker varje vertex exakt en gång och varje kant inspekteras exakt två gånger.
Exempel
På samma sätt som BFS kan du ta samma graf för att utföra DFS-operationer, och de inblandade stegen är:
- Med tanke på A som startvärde som undersöks och lagras i stapeln.
- B efterföljande vertex av A lagras i stapeln.
- Vertex B har två efterträdare E och F, bland dem alfabetiskt E utforskas först och lagras i stapeln.
- Efterföljaren av vertexen E, dvs G lagras i stapeln.
- Vertex G har två anslutna vinklar, och båda är redan besökta, så G poppas ut från stapeln.
- På samma sätt togs E också bort.
- Nu är vertex B på toppen av stapeln, dess annan nod (vertex) F utforas och lagras i stapeln.
- Vertex F har två efterträdare C och D, mellan dem C är traverseras först och lagras i stapeln.
- Vertex C har bara en föregångare som redan har besökt, så den tas bort från stapeln.
- Nu vertex D ansluten till F besöks och lagras i stapeln.
- Eftersom vertex D inte har några unviserade noder, så avlägsnas D.
- På samma sätt dyker F, B och A också.
- Den genererade utsignalen är - A, B, E, G, F, C, D.
DFS-applikationerna innefattar inspektion av två kantanslutna grafer, starkt ansluten graf, acyklisk graf och topologisk ordning .
En graf kallas två kanter anslutna om och endast om den förbli ansluten även om en av dess kanter är borttagen. Denna applikation är väldigt användbar i datanät där felet på en länk i nätverket inte påverkar det återstående nätverket, och det skulle fortfarande vara anslutet.
Starkt kopplad graf är ett diagram där det måste finnas en bana mellan det beställda paret av kryssningar. DFS används i den riktade grafen för att söka sökvägen mellan varje beställt par hörn. DFS kan enkelt lösa anslutningsproblem.
Viktiga skillnader mellan BFS och DFS
- BFS är en vertexbaserad algoritm medan DFS är en kantbaserad algoritm.
- Ködatastrukturen används i BFS. DFS använder däremot stack eller recursion.
- Minneutrymme används effektivt i DFS medan rymdutnyttjandet i BFS inte är effektivt.
- BFS är optimal algoritm medan DFS inte är optimal.
- DFS konstruerar smala och långa träd. Däremot konstruerar BFS bred och kort träd.
Slutsats
BFS och DFS, båda grafikkökteknikerna har liknande körtid men olika rymdförbrukning, DFS tar linjärt utrymme eftersom vi måste komma ihåg en enda bana med oförtäckta noder medan BFS håller varje nod i minnet.
DFS ger djupare lösningar och är inte optimal, men det fungerar bra när lösningen är tät medan BFS är optimal som först söker det optimala målet.
