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

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

暫缺《Java算法：圖算法（第2卷）》作者簡(jiǎn)介