Breadth First Search
BFS oznacza Breadth First Search, jest opartą na wierzchołkach techniką znajdowania najkrótszej ścieżki w grafie. Wykorzystuje ona strukturę danych kolejki, która działa na zasadzie „pierwsze weszło, pierwsze wyszło”. W BFS, jeden wierzchołek jest wybierany na raz, kiedy jest odwiedzany i oznaczany, wtedy jego sąsiednie wierzchołki są odwiedzane i przechowywane w kolejce. Jest to wolniejsze niż DFS.
Ex-
A / \ B C / / \ D E F
Output is:
A, B, C, D, E, F
Depth First Search
DFS oznacza Depth First Search jest techniką opartą na krawędziach. Używa struktury danych Stack, wykonuje dwa etapy, pierwsze odwiedzone wierzchołki są wypychane na stos, a drugie jeśli nie ma wierzchołków to odwiedzone wierzchołki są usuwane.
Ex-
A / \ B C / / \ D E F
Output is:
A, B, D, C, E, F
BFS vs DFS
| S.NO | BFS | DFS |
|---|---|---|
| BFS oznacza Breadth First Search. | DFS oznacza Depth First Search. | |
| BFS(Breadth First Search) używa struktury danych Queue do znalezienia najkrótszej ścieżki. | DFS(Depth First Search) używa struktury danych Stack. | |
| BFS może być użyty do znalezienia pojedynczego źródła najkrótszej ścieżki w grafie nieważonym, ponieważ w BFS, osiągamy wierzchołek z minimalną liczbą krawędzi od wierzchołka źródłowego. | W DFS, możemy przejść przez więcej krawędzi, aby dotrzeć do wierzchołka docelowego ze źródła. | |
| BFS jest bardziej odpowiedni do wyszukiwania wierzchołków, które są bliżej danego źródła. | DFS jest bardziej odpowiedni, gdy istnieją rozwiązania z dala od źródła. | |
| BFS rozważa najpierw wszystkich sąsiadów i dlatego nie nadaje się do drzew decyzyjnych używanych w grach i łamigłówkach. | DFS jest bardziej odpowiednie dla problemów z grami lub łamigłówkami. Podejmujemy decyzję, a następnie badamy wszystkie ścieżki poprzez tę decyzję. I jeśli ta decyzja prowadzi do sytuacji wygranej, zatrzymujemy się. | Złożoność czasowa BFS wynosi O(V + E), gdy używana jest lista adjacency i O(V^2), gdy używana jest macierz adjacency, gdzie V oznacza wierzchołki, a E oznacza krawędzie. | Złożoność czasowa DFS jest również O(V + E), gdy używana jest Lista Adjacency i O(V^2), gdy używana jest Macierz Adjacency, gdzie V oznacza wierzchołki, a E oznacza krawędzie. |
Proszę również zobaczyć BFS vs DFS dla drzewa binarnego dla różnic dla Traversal drzewa binarnego.