Djupet-först-sökning (DFS)

Depth-first search (DFS) följer en gren så långt reglerna tillåter och återkommer sedan till återstående grenar. Det kan göras med rekursion, vars anropsstack sparar aktiva funktioner, eller med en explicit LIFO-stack. I grafer behövs visited-markering eftersom cykler och sammanlänkande vägar kan förekomma.

Följ en graf

Besökta: –

Queue: –

FöregåendeNästa stegÅterställ

Grannar behandlas i alfabetisk ordning. DFS använder omvänd push-ordning för att besöka den alfabetiskt första grannen först.

Välj DFS. Här läggs grannar på stacken i omvänd alfabetisk ordning så att den alfabetiskt första grannen tas ut först. Stacken visar noder som väntar på att behandlas, inte nödvändigtvis samma sak som rekursiva funktionsanrop. Andra grannordningar kan ge andra men fortfarande giltiga DFS-ordningar.

C# och C++

C#

C# | DFS.cs

using System.Collections.Generic;

static List<int> Dfs(IReadOnlyList<int>[] graph, int start)
{
    if ((uint)start >= (uint)graph.Length)
        throw new ArgumentOutOfRangeException(nameof(start));
    var visited = new bool[graph.Length];
    var stack = new Stack<int>();
    var order = new List<int>();
    visited[start] = true;
    stack.Push(start);
    while (stack.Count > 0)
    {
        int current = stack.Pop();
        order.Add(current);
        for (int i = graph[current].Count - 1; i >= 0; i--)
        {
            int next = graph[current][i];
            if ((uint)next >= (uint)graph.Length)
                throw new ArgumentException("Invalid neighbor index", nameof(graph));
            if (visited[next]) continue;
            visited[next] = true;
            stack.Push(next);
        }
    }
    return order;
}

C++

C++ | DFS.cpp

#include <vector>
#include <stack>
#include <stdexcept>

std::vector<int> dfs(const std::vector<std::vector<int>>& graph, int start) {
    if (start < 0 || static_cast<std::size_t>(start) >= graph.size())
        throw std::out_of_range("start");
    std::vector<bool> visited(graph.size(), false);
    std::stack<int> stack;
    std::vector<int> order;
    visited[start] = true;
    stack.push(start);
    while (!stack.empty()) {
        int current = stack.top(); stack.pop();
        order.push_back(current);
        const auto& neighbors = graph[current];
        for (auto it = neighbors.rbegin(); it != neighbors.rend(); ++it) {
            int next = *it;
            if (next < 0 || static_cast<std::size_t>(next) >= graph.size())
                throw std::out_of_range("neighbor");
            if (visited[next]) continue;
            visited[next] = true;
            stack.push(next);
        }
    }
    return order;
}

Exemplen markerar noder redan när de läggs på stacken, så samma nod inte planeras flera gånger. Rekursiv DFS markerar normalt vid inträde och undersöker varje obesökt granne direkt. I grafer med tvärkanter kan en iterativ variant med tidig markering ge annan ordning än rekursiv DFS, men båda besöker den nåbara komponenten.

Användningsområden

DFS används för nåbarhet, sammanhängande komponenter, topologisk sortering av riktade acykliska grafer och cykeldetektion med ytterligare tillstånd. I spelutveckling kan DFS kontrollera vilka rum som nås från ett visst område. DFS garanterar inte kortaste väg, även om alla kanter kostar lika mycket.

Tid och minne

För grannlistor är tiden O(V + E) för den nåbara komponenten. Visited-array och stack eller rekursionsstack kräver O(V) extraminne i värsta fall. Om besöksordningen samlas in tar resultatet ytterligare O(V). Mycket djup rekursion kan orsaka stack overflow, medan iterativ DFS undviker just begränsningen för funktionsstacken.

Frånkopplade grafer och riktning

En enda start hittar bara nåbara noder. Vill du besöka alla komponenter kan du iterera över samtliga noder och starta DFS där visited är falskt. I en riktad graf går man bara längs riktade kanter; motsatt väg behöver inte finnas.

Övning: Ändra ordningen på B:s grannar på papper. Ändras traverseringsordningen? Ändras nåbarheten? Jämför sedan BFS och DFS.

Referenser: Codecademy DFS, GeeksforGeeks DFS, Wikipedia DFS.