Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We estimate the expected value of various search quantities for a variety of

graph-searching methods, for example, depth-first search and breadth-first

search. Our analysis applies to both directed and undirected random graphs,

and it covers the range of interesting graph densities, including densities

at which a random graph is disconnected with a giant connected component.

We estimate the number of edges examined during the search, since this number

is proportional to the running time of the algorithm. We find that for hardly

connected graphs, all of the edges might be examined, but for denser graphs

many fewer edges are generally required. We prove that any searching algorithm

examines O(n log n) edges, if present, on all random graphs with n nodes but

not necessarily on the complete graphs.

One property of some searching algorithms is the maximum depth of the search.

In depth-first search, this depth can be used to estimate the space needed for

the recursion stack. For random graphs of any density, even for disconnected

graphs, we prove that this space is O(n). On the other hand, the depth of

breadth-first search is O(log n/log(pn)), where p is the probability of the

existence of an edge. The size of the data structure needed by any searching

algorithm is proved to be O(n). If the search terminates at a particular node,

any searching algorithm needs a data structure of size O(n), and examines

only O(n) edges.

Finally we derive similar results for variants of the above searching

algorithms, more general classes of searching algorithms, and for random

graphs with multiple edges.

These results are verified through simulations. The techniques employed to

permit simulations of big graphs (few millions of nodes) and the results

obtained are of general interest, especially to those performing similar

experiments.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/91

[2] ftp://ftp.cs.princeton.edu/techreports/1990/286.pdf