Depth-first and breadth-first search—the standard procedures to traverse graphs—are the basis for many graph algorithms such as the construction of spanning trees and rings and the search for shortest paths. Because of their importance, in this chapter, techniques for the construction of algorithms for depth- and breadth-first search in distributed graphs are developed. They supply the corresponding spanning trees, and depth-first search also makes it possible to find circles. In many textbooks on distributed programming, only the principles of the algorithms are presented, without going into concrete realizations. The considerable effort for that in this chapter shows that this is by no means negligible.