We present distributed algorithms for constructing a depth-first search tree for a communication network which are more efficient than previous methods. Our algorithms require 21VI -2 messages and units of time in the worst case, where IV1 is the number of sites in the network, and as little as IV1 messages and time units in the best case. The actual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is 1 VI ( 1 + r) in the worst case, where 0 < r < 1 and the value of r depends on the topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, r = 0 and our basic algorithm requires IV\ messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best case bound for other topologies. The worst case bound, which has r = 1 -2/lVl, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.