算法（第5部分）

前言

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

內(nèi)容概要

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

作者簡介

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

書籍目錄

出版者的話
譯者序
中文版序
前言
第五部分　圖算法
　第17章　圖的性質(zhì)及類型
　　17.1　術(shù)語
　　17.2　圖的
　　17.3　鄰接矩陣表示
　　17.4　鄰接表表示
　　17.5　變量、擴(kuò)展和開銷
　　17.6　圖生成器
　　17.7　簡單路徑、歐拉路徑和哈密頓路徑
　　17.8　圖處理問題
　第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章　有向圖和有向無環(huán)圖
　　19.1　術(shù)語和游戲規(guī)則
　　19.2　有向圖中的DFS剖析
　　19.3　可達(dá)性和傳遞閉包
　　19.4　等價關(guān)系和偏序
　　19.5　有向無環(huán)圖
　　19.6　拓?fù)渑判?br />　　19.7　有向無環(huán)圖中的可達(dá)性
　　19.8　有向圖中的強(qiáng)連通分量
　　19.9　再論傳遞閉包
　　19.10　展望
　第20章　最小生成樹
　　20.1　表
　　20.2　MST算法的基本原理
　　20.3　Prim算法和優(yōu)先級優(yōu)先搜索
　　20.4　Kruskal算法
　　20.5　Boruvka算法
　　20.6　比較與改進(jìn)
　　20.7　歐幾里得
　第21章　最短路徑
　　21.1　基本原理
　　21.2　Dijkstra算法
　　21.3　所有對最短路徑
　　21.4　無環(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é)所討論的所有變型算法，因為它們是以幾種高級抽象操作為基礎(chǔ)的，如“對于與頂點(diǎn)V鄰接的每條邊執(zhí)行如下操作?！睂嶋H上，我們考慮的某些程序只在這種抽象操作的實現(xiàn)方法上有所不同而已?！　槭裁床荒茉诟呒壍某橄箝_發(fā)這些算法，然后討論表示數(shù)據(jù)和實現(xiàn)相關(guān)操作的不同選項呢？就像我們在本書中的很多實例中所做的那樣。這個問題的答案并不是一句話就能說清楚的。對于稀疏圖常選擇用鄰接表，對于稠密圖常選擇用鄰接矩陣，這些選擇我們很清楚。在主要實現(xiàn)中，我們會直接選擇這兩種特殊表示中的其中一種，因為使用低級表示的代碼中，算法的性能特征非常清晰，而且比起那些利用高級抽象編寫的代碼，該代碼一般而言不難讀懂和理解?！　≡谀承嵗?，算法設(shè)計決策依賴于表示的某些性質(zhì)。在一個更高的抽象級上處理，可能使我們不了解這種依賴性的相關(guān)知識。如果我們知道某種表示將導(dǎo)致很差的性能，而另一種表示不會，在不適當(dāng)?shù)某橄蠹壙紤]算法時，就會存在不必要的風(fēng)險。如常，我們的目標(biāo)是精細(xì)實現(xiàn)，從而可以對性能做出準(zhǔn)確的說明?！　∈褂脟?yán)格的抽象方法可以解決這些問題，我們建立算法中需要的抽象操作的抽象層次。添加一個ADT操作來測試一條邊的存在性是一個例子（見練習(xí)17.1 9），我們還能建立與表示無關(guān)的代碼，來處理與給定頂點(diǎn)鄰接的每個頂點(diǎn)（見練習(xí)17.6 0）。在很多情況下，這樣的方法很有意義。然而，在本書中，我們關(guān)注的是在稠密圖上使用直接訪問鄰接矩陣的代碼和在稀疏圖上直接訪問鄰接表的代碼的性能，并增大數(shù)據(jù)結(jié)構(gòu)以適合所處理的任務(wù)?！　〉侥壳盀橹刮覀兯懻摰乃胁僮魇呛唵蔚亩直匾臄?shù)據(jù)處理函數(shù)；本節(jié)要討論的是第1—3部分的基本算法和數(shù)據(jù)結(jié)構(gòu)對于處理這些函數(shù)是有效的。當(dāng)開發(fā)更復(fù)雜的圖處理算法時，我們在找出特定實際問題的最佳實現(xiàn)時面臨更困難的挑戰(zhàn)。為了說明這一點(diǎn)，考慮表17.1 中的最后一行，其中給出了確定兩個給定頂點(diǎn)是否存在一條路徑的開銷。

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

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---