Search algorithm
on a graph, graph search
An algorithm that tries to find all nodes in a network or graph that satisfy a given property. Such algorithms are also used, e.g., to optimize a function on a graph or network or on a set which can easily be turned into a graph, such as . (Two
-
vectors of length
are joined if an only if they differ in precisely one coordinate, yielding a hypercube.) Thus, these are definite relations and similarities between graph search and search theory as a systematic optimization technique (of enumeration type) [a3]. See [a4] for a very complete overview of global optimization (from the search point of view, including random search).
Two of the most often used search techniques in graphs or networks are depth-first search and breadth-first search. Let be a finite oriented graph (cf. Graph, oriented). For each
, let
be the set of edges (arcs) issuing from
. For instance, in Fig.a1,
,
,
.
Figure: s110070a
It is assumed that the sets ,
, are given some fixed total order (cf. also Totally ordered set) for all
. The following algorithm picks out all nodes in
that are reachable from a source node
by means of a directed path. These nodes will be marked. Central to the algorithm is a certain list
, which can be seen as a sort of wave front indicating the boundary of the spreading blob of marked points:
unmark all points;
mark the source node ;
set ;
as long as is non-empty, run the following iterative procedure:
choose a node ;
select the first oriented edge that runs (from
) to an unmarked node
(if any);
mark the node ;
define the function on
as
;
add to
;
if there is no that runs to an unmarked node
, remove
from
.
stop when is empty.
The algorithm does not yet specify how to select a node from . If
is treated as a queue, i.e., the node selected is the one that has been longest in
(first-in-first-out) the result is breadth-first search. On the other hand, if
is treated as a stack, i.e., the node selected is the one that was last added to
(last-in-first-out) the result is depth-first search.
Figure: s110070b
For an oriented tree as in Fig.a2 (downwards oriented), starting at the indicated node, breadth-first search will first pick the three children of the node indicated (in some order) and then will proceed to the next layer. Depth-first search will first pick a maximal downward chain (maximal in the sense that it ends at a leaf, not necessarily maximal in length) and then go back to another child of the last branching node in that chain.
The order which is used on the edge sets also matters, but not as much.
The edges picked out by the function (reverse path), i.e., the edges
form an oriented tree comprising the reachable nodes from the source node
.
The results of the algorithm in four cases are given below for the case of Fig.a1.'
<tbody> </tbody>
|
There is an obvious analogous search algorithm for non-oriented graphs. These algorithms run in time.
References
[a1] | R.K. Ahuja, T.L. Magnanti, J.B. Orlin, "Network flows" G.L. Nemhauser (ed.) A.H.G. Rinnooy Kan (ed.) M.J. Todd (ed.) , Optimization , North-Holland (1991) pp. 211–370 |
[a2] | H.M. Salkin, "Integer programming" , Addison-Wesley (1975) |
[a3] | C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982) |
[a4] | A.A. Zhigljavsky, "Theory of global random search" , Kluwer Acad. Publ. (1991) (In Russian) |
Search algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Search_algorithm&oldid=48636