Java算法：圖算法（第2卷）

　　本書深入介紹了圖算法。書中分別對圖屬性和類型、圖搜索、有向圖、最小生成樹、最短路徑以及網(wǎng)絡流的有關(guān)內(nèi)容進行了透徹的討論。書中不僅對基本內(nèi)容做了全面的闡述，而且對經(jīng)典算法也提供了詳盡的分析，同時還涵蓋了有關(guān)的高級主題。全書既強調(diào)了與實用有關(guān)的內(nèi)容，在分析和理論研究上也很有深度。另外，對于書中提供的算法，讀者可以放心實現(xiàn)和調(diào)試，并用這些算法來解決問題。本書內(nèi)容全面、論述清晰，適合于計算機科學和數(shù)學領(lǐng)域各個層次的人員使用。圖和圖算法在當今的計算應用中頗為常見。對于在實際中出現(xiàn)的圖處理問題，本書描述了一些已知的最重要的解決方法。由于需要相關(guān)知識的人日漸增多，這本書的主要目的就是讓他們了解這些方法及其所蘊藏的基本原則。全書由最基本的原則展開，并從基本概念開始介紹，逐步過渡到經(jīng)典方法，最后對仍在開發(fā)中的最新技術(shù)加以討論。在對算法和應用的描述中，我們提供了精心挑選的示例、詳盡的圖表以及完備的補充說明。算法為研究當前所使用的最為重要的計算機算法，計劃共出版3卷，本書是其中的第2卷。第1卷（第1一Ⅳ部分）所涵蓋的是基礎(chǔ)知識（第1部分）、數(shù)據(jù)結(jié)構(gòu)（第Ⅱ部分）、排序算法（第Ⅲ部分）以及查找算法（第Ⅳ部分）；這一卷（第V部分）則討論圖與圖算法；而未出版的第3卷（第Ⅵ～Ⅷ部分）將介紹串（第Ⅵ部分）、計算幾何（第Ⅶ部分）以及高級算法和應用（第Ⅷ部分）。在學習計算機科學課程之初，即學生已經(jīng)掌握了基本的編程技巧，熟悉計算機系統(tǒng)，但是尚未選修計算機科學或計算機應用高級領(lǐng)域中的專業(yè)課程時，將這些書作為教材是很有用的。這些書也可用于自學，對從事計算機系統(tǒng)或應用程序開發(fā)的人來說，將這些書用作參考書也是相當有用的，書中包含了實用算法的實現(xiàn)，并對這些算法的性能特性提供了詳盡的信息。該系列圖書覆蓋面非常之廣，因此適于作為這一領(lǐng)域的入門讀物。多年以來，《Java算法》一書已由世界各地的學生和程序員廣泛使用，而以上這3卷書加在一起則構(gòu)成了這本書的第3版。在這一版本中，我完全重寫了有關(guān)內(nèi)容，并且增加了數(shù)千個新練習、數(shù)百個新圖表以及數(shù)十個新程序，而且對所有的圖表和程序做了詳盡的注釋說明。在此不僅涵蓋了新的主題，而且還對許多經(jīng)典算法提供了更為充分的解釋。全書強調(diào)了抽象數(shù)據(jù)類型，從而使得有關(guān)程序的應用面更廣，而且與當今的面向?qū)ο缶幊汰h(huán)境也更為相關(guān)。對于已經(jīng)閱讀過本書以前版本的人來說，會從這一版中發(fā)現(xiàn)相當多的新內(nèi)容；而對于所有讀者而言，都能從中得到極為豐富的學習資料，可以更好地理解基本概念。這套書不僅適合程序員和計算機科學專業(yè)的學生閱讀。每一個使用計算機的人都希望它能運行得更快，或者可以解決更大規(guī)模的問題。我們所考慮的算法代表了近5年發(fā)展起來的知識體系，該體系是在各種各樣的應用中有效地使用計算機的基礎(chǔ)。從物理學中的多體仿真問題到分子生物學中的基因序列問題，在此所描述的基本方法在科學研究中已日顯重要：另外，對于從數(shù)據(jù)庫系統(tǒng)到Internet搜索引擎等當今的軟件系統(tǒng)，這些基本方法也已經(jīng)成為其基本的組成部分。隨著計算機應用的覆蓋面越來越廣，基本算法的影響也日益顯著，特別是本書所介紹的基本圖算法，作用更為突出。廣大學生以及專業(yè)人士可能會參與完成各種計算機應用，隨著這些應用中相關(guān)需求的增長，本書的目標就是要提供一個有效的資源，從而使他們充分了解并明智地使用圖算法。本書范圍《Java算法》（第3版）的"第V部分：圖算法篇"共包括6章，分別介紹圖的屬性和類型、圖搜索、有向圖、最小生成樹、最短路徑以及網(wǎng)。其目的是為了使讀者能夠了解盡可能多的基本圖算法，并對其基本屬性有所理解。如果你曾經(jīng)學過有關(guān)算法設計和分析基本原則的課程，并且有利用諸如Java，C++或C等高級語言編程的經(jīng)驗，那么對于在此介紹的內(nèi)容，就會充分領(lǐng)略到它的價值。當然，《Java算法》（第3版）的第1一Ⅳ部分已經(jīng)為此做了充分的準備。本書假設你已經(jīng)對數(shù)組、鏈表以及ADT（AbstractDataType，抽象數(shù)據(jù)類型）設計等有基本的了解，而且使用過優(yōu)先隊列、符號表以及并查ADT，所有這些在第1一Ⅳ部分中都有詳細的描述（而且在另外一些有關(guān)算法和數(shù)據(jù)結(jié)構(gòu)的介紹性文字中也有說明）。圖和圖算法的基本屬性由最基本的原則建立，但要充分理解，則往往需要擁有博大精深的數(shù)學背景。盡管在此對高級數(shù)學概念的討論很簡短，而且是概括性和描述性的，但與第1一Ⅳ部分所介紹的內(nèi)容相同，要想對圖算法有更深入的認識，自然應該有更高的數(shù)學水平。不過廣數(shù)學水平各不相同的讀者都可從此書中獲益。這種說法可做如下考慮：相對于并非任何人都能理解的一些高級算法，每個人都應該理解并使用的基本圖算法只是略有差異。在此的主要意圖是結(jié)合貫穿于全書的其他方法來討論重要的算法，而不是對所有數(shù)學知識做全面的介紹。不過，好的數(shù)學基礎(chǔ)往往要求嚴格的行事方式，而這通常可使我們得到好的程序，因此我盡量在理論家所崇尚的形式規(guī)范性和實踐家所需要的內(nèi)容豐富性之間進行權(quán)衡，同時也不損害嚴格性。教學使用在本書的講授方式上有很大的靈活性，這取決于教師的偏好，同時也依賴于學生所做的準備。可把本書用作面向初學者的數(shù)據(jù)結(jié)構(gòu)課程，因為它闡述了足夠的基本內(nèi)容；也可把本書用作面向高水平學生的算法分析與設計課程，因為它不僅足夠詳細，而且涵蓋了高級內(nèi)容。有些教師可能希望強調(diào)與實現(xiàn)和實用有關(guān)的內(nèi)容，而另外一些教師則可能希望把重點放在分析和理論概念上?？蓪⒈緯c第1一Ⅳ部分結(jié)合起來，作為一門更為全面的課程講授。這樣，教師就可以完全用一種一致的風格來介紹基礎(chǔ)知識、數(shù)據(jù)結(jié)構(gòu)、排序、查找和圖算法等全部內(nèi)容。書中的練習（幾乎全都是在這一版中新增加的）可分為多種類型。有一些是為了檢查對正文中內(nèi)容的理解，只要求讀者完成某個示例，或者應用正文中所描述的概念。另外一些則涉及實現(xiàn)和整理算法，或者進行實驗研究，從而對不同算法加以比較以了解其屬性。還有一些練習則相當于知識儲備，是對一些重要信息所做的相當詳細的說明，而這些信息本身不適于放在正文里。閱讀這些練習并加以思考，會使每個讀者都有意想不到的收獲。實用算法任何人若希望更為有效地使用計算機，都可以將這本書作為參考，或用于自學。有編程經(jīng)驗的人可以從書中找到有關(guān)一些特定主題的信息。一般地，你可以抽取書中的各章獨立地閱讀。不過，有些情況下，某一章中的算法可能會用到前一章中所介紹的方法。本書的定位是對很可能會在實際中使用的算法加以研究。本書對所討論的工具（即算法）提供了詳盡的信息，讀者可以放心地實現(xiàn)和調(diào)試，并用這些算法來解決問題，或在應用中利用它們來提供有關(guān)功能。在此對所討論的方法提供了完整的實現(xiàn)，同時，針對書中一系列一致的示例程序的操作做了描述。由于我們采用了實際代碼，而不是編寫偽代碼，因此這些程序很快就可以在實際中使用。通過訪問本書的主頁可以得到程序的代碼清單。您可以用許多方法使用這些工作程序，從而幫助你研究算法。閱讀它們以檢查你對算法細節(jié)的了解，或用一種方法來處理實例化、邊界條件和在編程中可能遇到的其他情況。運行這些程序，看看算法在實際中的表現(xiàn)，以根據(jù)經(jīng)驗研究性能，并根據(jù)書中提供的表檢查結(jié)果，或試一下你自己所做的修改。實際上，由算法的一個實際應用已經(jīng)得到了本書中的數(shù)百個圖表。許多算法正是通過這些圖表所提供的視覺維度直觀地發(fā)現(xiàn)和得到的。本書將詳細討論這些算法的特性以及它們可能在哪些情況下是有用的。在此可建立算法分析與理論計算機科學之間的聯(lián)系。在適當?shù)那闆r下，都將給出經(jīng)驗性的結(jié)果以及分析結(jié)果，以說明為什么某些算法更為適用。如果有意義，還會對所討論的實際算法與純理論結(jié)果之間的關(guān)系加以描述。對于算法和實現(xiàn)的性能特性的特定信息，全書將對其進行綜合性和概要性的討論。編程語言書中所有實現(xiàn)所用的編程語言均為Java。程序中使用了大量的標準Java習慣用法且對于每個構(gòu)造，正文中都做了簡潔的描述。MikeSchidlowsky和本人基于ADT建立了一種Java編程的風格，并認為這是一個將算法和數(shù)據(jù)結(jié)構(gòu)表示為實際程序的有效方法。我們在實現(xiàn)的優(yōu)雅性、簡潔性、有效性和可移植性方面做了很大的努力。程序風格會盡可能保持一致，因此類似的程序看-上去也是相似的。本書的目標是以盡可能簡單明了的方式宋展示算法。對于許多算法而言，盡管所用的語言不同，但存在著相似性。作為一個突出的例子，Dijkstra算法就是Dijkstra算法，無論采用Algol-6，Basic，F(xiàn)ortran，Smalltalk，Ada，Pascal，C，C++，Modula-3，PostScript，Java，Python，還是任何一種其他的編程語言（這樣的語言可謂不計其數(shù)）來編寫，也不管所在的是何種環(huán)境，均可以證實為有效的圖處理方法。一方面，采用這些語言（以及其他多種語言）宋實現(xiàn)算法會獲得一些經(jīng)驗（本書的C和C++版本已經(jīng)面世），代碼會受到這些經(jīng)驗的影響：另一方面，對于這其中的一些語言，其屬性會受其設計人員的經(jīng)驗所左右，而這些經(jīng)驗又來自于他對本書所討論的部分算法和數(shù)據(jù)結(jié)構(gòu)的使用。最后，我們認為本書所提供的代碼不僅準確地定義了算法，而且在實際工作中也相當有用。

暫缺《Java算法：圖算法（第2卷）》作者簡介