Prohledávání do šířky

    /**
     * Dosud neobjeveny uzel
     */
    private static final int FRESH = 0;
    /**
     * Otevreny uzel
     */
    private static final int OPENED = 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] = OPENED; //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()] = OPENED;
                    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);
    }
}