breadth first search

(redirected from Breadth-first search)
Also found in: Wikipedia.

breadth first search

(algorithm)
A graph search algorithm which tries all one-step extensions of current paths before trying larger extensions. This requires all current paths to be kept in memory simultaneously, or at least their end points.

Opposite of depth-first search. See also best first search.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
Peng, "Virtual network embedding algorithm based on breadth-first search," Journal of Sichuan university (engineering science edition), vol.
Nodes are classified and ranked by breadth-first search; then the total minimal cut sets are traversed out by replacing high graded nodes with low graded nodes.
Techniques such as Random Walk [5], Restricted Random Walk [6], Breadth-First Search [7], Intelligent BFS [8], Depth-First Search [9], Adaptive Probabilistic Search [10], Blackboard Resource Discovery Mechanism [11] are explained briefly in the following subsections.
We design algorithms based on the Dijkstra and breadth-first search algorithms, propose an efficient pruning algorithm for breadth-first search, and analyze their performance of number of iterations and I/O cost.
Currently implemented algorithms include Breadth-First Search (BFS), Page Rank, Single Source Shortest Paths (SSSP), connected components, and both exact and approximate betweenness centrality.
Search-level control strategy was introduce to integrate the Breadth-First Search method (BFS) and Depth-First Search method (DFS).
3 Breadth-first Search algorithm Select start node repeat calculate: diff =quantity - [SIGMA] node if (diff==0) then found solution else for node = 1 ...
It can be solved with conventional search, such as breadth-first search, by finding a shortest path every time some edge costs change.
The algorithms tested were the breadth-first search, Dijsktra's algorithm, the best-first search, and two [A.sup.*] algorithms (the two had differences in their distance estimates).
We first use a breadth-first search strategy to find all possible machine assignments for machine types with multiple copies.