|
|
Algorithm (informal)
- Put the ending node (the root node) in the queue.
- Pull a node from the beginning of the queue and examine it.
- If the searched element is found in this node, quit the search and return a result.
- Otherwise push all the (so-far-unexamined) successors (the direct child nodes) of this node into the end of the queue, if there are any.
- If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
- Repeat from Step 2.
C implementation
Algorithm of Breadth-first search：
void BFS(VLink G[], int v) {
int w;
VISIT(v); /*visit vertex v*/
visited[v] = 1; /*mark v as visited : 1 */
ADDQ(Q,v);
while(!QMPTYQ(Q)) {
v = DELQ(Q); /*Dequeue v*/
w = FIRSTADJ(G,v); /*Find first neighbor, return -1 if no neighbor*/
while(w != -1) {
if(visited[w] == 0) {
VISIT(w); /*visit vertex v*/
ADDQ(Q,w); /*Enqueue current visited vertext w*/
visited[w] = 1; /*mark w as visited*/
}
W = NEXTADJ(G,v); /*Find next neighbor, return -1 if no neighbor*/
}
}
}
Main Algorithm of apply Breadth-first search to graph G=(V,E)：
void TRAVEL_BFS(VLink G[], int visited[], int n) {
int i;
for(i = 0; i<n; i ++) {
visited[i] = 0; /* Mark initial value as 0 */
}
for(i = 0; i<n; i ++)
if(visited[i] == 0)
BFS(G,i);
}
C++ implementation
This is the implementation of the above informal algorithm, where the "so-far-unexamined" is handled by the parent array. For actual C++ applications, see the Boost Graph Library.
Suppose we have a struct:
struct Vertex {
...
std::vector<int>out;
...
};
and an array of vertices: (the algorithm will use the indexes of this array, to handle the vertices)
std::vector<Vertex>graph(vertices);
the algorithm starts from start and returns true if there is a directed path from start to end:
bool BFS(const std::vector<Vertex>&graph, int start, int end) {
std::queue<int>next;
std::map<int,int>parent;
parent[start] = -1;
next.push(start);
while (!next.empty()) {
int u = next.front();
next.pop();
// Here is the point where you can examine the u th vertex of graph
// For example:
if (u == end) return true;
for (std::vector<int>::const_iterator j = graph[u].out.begin(); j != graph[u].out.end(); ++j) {
// Look through neighbors.
int v = *j;
if (parent.count(v) == 0) {
// If v is unvisited.
parent[v] = u;
next.push(v);
}
}
}
return false;
}
it also stores the parents of each node, from which you can get the path.
Features
- Space Complexity
Since all nodes discovered so far have to be saved, the space complexity of breadth-first search is O(|V| + |E|) where |V| is the number of nodes and |E| the number of edges in the graph. Note: another way of saying this is that it is O(BM) where B is the maximum branching factor and M is the maximum path length of the tree. This immense demand for space is the reason why breadth-first search is impractical for larger problems.
- Time Complexity
Since in the worst case breadth-first search has to consider all paths to all possible nodes the time complexity of breadth-first search is O(|V| + |E|) where |V| is the number of nodes and |E| the number of edges in the graph. The best case of this search is o(1). It occurs when the node is found at first time.