Tham khảo tài liệu 'thuật toán algorithms (phần 39)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 29. Elementary Graph Algorithms A great many problems are naturally formulated in terms of objects and connections between them. For example given an airline route map of the eastern U. S. we might be interested in questions like What s the fastest way to get from Providence to Princeton Or we might be more interested in money than in time and look for the cheapest way to get from Providence to Princeton. To answer such questions we need only information about interconnections airline routes between objects towns . Electric circuits are another obvious example where interconnections between objects play a central role. Circuit elements like transistors resistors and capacitors are intricately wired together. Such circuits can be represented and processed within a computer in order to answer simple questions like Is everything connected together as well as complicated questions like If this circuit is built will it work In this case the answer to the first question depends only on the properties of the interconnections wires while the answer to the second question requires detailed information about both the wires and the objects that they connect. A third example is job scheduling where the objects are tasks to be performed say in a manufacturing process and interconnections indicate which jobs should be done before others. Here we might be interested in answering questions like When should each task be performed A graph is a mathematical object which accurately models such situations. In this chapter we ll examine some basic properties of graphs and in the next several chapters we ll study a variety of algorithms for answering questions of the type posed above. Actually we ve already encountered graphs in several instances in previous chapters. Linked data structures are actually representations of graphs and some of the algorithms that we ll see for processing graphs are similar to algorithms that we ve already seen for processing trees and other structures. 373
