Prohledávání do hloubky (DFS) je základní grafový algoritmus pro procházení grafu. Tento algoritmus systematicky prochází graf od počátečního uzlu, pro dočasné ukládání nenavštívených uzlů používá zásobník.

Kroky algoritmu

  1. Všem uzlům x nastav příznak VISIT(x) = FALSE.
  2. Počátečnímu uzlu s nastav příznak VISIT(x) = TRUE.
  3. Vlož počáteční uzel na zásobník.
  4. Vezmi uzel z vrcholu zásobníku a označ jej u.
  5. Každý uzel v, do kterého vede hrana z uzlu u a jeho příznak VISIT(v) je roven FALSE, vlož na zásobník a změň jeho příznak VISIT(v) = TRUE.
  6. Krok 4 opakuj tak dlouho, dokud není zásobník prázdný.

Příklad

Mějme následující graf. Počátečním uzlem je START, sousední uzly budou na zásobník vkládány v abecedním pořadí.

diagram

Algoritmus bude postupovat v následujících krocích:

KrokZásobník (vrchol: vlevo)Navštívené uzly
1START-
2G, ESTART
3C, ESTART, G
4ESTART, G, C
5D, BSTART, G, C, E
6F, BSTART, G, C, E, D
7BSTART, G, C, E, D, F
8-START, G, C, E, D, F, B

Uzly byly navštíveny v tomto pořadí: START, G, C, E, D, F, B

diagram
diagram
diagram
diagram
diagram
diagram
diagram
diagram

Složitost

Asymptotická složitost algoritmu je € O(V+E) €, kde €V€ je počet uzlů a €E€ je počet hran.

Implementace

package graph.algorithm.traversal;

import com.google.common.base.Preconditions;
import graph.model.Graph;

import java.util.*;

/**
 * Implementation of depth-first traversal algorithm.
 */
public final class Dfs {
    /**
     * Performs a DFS walk starting from the given node.
     * @param graph graph to walk
     * @param startingNode node to start walking from (must be in the given graph)
     * @return list of nodes in order they were visited
     */
    public static <N> List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode) {
        Preconditions.checkArgument(graph.nodes().contains(startingNode));

        final Set<N> allNodes = graph.nodes();
        final int n = allNodes.size();
        final List<N> result = new ArrayList<>(n);
        final Set<N> closed = new HashSet<>(n);
        final Stack<N> open = new Stack<>();

        // initialize the stack with the root node
        open.push(startingNode);

        while (!open.isEmpty()) {
            // pop the top node
            final N active = open.pop();

            if (!closed.contains(active)) {
                // add the node to result
                result.add(active);

                // mark the node as visited
                closed.add(active);

                // add the node neighbours to the stack
                open.addAll(graph.successors(active));
            }
        }

        return result;
    }
}

Zdrojový kód Pokrytí testy