wake-up-neo.net

Wie kann ich mir merken, welche Datenstrukturen von DFS und BFS verwendet werden?

Ich vermische immer, ob ich einen Stapel oder eine Warteschlange für DFS oder BFS benutze. Kann jemand bitte eine Vorstellung davon geben, wie man sich daran erinnert, welcher Algorithmus welche Datenstruktur verwendet?

20
captcadaver

Zeichnen Sie ein kleines Diagramm auf ein Blatt Papier und denken Sie darüber nach, in welcher Reihenfolge Knoten in jeder Implementierung verarbeitet werden. Wie unterscheidet sich die Reihenfolge, in der Sie auf die Knoten treffen, und die Reihenfolge, in der Sie die Knoten verarbeiten, zwischen den Suchvorgängen?

Einer von ihnen verwendet einen Stack (Tiefe zuerst) und der andere eine Warteschlange (Breite zuerst) (zumindest für nicht rekursive Implementierungen).

21
James McNellis

Warteschlange kann im Allgemeinen als horizontal in der Struktur, d.h. Breite/Breite , bezeichnet werden -BFS, während

Stack wird als vertikale Struktur visualisiert und hat somit Tiefe -DFS.

51

BFS erforscht/verarbeitet zuerst die nächstgelegenen Scheitelpunkte und bewegt sich dann von der Quelle weg nach außen. Aus diesem Grund möchten Sie eine Datenstruktur verwenden, die bei Abfrage das älteste Element enthält, basierend auf der Reihenfolge, in der sie eingefügt wurden. In diesem Fall benötigen Sie eine Warteschlange, da sie First-In-First-Out (FIFO) ist. Während eine DFS zuerst entlang jedes Zweigs und dann erst nach Bracktracks untersucht. Dafür funktioniert ein Stack besser, da er LIFO ist (Last-In-First-Out).

26
Lizz In

Ich erinnere mich daran, indem ich Barbecue im Kopf habe. Barbecue beginnt mit einem 'B' und endet mit einem Sound wie 'q', also BFS -> Queue und die restlichen DFS -> Stack.

23
kawadhiya21

Nimm es in alphabetischer Reihenfolge ...

.... B (BFS) ..... C ...... D (DFS) ....

.... Q (Warteschlange) ... R ...... S (Stapel) ...

6

BFS verwendet immer Warteschlange, DFS verwendet Stack-Datenstruktur. Wie die vorigen Erklärungen zeigen, verwendet DFS Backtracking. Denken Sie daran, dass das Zurückverfolgen nur durch Stapel erfolgen kann. 

5
ashutosh

Die Tiefensuche verwendet eine Stack, um sich zu merken, wohin sie gehen soll, wenn sie eine Sackgasse erreicht. 

DFSS

2

Bfs; Breite => Warteschlange

Dfs; Tiefe => Stapel

Beziehen Sie sich auf ihre Struktur

2
Subrato

Sie können sich daran erinnern, indem Sie ein Akronym erstellen

BQDS

Schöne Königin hat Sünden erledigt.

In Hindi हुरानी क्यु र्दहा

1
  1. Stack (Last In First Out, LIFO). Bei DFS rufen wir es so weit wie möglich vom Stamm zum weitesten Knoten ab. Dies ist die gleiche Idee wie bei LIFO.

  2. Warteschlange (First In First Out, FIFO). Für BFS rufen wir es eine Ebene nach der anderen ab, nachdem wir die obere Ebene des Knotens besucht haben, wir besuchen die untere Ebene des Knotens. Dies ist dieselbe Idee wie beim FIFO.

1

Ein leichter Weg, sich vor allem für junge Studenten zu erinnern, ist die Verwendung eines ähnlichen Akronyms:

BFS => Boy FriendS in der Warteschlange (offenbar für beliebte Damen). 

DFS ist anders (Stack).

1
Hongyu Zhang

Erinnere mich an nichts.

Angenommen, die für die Suche verwendete Datenstruktur lautetX:

Breite zuerst = Die zuvor eingegebenen KnotenXmüssen zuerst im Baum generiert werden: X ist eine Warteschlange.

Tiefe zuerst = Eingegebene KnotenXspäter müssen zuerst im Baum generiert werden: X ist ein Stapel.

In Kürze: Stack ist Last-In-First-Out (DFS). Die Warteschlange ist First-In-First-Out (BFS).

0
M-J

Ich möchte diese Antwort teilen: https://stackoverflow.com/a/20429574/3221630

Bei Verwendung von BFS und Ersetzen einer Warteschlange durch einen Stapel wird die gleiche Besuchsreihenfolge von DFS reproduziert. Dabei wird mehr Speicherplatz als der tatsächliche DFS-Algorithmus benötigt.

0
arboreal84