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

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

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