Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
(BQ) Part 1 book "Algorithms" has contents: Basic programming model, data abstraction, analysis of algorithms, elementary sorts, mergesort, priority queues, symbol tables, binary search trees, balanced search trees, hash tables, applications. | FOUR Graphs 4.1 Undirected Graphs . . . . . . . . . . . 518 4.2 Directed Graphs . . . . . . . . . . . . . 566 4.3 Minimum Spanning Trees . . . . . . . 604 4.4 Shortest Paths . . . . . . . . . . . . . . 638 P airwise connections between items play a critical role in a vast array of computational applications. The relationships implied by these connections lead immediately to a host of natural questions: Is there a way to connect one item to another by following the connections? How many other items are connected to a given item? What is the shortest chain of connections between this item and this other item? To model such situations, we use abstract mathematical objects called graphs. In this chapter, we examine basic properties of graphs in detail, setting the stage for us to study a variety of algorithms that are useful for answering questions of the type just posed. These algorithms serve as the basis for attacking problems in important applications whose solution we could not even contemplate without good algorithmic technology. Graph theory, a major branch of mathematics, has been studied intensively for hundreds of years. Many important and useful properties of graphs have been discovered, many important algorithms have been developed, and many difficult problems are still actively being studied. In this chapter, we introduce a variety of fundamental graph algorithms that are important in diverse applications. Like so many of the other problem domains that we have studied, the algorithmic investigation of graphs is relatively recent. Although a few of the fundamental algorithms are centuries old, the majority of the interesting ones have been discovered within the last several decades and have benefited from the emergence of the algorithmic technology that we have been studying. Even the simplest graph algorithms lead to useful computer programs, and the nontrivial algorithms that we examine are among the most elegant and interesting algorithms .