6. Minimum Spanning Trees
Robert Endre Tarjan · Society for Industrial and Applied Mathematics eBooks · 1983
6.1. The greedy method. In the last half of this book we shall use the data structures developed in the first half to solve four classical problems in network optimization. A network is a graph, either undirected or directed, each of whose edges has an associated real number. The object of a network optimization problem is to find a subgraph of a given network that has certain specified properties and that minimizes (or maximizes) some function of the edge numbers. In this chapter we shall study one of the simplest problems of network optimization, the minimum spanning tree problem: given a connected undirected graph each of whose edges has a real-valued cost, find a spanning tree of the graph whose total edge cost is minimum. We shall denote the cost of an edge e={v,w} by cost (e) or, to avoid extra brackets, by cost (v, w).