BFS og DFS er de kryssende metodene som brukes til å søke i en graf. Grafstrekning er prosessen med å besøke alle nodene i grafen. En graf er en gruppe av Vertices 'V' og Edges 'E' som knytter til kryssene.
Sammenligningstabel
| Grunnlag for sammenligning | BFS | DFS |
|---|---|---|
| grunn~~POS=TRUNC | Vertex-basert algoritme | Edge-basert algoritme |
| Datastruktur brukes til å lagre noder | Kø | Stable |
| Minneforbruk | Ineffektiv | Effektiv |
| Struktur av det konstruerte treet | Bred og kort | Smal og lang |
| Traversing mote | Eldste unvisited vertices blir utforsket først. | Vertikaler langs kanten blir utforsket i begynnelsen. |
| optimalitet | Optimal for å finne den korteste avstanden, ikke i kostnad. | Ikke optimal |
| applikasjon | Undersøker bipartittgraf, tilkoblet komponent og korteste vei til stede i en graf. | Undersøker to-kant koblet graf, sterkt tilkoblet graf, acyklisk graf og topologisk rekkefølge. |
Definisjon av BFS
Bredde første søk (BFS) er den krypteringsmetoden som brukes i grafer. Den bruker en kø for å lagre de besøkte hjørnene. I denne metoden legges vekten på graftene i grafen, en toppunkt velges først da den blir besøkt og merket. Sporene ved siden av det besøkte toppunktet blir deretter besøkt og lagret i køen i rekkefølge. På samme måte blir de lagrede vertices behandlet en etter en, og deres tilstøtende hjørner blir besøkt. En knutepunkt er fullstendig utforsket før du besøker noen annen knutepunkt i grafen, med andre ord, den krysser grunnleggende uutforskede noder først.
Eksempel
Vi har en graf hvis vinkler er A, B, C, D, E, F, G. Vurderer A som utgangspunkt. Trinnene involvert i prosessen er:
- Vertex A utvides og lagres i køen.
- Vertikaler B, D og G etterfølgere av A, blir utvidet og lagret i køen mens Vertex A fjernes.
- Nå er B i den forreste enden av køen fjernet sammen med lagring av etterfølgerens hjørner E og F.
- Vertex D er på forsiden av køen er fjernet, og den tilkoblede noden F er allerede besøkt.
- Vertex G fjernes fra køen, og den har etterfølger E som allerede er besøkt.
- Nå fjernes E og F fra køen, og dens etterfølgervertex C blir krysset og lagret i køen.
- Endelig fjernes også C, og køen er tom, noe som betyr at vi er ferdige.
- Den genererte utgangen er - A, B, D, G, E, F, C.
BFS kan være nyttig for å finne ut om grafen har koblet til komponenter eller ikke. Og også det kan brukes til å oppdage en todelt graf .
En graf er todelt når grafpunktene er delt inn i to disjoint sett; ingen to tilstøtende hjørner ville ligge i samme sett. En annen metode for å sjekke en todelt graf er å kontrollere forekomsten av en merkelig syklus i grafen. En todelt graf må ikke inneholde merkelig syklus.
BFS er også bedre å finne den korteste banen i grafen, kan sees som et nettverk.
Definisjon av DFS
Dybde-første søk (DFS) -kryssingsmetode bruker stakken til å lagre de besøkte vertikaler. DFS er kantenbasert metode og fungerer på rekursivt mote hvor kryssene utforskes langs en bane (kant). Utforskningen av en node er suspendert så snart en annen uutforsket node er funnet, og de dypeste uutforskede noder blir krysset fremover. DFS krysse / besøke hvert toppunkt nøyaktig en gang og hver kant blir inspisert nøyaktig to ganger.
Eksempel
Ligner på BFS, kan vi ta samme graf for å utføre DFS-operasjoner, og de involverte trinnene er:
- Vurderer A som startpunktet som utforskes og lagres i stakken.
- B etterfølgervertex av A lagres i stabelen.
- Vertex B har to etterfølgere E og F, blant dem er alfabetisk E utforsket først og lagret i stabelen.
- Etterfølgeren til toppunktet E, dvs. G, er lagret i stabelen.
- Vertex G har to sammenhenger, og begge er allerede besøkt, så G er poppet ut fra stakken.
- På samme måte fjernet E også.
- Nå er toppunktet B øverst på stakken, dets annen knutepunkt (vertex) F blir utforsket og lagret i stabelen.
- Vertex F har to etterfølgere C og D, mellom dem C blir krysset først og lagret i stabelen.
- Vertex C har bare en forgjenger som allerede er besøkt, så den fjernes fra stakken.
- Nå er vertex D koblet til F besøkt og lagret i stabelen.
- Da vertex D ikke har noen unvisited noder, blir D derfor fjernet.
- Tilsvarende er F, B og A også poppet.
- Den genererte produksjonen er - A, B, E, G, F, C, D.
Applikasjonene til DFS inkluderer inspeksjon av to kanten forbundet graf, sterkt koblet graf, acyklisk graf og topologisk rekkefølge .
En graf kalles to kanter tilkoblet hvis og bare hvis den forblir tilkoblet, selv om en av kantene er fjernet. Denne applikasjonen er veldig nyttig i datanettverk der feilen på en kobling i nettverket ikke vil påvirke det gjenværende nettverket, og det ville fortsatt være tilkoblet.
Sterk koblet graf er en graf der det må eksistere en bane mellom det ordnede parpunktet. DFS brukes i den rettede grafen for å søke banen mellom hvert bestilt par punkter. DFS kan enkelt løse problemer med tilkobling.
Viktige forskjeller mellom BFS og DFS
- BFS er verteksbasert algoritme mens DFS er en kantbasert algoritme.
- Que data strukturen brukes i BFS. På den annen side bruker DFS stabel eller rekursjon.
- Minneplass utnyttes effektivt i DFS mens romutnyttelse i BFS ikke er effektiv.
- BFS er optimal algoritme mens DFS ikke er optimal.
- DFS konstruerer smale og lange trær. BFS konstruerer imidlertid bredt og kort tre.
Konklusjon
BFS og DFS, begge grafnesøkteknikkene har lignende kjøretid, men forskjellig plassforbruk, DFS tar lineær plass fordi vi må huske enkeltvei med uutforskede noder mens BFS holder hver knut i minnet.
DFS gir dypere løsninger og er ikke optimal, men det fungerer bra når løsningen er tett, mens BFS er optimal som først søker det optimale målet.
