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 , protože každou hranu a každý uzel projde právě jednou.
Kód
/**
* 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.