算法（第5部分）

前言

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

內(nèi)容概要

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

作者簡(jiǎn)介

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

書籍目錄

出版者的話
譯者序
中文版序
前言
第五部分　圖算法
　第17章　圖的性質(zhì)及類型
　　17.1　術(shù)語
　　17.2　圖的
　　17.3　鄰接矩陣表示
　　17.4　鄰接表表示
　　17.5　變量、擴(kuò)展和開銷
　　17.6　圖生成器
　　17.7　簡(jiǎn)單路徑、歐拉路徑和哈密頓路徑
　　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　等價(jià)關(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)先級(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　無環(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í)的抽象開發(fā)這些算法，然后討論表示數(shù)據(jù)和實(shí)現(xiàn)相關(guān)操作的不同選項(xiàng)呢？就像我們?cè)诒緯械暮芏鄬?shí)例中所做的那樣。這個(gè)問題的答案并不是一句話就能說清楚的。對(duì)于稀疏圖常選擇用鄰接表，對(duì)于稠密圖常選擇用鄰接矩陣，這些選擇我們很清楚。在主要實(shí)現(xiàn)中，我們會(huì)直接選擇這兩種特殊表示中的其中一種，因?yàn)槭褂玫图?jí)表示的代碼中，算法的性能特征非常清晰，而且比起那些利用高級(jí)抽象編寫的代碼，該代碼一般而言不難讀懂和理解?！　≡谀承?shí)例中，算法設(shè)計(jì)決策依賴于表示的某些性質(zhì)。在一個(gè)更高的抽象級(jí)上處理，可能使我們不了解這種依賴性的相關(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)確的說明?！　∈褂脟?yán)格的抽象方法可以解決這些問題，我們建立算法中需要的抽象操作的抽象層次。添加一個(gè)ADT操作來測(cè)試一條邊的存在性是一個(gè)例子（見練習(xí)17.1 9），我們還能建立與表示無關(guān)的代碼，來處理與給定頂點(diǎn)鄰接的每個(gè)頂點(diǎn)（見練習(xí)17.6 0）。在很多情況下，這樣的方法很有意義。然而，在本書中，我們關(guān)注的是在稠密圖上使用直接訪問鄰接矩陣的代碼和在稀疏圖上直接訪問鄰接表的代碼的性能，并增大數(shù)據(jù)結(jié)構(gòu)以適合所處理的任務(wù)?！　〉侥壳盀橹刮覀兯懻摰乃胁僮魇呛?jiǎn)單的而又必要的數(shù)據(jù)處理函數(shù)；本節(jié)要討論的是第1—3部分的基本算法和數(shù)據(jù)結(jié)構(gòu)對(duì)于處理這些函數(shù)是有效的。當(dāng)開發(fā)更復(fù)雜的圖處理算法時(shí)，我們?cè)谡页鎏囟▽?shí)際問題的最佳實(shí)現(xiàn)時(shí)面臨更困難的挑戰(zhàn)。為了說明這一點(diǎn)，考慮表17.1 中的最后一行，其中給出了確定兩個(gè)給定頂點(diǎn)是否存在一條路徑的開銷。

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

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

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

---

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

---