Breadth-first search

Breadth-first search (English breadth-first search, BFS ) is a procedure in computer science, for searching and traversing the nodes of a graph. It is among the uninformed searches. In contrast to the depth-first search, all nodes are first trod that are reachable from the output node. Only after succeeding node be pursued ( see figure).

Operation

Breadth-first search is an uninformed search, which searches through expansion of each level of the graph, starting from the start node to the graph in the width for an element.

First, a starting node is selected. From this node from each edge is now viewed and tested whether the opposite node was already discovered or the searched element. If this is not the case, then the corresponding node will be stored in a queue and processed in the next step. It should be noted that breadth-first search always processed first, all subsequent nodes directly, and not as the depth-first search follows a path into the depths. After all of the edges of the output node were considered, the first node of the queue is removed and the process repeated.

Algorithm ( informal)

  • If the search item was found, break off the search and deliver " found."
  • Otherwise, hang all previously unmarked successor of this node that are not still in the queue at the end of the queue.

Algorithm (formal)

The following algorithms are formulated to be understood as pseudo code and enter for readability only whether the destination node is found. More important in applications information - such as the current path level or the current search path - could be additionally inserted.

Recursive formulated:

BFS ( start_node, goal_node ) {    return BFS ' ({ start_node }, ∅, goal_node ); } BFS ' ( fringe, visited, goal_node ) {    if ( fringe == ∅ ) {      Not found / / node      return false;    }    if ( goal_node ∈ fringe ) {      return true;    }    return BFS ' ({ child | x ∈ fringe, child ∈ expand ( x) } \ visited, visited ∪ fringe, goal_node ); } As loop formulated:

BFS ( start_node, goal_node ) {   for ( all nodes i) visited [i ] = false; / / Initially no nodes are visited   queue.push ( start_node ); Begin / / with start node   visited [ start_node ] = true;   while (! queue.empty ()) {/ / while queue is not empty    node = queue.pop (); Take / / first element of the queue    if ( node == goal_node ) {     return true; / / Test if destination node found    }    foreach (child in expand ( node) ) { / / all successor nodes, ...     if ( visited [child ] == false) {/ / ... which have not yet visited ...      queue.push ( child); / / ... Add to queue ...      visited [child ] = true; Mark saw / / ... and as already     }    }   }   return false; / / Node can not be reached } properties

Denote the number of the node (vertex ), and the number of edges (EDGE) of the graph. Memory consumption and running time of the algorithm in Landau notation specified.

Memory consumption

Since all previously discovered nodes are stored is the memory usage of breadth-first search. Thus, the breadth-first search is unsuitable due to the immense space consumption for larger problems. A breadth-first search similar method, but with a significantly lower memory consumption, the iterative deepening search.

Term

Since in the worst case, all possible paths must be considered at all possible nodes, the running time of breadth-first search.

Completeness

If in each node are only finitely many alternatives, the breadth-first search is complete. This means that if a solution exists, it is also found. This is regardless of whether the underlying graph is finally or not. If, however, there is no solution, the breadth-first search diverges in an infinite graph.

Optimality

Breadth-first search is in general optimal, as always, the result is found with the shortest path to the start node. Performs one edge weights a, so must be the result, which is closest to the start node, not necessarily the result with the lowest path cost. This problem bypassing it by expanding the breadth-first search for the uniform-cost search. However, if all edge weights are equivalent, the breadth-first search is optimal, since in this case the solution that is closest to the output node, the solution with the lowest cost.

The uniform-cost search (English uniform -cost search, UCS) is an extension of breadth-first search for graphs with weighted edges. ( Therefore, and is usually a priority queue ( engl. priority queue ) implemented in all unvisited neighbors already visited nodes are managed with the path length as the key ) The algorithm visits nodes in order of increasing path cost from the root node. The optimality is guaranteed only for non-negative edge weights.

Application

Breadth-first search can be used for many problems in graph theory. Some are:

  • Find all nodes within a connected component
  • Collect between two nodes u and w a shortest path ( unweighted edges)
  • Shortest -circle problem
Ron Rivest
143956
de