tailieunhanh - Data Structures & Algorithms in Java PHẦN 10

Thuật toán để xây dựng cây bao trùm tối thiểu là một chút tham gia, vì vậy chúng tôi sẽ giới thiệu nó bằng cách sử dụng một tương tự liên quan đến nhân viên truyền hình cáp. Bạn là một nhân viên quản lý, tất nhiên, và cũng có những khảo sát khác nhau. Một thuật toán máy tính | Figure The GraphW Workshop applet Now find this graph s minimum spanning tree by stepping through the algorithm with the Tree key. The result should be the minimum spanning tree shown in Figure . Figure The minimum spanning tree The applet should discover that the minimum spanning tree consists of the edges AD AB BE EC and CF for a total edge weight of 28. The order in which the edges are specified is unimportant. If you start at a different vertex you will create a tree with the same edges but in a different order. Send Out the Surveyors The algorithm for constructing the minimum spanning tree is a little involved so we re going to introduce it using an analogy involving cable TV employees. You are one employee a manager of course and there are also various surveyors. A computer algorithm unless perhaps it s a neural network doesn t know about all the data in a given problem at once it can t deal with the big picture. It must acquire the data little by little modifying its view of things as it goes along. With graphs algorithms tend to start at some vertex and work outward acquiring data about nearby vertices before finding out about vertices farther away. We ve seen examples of this in the depth-first and breadth-first searches in the last chapter. In a similar way we re going to assume that you don t start out knowing the costs of installing the cable TV line between all the pairs of towns in Magnaguena. Acquiring this information takes time. That s where the surveyors come in. Starting in Ajo You start by setting up an office in Ajo. You could start in any town but Ajo has the best restaurants. Only two towns are reachable from Ajo Bordo and Danza refer to Figure . You hire two tough jungle-savvy surveyors and send them out along the dangerous wilderness trails one to Bordo and one to Danza. Their job is to determine the cost of installing cable along these routes. The first surveyor arrives in Bordo having completed her survey and calls you