Prohledávání do šířky

Pořadí v jakém je přistupováno k vrcholům

Prohledávání do šířky (anglicky Breadth-first search, zkráceně BFS) je grafový algoritmus, který postupně prochází všechny vrcholy v dané komponentě souvislosti. Algoritmus nejprve projde všechny sousedy startovního vrcholu, poté sousedy sousedů atd. až projde celou komponentu souvislosti.

Pseudokód

function breadthFirstSearch (Start, Goal) { 
    enqueue(Queue,Start)
    while notEmpty(Queue) {
        Node := dequeue(Queue)
        if Node = Goal
            return Node  
       
        for each Child in Expand(Node) {
            if notVisited(Child) {
                setVisited(Child)
                enqueue(Queue, Child)
            }
        }
    }
}

Efektivita

Asymptotická časová složitost algoritmu je O(|V| + |E|), kde V je množina vrcholů a E je množina hran grafu, protože algoritmus navštíví každý vrchol a každou hranu právě jednou. Paměťová složitost je také O(|V| + |E|).

Související články

• Prohledávání do hloubky

Externí odkazy

• Popis a implementace v ActionScriptu
• Animace běhu algoritmus
• Implementace v Pythonu