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 $ \\{ 0,1 \\} ^ {n} $. (Two $ 0 $- $ 1 $ vectors of length $ n $ 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 $ \Gamma = ( V,E ) $ be a finite oriented graph (cf. Graph, oriented). For each $ v \in V $, let $ A ( v ) $ be the set of edges (arcs) issuing from $ v $. For instance, in Fig.a1, $ A ( 1 ) = \\{ ( 1,2 ) , ( 1,4 ) \\} $, $ A ( 3 ) = \\{ ( 3,6 ) \\} $, $ A ( 7 ) = \emptyset $.

Figure: s110070a

It is assumed that the sets $ A ( v ) $, $ v \in V $, are given some fixed total order (cf. also Totally ordered set) for all $ v $. The following algorithm picks out all nodes in $ \Gamma $ that are reachable from a source node $ s $ by means of a directed path. These nodes will be marked. Central to the algorithm is a certain list $ L $, 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 $ s $;

set $ L = \\{ s \\} $;

as long as $ L $ is non-empty, run the following iterative procedure:

choose a node $ i \in L $;

select the first oriented edge $ ( i,j ) \in A ( i ) $ that runs (from $ i $) to an unmarked node $ j $( if any);

mark the node $ j $;

define the function $ { \mathop{\rm revp} } $ on $ j $ as $ { \mathop{\rm revp} } ( j ) = i $;

add $ j $ to $ L $;

if there is no $ ( i,j ) \in A ( i ) $ that runs to an unmarked node $ j $, remove $ i $ from $ L $.

stop when $ L $ is empty.

The algorithm does not yet specify how to select a node from $ L $. If $ L $ is treated as a queue, i.e., the node selected is the one that has been longest in $ L $( first-in-first-out) the result is breadth-first search. On the other hand, if $ L $ is treated as a stack, i.e., the node selected is the one that was last added to $ L $( 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 $ A ( v ) $ also matters, but not as much.

The edges picked out by the function $ { \mathop{\rm revp} } $( reverse path), i.e., the edges $ ( { \mathop{\rm revp} } ( j ) ,j ) $ form an oriented tree comprising the reachable nodes from the source node $ s $.

The results of the algorithm in four cases are given below for the case of Fig.a1.

<tbody> </tbody> | search | marking | oriented

|
|

method | sequence | tree
|  |
breadth first, | 1 2 4 3 5 6 7 |

lexicographic |  |
order |  |
on the $ A ( i ) $  |  |
|  |
breadth first, | 1 4 2 5 3 7 6 |

reverse |  |
lexicographic |  |
order |  |
on the $ A ( i ) $  |  |
|  |
depth first | 1 2 3 6 5 7 4 |

lexicographic |  |
order |  |
on the $ A ( i ) $  |  |
|  |
depth first | 1 4 5 7 2 3 6 |

reverse |  |
lexicographic |  |
order |  |
on the $ A ( i ) $  |  |

There is an obvious analogous search algorithm for non-oriented graphs. These algorithms run in $ O ( \\# V + \\# E ) $ time.

#### References[edit]

[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)