Breadth-first search
Breadth-first search - number denotes a level, in which the node was discovered

Breadth-first search is a fundamental graph algorithm, which is used for graph traversal. Its principles are used in many other algorithms such as Jarník-Prim algorithm or Dijkstra's algorithm.

Description

Breadth-first search (BFS) uses a queue data structure for storing nodes, which are not yet processed. In the initialization phase the algorithm starts at an arbitrary node and places it into the queue.

Than BFS processes the head H of the queue and inserts all its unprocessed descendants into the queue. BFS repeats this step till the queue is not empty. This procedure guarantees that nodes are processed in the order given by their distance (number of edges) from the starting node. We call the resulting tree representing distances from the root node BF-Tree.

Relation to depth-first search

The BFS procedure can be easily modified to work in a depth-first search (DFS) manner. The only difference between these two algorithms is that DFS uses a stack for storing unprocessed nodes.

Complexity

Because each node and each edge is visited exactly once, the asymptotic complexity is O(|E| + |N|).


Code

view source
print?
001./**
002. * Not discovered node
003. */
004.private static final int FRESH = 0;
005./**
006. * Open node
007. */
008.private static final int OPEN = 1;
009./**
010. * Closed node
011. */
012.private static final int CLOSED = 2;
013. 
014./**
015. * Breadth-first search
016. *
017. * @param graph graph to be traversed
018. * @param rootNr root node
019. * @return array of predecessors
020. */
021.public static GraphNodeIface[] breadthFirstSearch(GraphIface graph, int rootNr) {
022.    GraphNodeIface[] predecessors = new GraphNodeIface[graph.getVertexCount()]; //array of predecessors
023.    int[] state = new int[graph.getVertexCount()];
024.    for (int i = 0; i < state.length; i++) {
025.        state[i] = FRESH;
026.    }
027.    state[rootNr] = OPEN; //root node is open
028.    predecessors[rootNr] = null; //root has no predecessor
029. 
030.    Queue<GraphNodeIface> l = new LinkedList<GraphNodeIface>(); //queue, by replacing with stack the algorithm would behave as DFS
031.    l.add(graph.getNode(rootNr));
032. 
033.    while (!l.isEmpty()) {
034.        GraphNodeIface node = l.poll();
035.        List<GraphNodeIface> successors = node.getSuccessors();
036.        for (GraphNodeIface succ : successors) {
037.            if (state[succ.getId()] == FRESH) { //newly discovered node
038.                l.add(succ); //to be processed
039.                state[succ.getId()] = OPEN;
040.                predecessors[succ.getId()] = node;
041.            }
042.        }
043.        state[node.getId()] = CLOSED;
044.    }
045.    return predecessors;
046.}
047. 
048./**
049. * Defines basic interface for a generic graph
050. *
051. * @author Pavel Micka
052. */
053.public interface GraphIface<ENTITY> {
054. 
055.    /**
056.     * Add an edge to a graph
057.     *
058.     * @param from source node
059.     * @param to target node
060.     */
061.    public void addEdge(int from, int to);
062. 
063.    /**
064.     * Get number of edges in the graph
065.     *
066.     * @return number of edges in the graph
067.     */
068.    public int getEdgeCount();
069. 
070.    /**
071.     * Return vertex (node) with the given identifier
072.     *
073.     * @param id
074.     * @return
075.     */
076.    public GraphNodeIface getNode(int id);
077. 
078.    /**
079.     * Return total number of nodes (vertices)
080.     *
081.     * @return total number of nodes (vertices)
082.     */
083.    public int getVertexCount();
084. 
085.    /**
086.     * Remove the edge
087.     *
088.     * @param from source node
089.     * @param to target node
090.     */
091.    public void removeEdge(int from, int to);
092. 
093.    /**
094.     * Defines basic interface for a node of a graph
095.     *
096.     * @param <ENTITY>
097.     */
098.    public interface GraphNodeIface<ENTITY> {
099. 
100.        /**
101.         * @return the id
102.         */
103.        public int getId();
104. 
105.        /**
106.         * @return the successors
107.         */
108.        public List<GraphNodeIface> getSuccessors();
109. 
110.        /**
111.         * @return the value
112.         */
113.        public ENTITY getValue();
114. 
115.        /**
116.         * @param value the value to set
117.         */
118.        public void setValue(ENTITY value);
119.    }
120.}







  1. Home
  2. Graph algorithms
       
 

Place for your banner

Here is the position ready for our customer's banners.