Breadth First Search
BFS står för Breadth First Search och är en vertexbaserad teknik för att hitta den kortaste vägen i en graf. Den använder en datastruktur med köer som följer principen ”först in, först ut”. I BFS väljs en vertex ut i taget när den besöks och markeras, därefter besöks dess angränsande vertexar och lagras i kön. Den är långsammare än DFS.
Ex-
A / \ B C / / \ D E F
Output är:
A, B, C, D, E, F
Depth First Search
DFS står för Depth First Search och är en kantbaserad teknik. Den använder datastrukturen Stack och utför två steg, först läggs besökta hörn in i stapeln och om det inte finns några hörn tas de besökta hörnen bort.
Ex-
A / \ B C / / \ D E F
Resultatet är:
A, B, D, C, E, F
BFS vs DFS
| S.NO | BFS | DFS | |
|---|---|---|---|
| DFS står för Depth First Search. | |||
| DFS (Depth First Search) använder datastrukturen Stack. | |||
| BFS kan användas för att hitta den kortaste vägen med en enda källa i en oviktad graf, eftersom vi i BFS når en punkt med minsta möjliga antal kanter från en källpunkt. | I DFS kan det hända att vi går igenom fler kanter för att nå en målpunkt från en källa. | ||
| BFS lämpar sig bättre för att söka efter hörn som ligger närmare den givna källan. | DFS lämpar sig bättre när det finns lösningar som ligger längre bort från källan. | ||
| BFS tar hänsyn till alla grannar först och lämpar sig därför inte för beslutsträd som används i spel eller pussel. | DFS lämpar sig bättre för spel- eller pusselproblem. Vi fattar ett beslut och utforskar sedan alla vägar genom detta beslut. Och om detta beslut leder till en vinstsituation slutar vi. | Tidskomplexiteten för BFS är O(V + E) när Adjacency List används och O(V^2) när Adjacency Matrix används, där V står för hörn och E står för kanter. | Tidskomplexiteten för DFS är också O(V + E) när Adjacency List används och O(V^2) när Adjacency Matrix används, där V står för vertices och E står för edges. |
Se även BFS vs DFS for Binary Tree för att se skillnaderna för en binär trädtraversal.
Article Tags :
Praktik Taggar :