算法（第5部分）

前言

　　圖和圖算法在現(xiàn)代計(jì)算機(jī)應(yīng)用中頗為常見(jiàn)。對(duì)于在實(shí)際中出現(xiàn)的一些圖處理問(wèn)題，本書(shū)描述了目前最重要的解決方法。由于需要相關(guān)知識(shí)的人日漸增多，本書(shū)的主要目標(biāo)是使讀者了解這些方法及其所蘊(yùn)含的基本原理。本書(shū)從基本原理展開(kāi)，并從基本信息開(kāi)始，從經(jīng)典方法到現(xiàn)代仍在研發(fā)中的技術(shù)逐一展開(kāi)討論。精心選擇的示例、詳盡的圖表以及完善實(shí)現(xiàn)的補(bǔ)充材料無(wú)一不體現(xiàn)在算法和應(yīng)用的描述中?！　∷惴ā　”緯?shū)是對(duì)當(dāng)前使用的最重要的計(jì)算機(jī)算法進(jìn)行深入研究的三卷中的第二卷：圖算法。第一卷（第1~4部分）覆蓋了基本概念（第1部分）、數(shù)據(jù)結(jié)構(gòu)（第2部分）、排序算法（第3部分）和搜索算法（第4部分）；本卷（第5部分）覆蓋了圖與圖算法；（尚未出版的）第三卷（第6~8部分）覆蓋了字符串（第6部分）、計(jì)算幾何（第7部分）和高級(jí)算法及應(yīng)用（第8部分）?！　∵@些書(shū)可作為計(jì)算機(jī)科學(xué)低年級(jí)本科生的教材。學(xué)習(xí)本課程之前要求學(xué)生掌握基本程序設(shè)計(jì)技巧并熟知計(jì)算機(jī)系統(tǒng)，不過(guò)尚未選修計(jì)算機(jī)科學(xué)或計(jì)算機(jī)應(yīng)用的高級(jí)領(lǐng)域的專(zhuān)業(yè)課程。這些書(shū)還可用作自學(xué)或作為從事計(jì)算機(jī)系統(tǒng)或應(yīng)用程序開(kāi)發(fā)的參考讀本，因?yàn)樗鼈儼藢?shí)用算法的實(shí)現(xiàn)以及關(guān)于這些算法性能特征的詳盡信息。這些書(shū)包含內(nèi)容廣泛，適合作為這一領(lǐng)域的入門(mén)讀物?！　《嗄暌詠?lái)，這三卷書(shū)共同構(gòu)成的《算法：C語(yǔ)言實(shí)現(xiàn)》（第3版）已經(jīng)得到世界各地的學(xué)生和程序員的廣泛使用。我完全重寫(xiě)了這一版的內(nèi)容，并且增加了數(shù)千個(gè)新練習(xí)、數(shù)百個(gè)新圖表、數(shù)十個(gè)新程序以及對(duì)圖表和程序詳盡的注釋說(shuō)明。這個(gè)新版本不僅涵蓋了新的主題，而且還提供了對(duì)許多經(jīng)典算法的更充分的解釋。全書(shū)對(duì)抽象數(shù)據(jù)類(lèi)型的強(qiáng)調(diào)使這些程序使用更為廣泛，而且在現(xiàn)代面向?qū)ο蟮木幊汰h(huán)境中也更為適用。對(duì)于已經(jīng)閱讀過(guò)以前版本的人來(lái)說(shuō)，會(huì)從這一版找到更為豐富的信息；并且所有讀者都會(huì)從中找到富有教益的內(nèi)容，有效地學(xué)習(xí)本書(shū)提供的基本概念?！　∵@些書(shū)適合于程序員和計(jì)算機(jī)科學(xué)專(zhuān)業(yè)的學(xué)生閱讀。每一個(gè)使用計(jì)算機(jī)的人都希望它能運(yùn)行得更快，或者可解決更大規(guī)模的問(wèn)題。我們所考慮的算法代表了近50年發(fā)展起來(lái)的知識(shí)體系，該體系是在各種應(yīng)用中有效地使用計(jì)算機(jī)解決問(wèn)題不可缺少的部分。從物理學(xué)中的N?體模擬問(wèn)題到分子生物學(xué)中的基因序列問(wèn)題，在此所描述的基本方法在科學(xué)研究中已日顯重要；另外，對(duì)于從數(shù)據(jù)庫(kù)系統(tǒng)到Internet搜索引擎，這些方法已經(jīng)成為現(xiàn)代軟件系統(tǒng)的重要組成部分。隨著計(jì)算機(jī)應(yīng)用的覆蓋面越來(lái)越廣，基本算法的影響也日益顯著，特別是本書(shū)所涵蓋的基本圖算法，作用更為突出。本書(shū)的目標(biāo)是要提供一種資源，使廣大學(xué)生以及專(zhuān)業(yè)人士可以了解并明智地利用圖算法來(lái)解決計(jì)算機(jī)應(yīng)用中出現(xiàn)的問(wèn)題。

內(nèi)容概要

本書(shū)是深入論述算法的三卷本教程《算法：C語(yǔ)言實(shí)現(xiàn)》（第3版）中的第二卷——圖算法。作者在這次修訂中重寫(xiě)了許多內(nèi)容，增加了數(shù)千個(gè)新練習(xí)、數(shù)百個(gè)新圖表、數(shù)十個(gè)新程序，并對(duì)圖表和程序做了詳盡的注釋說(shuō)明。新版中不僅涵蓋了新的主題，而且還提供了對(duì)許多經(jīng)典算法的更充分的解釋?zhuān)▓D的性質(zhì)、圖搜索、有向圖、最小生成樹(shù)、最短路徑和網(wǎng)。本書(shū)涵蓋了足夠的基本內(nèi)容及較詳細(xì)的圖算法高級(jí)主題，既可單獨(dú)用作數(shù)據(jù)結(jié)構(gòu)與算法課程的教材，也可與第一卷（第1～4部分）結(jié)合使用。
本書(shū)適合高等院校計(jì)算機(jī)專(zhuān)業(yè)師生參考，也可供軟件開(kāi)發(fā)人員參考。

作者簡(jiǎn)介

　　Robed Sedgewick，擁有斯坦福大學(xué)博士學(xué)位（導(dǎo)師為Donald E. Knuth），昔林斯頓大學(xué)計(jì)算機(jī)科學(xué)系教授，Adobe Systems公司董事，曾是XeroxPARC的研究人員，還曾就職于美國(guó)國(guó)防部防御分析研究所以及INRIA。除本書(shū)外，他還與Philippe Flajolet合著了《算法分析導(dǎo)論》一書(shū)

書(shū)籍目錄

出版者的話
譯者序
中文版序
前言
第五部分　圖算法
　第17章　圖的性質(zhì)及類(lèi)型
　　17.1　術(shù)語(yǔ)
　　17.2　圖的
　　17.3　鄰接矩陣表示
　　17.4　鄰接表表示
　　17.5　變量、擴(kuò)展和開(kāi)銷(xiāo)
　　17.6　圖生成器
　　17.7　簡(jiǎn)單路徑、歐拉路徑和哈密頓路徑
　　17.8　圖處理問(wèn)題
　第18章　圖搜索
　　18.1　探索迷宮
　　18.2　深度優(yōu)先搜索
　　18.3　圖搜索ADT函數(shù)
　　18.4　DFS森林的性質(zhì)
　　18.5　DFS算法
　　18.6　可分離性和雙連通性
　　18.7　廣度優(yōu)先搜索
　　18.8　廣義圖搜索
　　18.9　圖算法分析
　第19章　有向圖和有向無(wú)環(huán)圖
　　19.1　術(shù)語(yǔ)和游戲規(guī)則
　　19.2　有向圖中的DFS剖析
　　19.3　可達(dá)性和傳遞閉包
　　19.4　等價(jià)關(guān)系和偏序
　　19.5　有向無(wú)環(huán)圖
　　19.6　拓?fù)渑判?br />　　19.7　有向無(wú)環(huán)圖中的可達(dá)性
　　19.8　有向圖中的強(qiáng)連通分量
　　19.9　再論傳遞閉包
　　19.10　展望
　第20章　最小生成樹(shù)
　　20.1　表
　　20.2　MST算法的基本原理
　　20.3　Prim算法和優(yōu)先級(jí)優(yōu)先搜索
　　20.4　Kruskal算法
　　20.5　Boruvka算法
　　20.6　比較與改進(jìn)
　　20.7　歐幾里得
　第21章　最短路徑
　　21.1　基本原理
　　21.2　Dijkstra算法
　　21.3　所有對(duì)最短路徑
　　21.4　無(wú)環(huán)網(wǎng)中的最短路徑
　　21.5　歐幾里得網(wǎng)
　　21.6　歸約
　　21.7　負(fù)權(quán)值
　　21.8　展望
　第22章　網(wǎng)絡(luò)流
　　22.1　流網(wǎng)絡(luò)
　　22.2　增大路徑最大流算法
　　22.3　預(yù)流-推進(jìn)最大流算法
　　22.4　最大流歸約
　　22.5　最小成本流
　　22.6　網(wǎng)絡(luò)單純形算法
　　22.7　最小成本流歸約
　　22.8　展望
第五部分參考文獻(xiàn)

章節(jié)摘錄

　　我們討論的很多算法可以很容易改造為本節(jié)所討論的所有變型算法，因?yàn)樗鼈兪且詭追N高級(jí)抽象操作為基礎(chǔ)的，如“對(duì)于與頂點(diǎn)V鄰接的每條邊執(zhí)行如下操作。”實(shí)際上，我們考慮的某些程序只在這種抽象操作的實(shí)現(xiàn)方法上有所不同而已?！　槭裁床荒茉诟呒?jí)的抽象開(kāi)發(fā)這些算法，然后討論表示數(shù)據(jù)和實(shí)現(xiàn)相關(guān)操作的不同選項(xiàng)呢？就像我們?cè)诒緯?shū)中的很多實(shí)例中所做的那樣。這個(gè)問(wèn)題的答案并不是一句話就能說(shuō)清楚的。對(duì)于稀疏圖常選擇用鄰接表，對(duì)于稠密圖常選擇用鄰接矩陣，這些選擇我們很清楚。在主要實(shí)現(xiàn)中，我們會(huì)直接選擇這兩種特殊表示中的其中一種，因?yàn)槭褂玫图?jí)表示的代碼中，算法的性能特征非常清晰，而且比起那些利用高級(jí)抽象編寫(xiě)的代碼，該代碼一般而言不難讀懂和理解?！　≡谀承?shí)例中，算法設(shè)計(jì)決策依賴(lài)于表示的某些性質(zhì)。在一個(gè)更高的抽象級(jí)上處理，可能使我們不了解這種依賴(lài)性的相關(guān)知識(shí)。如果我們知道某種表示將導(dǎo)致很差的性能，而另一種表示不會(huì)，在不適當(dāng)?shù)某橄蠹?jí)考慮算法時(shí)，就會(huì)存在不必要的風(fēng)險(xiǎn)。如常，我們的目標(biāo)是精細(xì)實(shí)現(xiàn)，從而可以對(duì)性能做出準(zhǔn)確的說(shuō)明?！　∈褂脟?yán)格的抽象方法可以解決這些問(wèn)題，我們建立算法中需要的抽象操作的抽象層次。添加一個(gè)ADT操作來(lái)測(cè)試一條邊的存在性是一個(gè)例子（見(jiàn)練習(xí)17.1 9），我們還能建立與表示無(wú)關(guān)的代碼，來(lái)處理與給定頂點(diǎn)鄰接的每個(gè)頂點(diǎn)（見(jiàn)練習(xí)17.6 0）。在很多情況下，這樣的方法很有意義。然而，在本書(shū)中，我們關(guān)注的是在稠密圖上使用直接訪問(wèn)鄰接矩陣的代碼和在稀疏圖上直接訪問(wèn)鄰接表的代碼的性能，并增大數(shù)據(jù)結(jié)構(gòu)以適合所處理的任務(wù)?！　〉侥壳盀橹刮覀兯懻摰乃胁僮魇呛?jiǎn)單的而又必要的數(shù)據(jù)處理函數(shù)；本節(jié)要討論的是第1—3部分的基本算法和數(shù)據(jù)結(jié)構(gòu)對(duì)于處理這些函數(shù)是有效的。當(dāng)開(kāi)發(fā)更復(fù)雜的圖處理算法時(shí)，我們?cè)谡页鎏囟▽?shí)際問(wèn)題的最佳實(shí)現(xiàn)時(shí)面臨更困難的挑戰(zhàn)。為了說(shuō)明這一點(diǎn)，考慮表17.1 中的最后一行，其中給出了確定兩個(gè)給定頂點(diǎn)是否存在一條路徑的開(kāi)銷(xiāo)。

媒體關(guān)注與評(píng)論

　　對(duì)于在數(shù)學(xué)分析方面不算熟練且需要留意理論算法的普通程序員來(lái)說(shuō)，本書(shū)是一本可讀性很強(qiáng)的優(yōu)秀讀本。他們應(yīng)該會(huì)從中獲益良多?！　　猄teve Summit，《C Programming FAQs》的作者　　Sedgewick有一種真正的天賦，可以用易于理解的方式來(lái)解釋概念。書(shū)中采用了一些易懂的實(shí)戰(zhàn)程序，其篇幅僅有一頁(yè)左右，這更是錦上添花。而書(shū)中大量采用的圖、程序、表格也會(huì)極大幫助讀者的學(xué)習(xí)和理解，這使本書(shū)更顯得與眾不同?！　　猈illiam A. Ward，南亞拉巴馬大學(xué)

編輯推薦

　　本書(shū)是Sedgewick徹底修訂和重寫(xiě)的C算法系列的第二本，集中講解圖算法。全書(shū)共有6章 (第17～22章)。第17章詳細(xì)討論圖性質(zhì)和類(lèi)型，第18～22章分別講解圖搜索、有向圖和DAG、最小生成樹(shù)、最短路徑以及網(wǎng)絡(luò)流?！　?shū)中提供了用C語(yǔ)言描述的完整算法源程序，并且配有豐富的插圖和練習(xí)。作者用簡(jiǎn)潔的實(shí)現(xiàn)將理論和實(shí)踐成功地結(jié)合了起來(lái)，這些實(shí)現(xiàn)均可在真實(shí)應(yīng)用上測(cè)試，使得本書(shū)自問(wèn)世以來(lái)備受程序員的歡迎?！　”緯?shū)可作為高等院校計(jì)算機(jī)相關(guān)專(zhuān)業(yè)算法與數(shù)據(jù)結(jié)構(gòu)課程的教材和補(bǔ)充讀物，也可供自學(xué)之用。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法（第5部分） PDF格式下載

---