Unterschied zwischen BFS und DFS

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Repräsentative Methoden zum Untersuchen eines Diagramms sind BFS und DFS. Beide folgen nicht besuchten Scheitelpunkten, jedoch in unterschiedlicher Reihenfolge.

BFS

Die Breitensuche führt eine umfassende Suche durch, beginnend mit dem Scheitelpunkt, der dem Startpunkt am nächsten liegt. Verwenden Sie die Warteschlange.

std::queue<int> Open;
std::vector<bool> Visited(NodeCount, false);

Open.push(Start);
Visited[Start] = true;

while (!Open.empty())
{
    const int Current = Open.front();
    Open.pop();

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            Visited[Next] = true;
            Open.push(Next);
        }
    }
}

Wenn alle Kanten die gleichen Kosten haben, kann BFS vom Startpunkt aus den Pfad mit den wenigsten Kanten finden.

DFS

Die Tiefensuche geht den gesamten Weg entlang und kehrt dann zurück. Verwenden Sie rekursive Aufrufe oder Stack.

void DFS(int Current)
{
    Visited[Current] = true;

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            DFS(Next);
        }
    }
}

Es wird häufig in Verbindungselementen, Zykluserkennung und Backtracking-Strukturen verwendet. Wenn das Diagramm sehr tief ist, kann der rekursive Stack überlaufen. Erwägen Sie daher die Implementierung eines expliziten Stacks.

BFS ist nicht unbedingt besser oder DFS ist nicht unbedingt schneller. Ihre Wahl hängt davon ab, ob Sie eine genaue Antwort benötigen, ob Sie den Pfad gründlich testen müssen und wie groß Ihr Gedächtnis und die Diagrammtiefe sind.