Programowanie breadth-first-search

16

Kiedy praktyczne jest wyszukiwanie według głębokości jako pierwszej (DFS) a wyszukiwanie według szerokości (BFS)? [Zamknięte]

Zamknięte . To pytanie jest oparte na opiniach . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby można było na nie odpowiedzieć faktami i cytatami, edytując ten post . Zamknięte 12 dni temu . Popraw to pytanie Rozumiem różnice między DFS i BFS, ale chcę wiedzieć, kiedy …

345 algorithm graph-algorithm graph-theory depth-first-search breadth-first-search

4

Najpierw szerokość a najpierw głębokość

Podczas przechodzenia przez drzewo / wykres, jaka jest różnica między Najpierw szerokość i najpierw głębokość? Wszelkie przykłady kodowania lub pseudokodu byłyby świetne.

171 algorithm depth-first-search breadth-first-search tree-traversal

21

Rekurencyjne wykonywanie pierwszego przeszukiwania wszerz

Załóżmy, że chcesz zaimplementować rekurencyjne przeszukiwanie wszerz drzewa binarnego . Jak byś się do tego zabrał? Czy jest możliwe używanie tylko stosu wywołań jako pamięci dyskowej?

152 algorithm breadth-first-search

8

Dlaczego złożoność czasowa zarówno DFS, jak i BFS O (V + E)

Podstawowy algorytm dla BFS: set start vertex to visited load it into queue while queue not empty for each edge incident to vertex if its not visited load into queue mark vertex Więc myślę, że złożoność czasowa byłaby następująca: v1 + (incident edges) + v2 + (incident edges) + .... …

137 algorithm time-complexity graph-theory breadth-first-search

7

Jak działa wyszukiwanie wszerz, gdy szukasz najkrótszej ścieżki?

Zrobiłem kilka badań i wydaje mi się, że brakuje mi jednej małej części tego algorytmu. Rozumiem, jak działa wyszukiwanie wszerz, ale nie rozumiem, jak dokładnie doprowadzi mnie do określonej ścieżki, w przeciwieństwie do zwykłego informowania mnie, gdzie może przejść każdy węzeł. Myślę, że najłatwiejszym sposobem wyjaśnienia mojego pomieszania jest podanie …

129 java shortest-path breadth-first-search

4

Po co używać algorytmu Dijkstry, skoro Breadth First Search (BFS) może zrobić to samo szybciej?

Oba mogą być użyte do znalezienia najkrótszej ścieżki z jednego źródła. BFS wbiega O(E+V), a Dijkstra wbiega O((V+E)*log(V)). Poza tym widziałem, że Dijkstra używał bardzo podobnie jak w protokołach routingu. Zatem po co używać algorytmu Dijkstry, skoro BFS może zrobić to samo szybciej?

110 algorithm graph dijkstra breadth-first-search

5

Jak prześledzić ścieżkę w przeszukiwaniu wszerz?

Jak prześledzić ścieżkę przeszukiwania wszerz, tak jak w poniższym przykładzie: Jeśli szukasz klucza 11, zwróć najkrótszą listę łączącą od 1 do 11. [1, 4, 7, 11]

104 python algorithm graph breadth-first-search

9

Dlaczego DFS, a nie BFS do znajdowania cyklu na wykresach

Przeważnie DFS służy do znajdowania cyklu na wykresach, a nie BFS. Jakieś powody? Oba mogą sprawdzić, czy węzeł został już odwiedzony podczas przeglądania drzewa / wykresu.

85 algorithm tree graph-theory depth-first-search breadth-first-search

Pytania otagowane jako breadth-first-search