Prohledávání do šířky

Prohledávání do šířky - čísla označují vlnu, ve které je uzel zpracován

Prohledávání do šířky (breadth-first search, BFS) je jedním ze základních grafových algoritmů, který slouží k průchodu daného grafu. Jeho principy jsou základem pro další algoritmy, jako je například Jarník-Primův algoritmus nebo Dijkstrův algoritmus.

Princip

Při prohledávání do šířky začneme procházet graf z libovolného uzlu. Tento uzel zpracujeme a při objevení jeho dosud nenalezených potomků tyto uložíme do fronty a postupně zpracováváme stejným způsobem. Takto postupujeme, dokud není fronta prázdná.

Díky ukládání do fronty dochází k procházení grafu po vlnách – uzly jsou zpracovávány v pořadí daném jejich vzdáleností od kořene.

Výstupem algoritmu je strom prohledávání do hloubky obsahující všechny uzly dosažitelné z výchozího uzlu - tzv. BF-strom. BF-strom je stromem nejkratších cest z daného uzlu ve smyslu počtu hran.

Složitost

Za předpokladu, že je složitost přístupu k potomkům daného uzlu konstantní, stejně jako složitost uložení a výběru z fronty, tak je asymptotická složitost celého algoritmu $O(\\vert U \\vert + \\vert H \\vert)$ , protože každou hranu a každý uzel projde právě jednou.

Kód

Java

/**
 * Dosud neobjeveny uzel
 */
private static final int FRESH = 0;
/**
 * Otevreny uzel
 */
private static final int OPEN = 1;
/**
 * Uzavreny uzel
 */
private static final int CLOSED = 2;
 
/**
 * Prohledavani do sirky
 *
 * @param graph graf k prohledani
 * @param rootNr cislo uzlu, ktery je korenem
 * @return pole predchudcu
 */
public static GraphNodeIface[] breadthFirstSearch(GraphIface graph, int rootNr) {
    GraphNodeIface[] predecessors = new GraphNodeIface[graph.getVertexCount()]; //pole predchudcu
    int[] state = new int[graph.getVertexCount()];
    for (int i = 0; i < state.length; i++) {
        state[i] = FRESH;
    }
    state[rootNr] = OPEN; //koren je otevreny
    predecessors[rootNr] = null; //koren nema predky
 
    Queue<GraphNodeIface> l = new LinkedList<GraphNodeIface>(); //fronta - pokud zde frontu nahradime zasobnikem, tak ziskame prohledavani do hloubky
    l.add(graph.getNode(rootNr));
 
    while (!l.isEmpty()) {
        GraphNodeIface node = l.poll();
        List<GraphNodeIface> successors = node.getSuccessors();
        for (GraphNodeIface succ : successors) { //potomci zpracovavaneho uzlu
            if (state[succ.getId()] == FRESH) { //byl prave objeven
                l.add(succ); //pridame ke zpracovani
                state[succ.getId()] = OPEN;
                predecessors[succ.getId()] = node;
            }
        }
        state[node.getId()] = CLOSED;
    }
    return predecessors;
}
 
/**
 * Operace, ktere by mel splnovat graf
 *
 * @author Pavel Micka
 */
public interface GraphIface<ENTITY> {
  
    /**
     * Prida hranu do grafu
     *
     * @param from uzel, ze ktereho hrana vychazi
     * @param to uzel, do ktereho hrana vede
     */
    public void addEdge(int from, int to);
 
    /**
     * Vrati pocet hran grafu
     *
     * @return pocet hran grafu
     */
    public int getEdgeCount();
 
    /**
     * Vrati uzel s danym identifikatorem
     *
     * @param id
     * @return
     */
    public GraphNodeIface getNode(int id);
 
    /**
     * Vrati pocet vrcholu grafu
     *
     * @return pocet vrcholu grafu
     */
    public int getVertexCount();
 
    /**
     * Odstrani hranu, v pripade vicenasobneho vyskytu odstrani prvni vyskyt
     *
     * @param from uzel, ze ktereho hrana vychazi
     * @param to uzel, do ktereho hrana vede
     */
    public void removeEdge(int from, int to);
 
    /**
     * Operace, ktere by mel splnovat uzel grafu
     *
     * @param <ENTITY>
     */
    public interface GraphNodeIface<ENTITY> {
 
        /**
         * @return the id
         */
        public int getId();
 
        /**
         * @return the successors
         */
        public List<GraphNodeIface> getSuccessors();
 
        /**
         * @return the value
         */
        public ENTITY getValue();
 
        /**
         * @param value the value to set
         */
        public void setValue(ENTITY value);
    }
}

Literatura

KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.

Princip

Složitost

Kód

Literatura

Doporučujeme