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 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 .
Code
/**
* Not discovered node
*/
private static final int FRESH = 0;
/**
* Open node
*/
private static final int OPEN = 1;
/**
* Closed node
*/
private static final int CLOSED = 2;
/**
* Breadth-first search
*
* @param graph graph to be traversed
* @param rootNr root node
* @return array of predecessors
*/
public static GraphNodeIface[] breadthFirstSearch(GraphIface graph, int rootNr) {
GraphNodeIface[] predecessors = new GraphNodeIface[graph.getVertexCount()]; //array of predecessors
int[] state = new int[graph.getVertexCount()];
for (int i = 0; i < state.length; i++) {
state[i] = FRESH;
}
state[rootNr] = OPEN; //root node is open
predecessors[rootNr] = null; //root has no predecessor
Queue<GraphNodeIface> l = new LinkedList<GraphNodeIface>(); //queue, by replacing with stack the algorithm would behave as DFS
l.add(graph.getNode(rootNr));
while (!l.isEmpty()) {
GraphNodeIface node = l.poll();
List<GraphNodeIface> successors = node.getSuccessors();
for (GraphNodeIface succ : successors) {
if (state[succ.getId()] == FRESH) { //newly discovered node
l.add(succ); //to be processed
state[succ.getId()] = OPEN;
predecessors[succ.getId()] = node;
}
}
state[node.getId()] = CLOSED;
}
return predecessors;
}
/**
* Defines basic interface for a generic graph
*
* @author Pavel Micka
*/
public interface GraphIface<ENTITY> {
/**
* Add an edge to a graph
*
* @param from source node
* @param to target node
*/
public void addEdge(int from, int to);
/**
* Get number of edges in the graph
*
* @return number of edges in the graph
*/
public int getEdgeCount();
/**
* Return vertex (node) with the given identifier
*
* @param id
* @return
*/
public GraphNodeIface getNode(int id);
/**
* Return total number of nodes (vertices)
*
* @return total number of nodes (vertices)
*/
public int getVertexCount();
/**
* Remove the edge
*
* @param from source node
* @param to target node
*/
public void removeEdge(int from, int to);
/**
* Defines basic interface for a node of a graph
*
* @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);
}
}