ABSTRACT
This chapter considers two algorithms that yield spanning trees by traversing a given connected graph from a specified vertex. The first is called Breadth-First Search and the second is called Depth-First Search. In the case that the graph represents a potential computer network, in which each edge is weighted with the cost of the link it reflects, a minimum spanning tree represents a cheapest possible connected network. If, instead, each edge is weighted with the time delay across the link it reflects, then a shortest path tree from a specified vertex represents a network with the fastest response time from the corresponding specified computer. An application of inorder traversal relates to binary search trees. The chapter shows how trees provide a valuable tool for analyzing algorithms. It provides a study of the analysis of algorithms in general. The chapter also shows how trees provide a valuable tool for analyzing algorithms.
