Prohledávání do šířky (BFS) 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á frontu.

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 do fronty.
  4. Vezmi první uzel z fronty 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, přidej na konec fronty a změň jeho příznak VISIT(v) = TRUE.
  6. Krok 4 opakuj tak dlouho, dokud není fronta prázdná.

Příklad

Mějme následující graf. Počátečním uzlem je START, sousední uzly budou do fronty přidávány v abecedním pořadí.

diagram

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

KrokFronta (první prvek: vlevo)Navštívené uzly
1START-
2E, GSTART
3G, B, C, DSTART, E
4B, C, DSTART, E, G
5C, DSTART, E, G, B
6DSTART, E, G, B, C
7FSTART, E, G, B, C, D
8-START, E, G, B, C, D, F

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

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 breadth-first traversal algorithm.
 */
public final class Bfs {
    /**
     * Performs a BFS 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> traverseBreadthFirst(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 Queue<N> open = new LinkedList<>();

        // initialize the queue with the root node
        open.add(startingNode);

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

            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 queue
                open.addAll(graph.successors(active));
            }
        }

        return result;
    }
}

Zdrojový kód Pokrytí testy