ACM-ICPC程序設(shè)計(jì)系列 圖論及應(yīng)用

出版時(shí)間:2012-3  出版社:哈爾濱工業(yè)大學(xué)出版社  作者:馮林,金博,姚翠莉 主編  頁(yè)數(shù):240  
Tag標(biāo)簽:無(wú)  

內(nèi)容概要

本書(shū)主要介紹ACM—ICPC比賽中涉及的圖論,其中包括許多實(shí)際問(wèn)題的抽象表示與求解,以及部分圖論理論內(nèi)容的證明。全書(shū)共分6章,第1章介紹了圖論的基礎(chǔ)知識(shí),包括基礎(chǔ)概念、存儲(chǔ)方法和遍歷方法;第2章介紹了有關(guān)樹(shù)的問(wèn)題,著重講解生成樹(shù)和一些樹(shù)上特殊點(diǎn)集的求法;第3章介紹了最短路徑問(wèn)題,包括幾種通用算法和特殊圖上的算法;第4章介紹圖論中有關(guān)連通性的問(wèn)題,包括有向圖的強(qiáng)連通、無(wú)向圖的雙連通及其擴(kuò)展問(wèn)題;第5章介紹網(wǎng)絡(luò)流解法,包括幾種常用的網(wǎng)絡(luò)流算法和對(duì)于問(wèn)題如何抽象成網(wǎng)絡(luò)流模型的經(jīng)驗(yàn)方法;第6章介紹二分圖的相關(guān)問(wèn)題,重點(diǎn)為二分圖的匹配及其變種問(wèn)題。本書(shū)的內(nèi)容基本滿(mǎn)足ACM—ICPC比賽對(duì)于圖論方面的要求,講解清晰易懂,代碼規(guī)范,例題豐富。

書(shū)籍目錄

第1章 圖
1.1 圖的定義和術(shù)語(yǔ)
1.1.1 圖的定義
1.1.2 特殊的圖
1.1.3 有向圖和無(wú)向圖
1.1.4 路徑與連通
1.2 圖的存儲(chǔ)結(jié)構(gòu)
1.2.1 鄰接矩陣
1.2.2 前向星
1.2.3 鄰接表
1.3 圖的遍歷
1.3.1 圖的深度優(yōu)先遍歷
1.3.2 圖的寬度優(yōu)先遍歷
1.3.3 圖的拓?fù)渑判?br /> 1.3.4 圖的可行遍性
第2章 樹(shù)
2.1 樹(shù)的定義和遍歷
2.1.1 樹(shù)的相關(guān)定義
2.1.2 樹(shù)的遍歷
2.2 圖的生成樹(shù)
2.2.1 最小生成樹(shù)
2.2.2 次小生成樹(shù)
2.2.3 有向圖的最小樹(shù)形圖
2.3 樹(shù)的其他問(wèn)題
2.3.1 樹(shù)上兩點(diǎn)的最近公共祖先
2.3.2 樹(shù)的最小支配集,最小點(diǎn)覆蓋與最大獨(dú)立集
第3章 圖的最短路徑問(wèn)題
3.1 單源最短路徑
3.1.1 Dijkstra算法
3.1.2 Bellman—Ford算法
3.1.3 SPFA算法
3.1.4 例題
3.2 每對(duì)頂點(diǎn)間的最短距離
3.2.1 Floyd算法
3.2.2 例題
3.3 最短路問(wèn)題的擴(kuò)展與應(yīng)用
3.3.1 k短路
3.3.2 差分約束系統(tǒng)
3.3.3 DAG圖上的單源最短路徑
3.3.4 Floyd求最小環(huán)
第4章 連通性問(wèn)題
4.1 圖的強(qiáng)連通
4.1.1 強(qiáng)連通的定義
4.1.2 Kosaraju算法
4.1.3 Tarjan算法
4.1.4 Garbow算法
4.1.5 例題
4.2 最小點(diǎn)基
4.2.1 最小點(diǎn)基的定義
4.2.2 最小點(diǎn)基
4.2.3 最小權(quán)點(diǎn)基
4.2.4 例題
4.3 圖的雙連通
4.3.1 雙連通的定義
4.3.2 點(diǎn)雙連通分量
4.3.3 邊雙連通分量
4.3.4 例題
4.4 圖的全局最小割問(wèn)題和Stoer—Wagner算法
4.5 2一SAT
4.5.1 SAT
4.5.2 2一SAT
4.5.3 例題
第5章 網(wǎng)絡(luò)流
第6章 二分圖及匹配算法
參考文獻(xiàn)

編輯推薦

  《圖論及應(yīng)用》是ACM-ICPC程序設(shè)計(jì)系列叢書(shū)之一。全書(shū)共分6章,內(nèi)容包括:圖,樹(shù),圖的最短路徑問(wèn)題,連通性問(wèn)題,網(wǎng)絡(luò)流,二分圖及匹配算法?! ”緯?shū)既可以作為高等院校信息與計(jì)算科學(xué)、計(jì)算機(jī)專(zhuān)業(yè)及數(shù)學(xué)相關(guān)專(zhuān)業(yè)的圖論教材,也可以作為高等學(xué)校計(jì)算機(jī)競(jìng)賽的培訓(xùn)教材,還可供計(jì)算機(jī)軟硬件研發(fā)人員參考。

圖書(shū)封面

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

無(wú)

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


    ACM-ICPC程序設(shè)計(jì)系列 圖論及應(yīng)用 PDF格式下載


用戶(hù)評(píng)論 (總計(jì)10條)

 
 

  •   我毫不吝惜溢美之詞來(lái)贊美這本書(shū)……
    細(xì)致全面,大部分都是算法的講解而非干枯的題目加代碼(當(dāng)然這本書(shū)的代碼還是很全的,這一套書(shū)的特點(diǎn)就是代碼全面)?!疚矣X(jué)得只有題目+幾句簡(jiǎn)單分析+貼代碼的那種書(shū)都是渣渣~】算法講得蠻透徹的,而且基本算法+稍高級(jí)的算法都全了,還有堆優(yōu)化等的樣例代碼,只有一些事無(wú)巨細(xì)的高級(jí)算法(比如第K小生成樹(shù),最小度限制生成樹(shù)等)沒(méi)有講。總而言之,能在這么小一本書(shū)里集成這么多東西,真是太棒了?。?/li>
  •   比較有針對(duì)性的講解值得看看
  •   但是有些例子講解的不是特別細(xì)致,導(dǎo)致我這種菜鳥(niǎo)看不懂呃。。。
  •   內(nèi)容很不錯(cuò),學(xué)習(xí)ing
  •   專(zhuān)業(yè)學(xué)習(xí)用的書(shū),當(dāng)當(dāng)買(mǎi)書(shū)真方便呀,速度送到!
  •   看別人買(mǎi)的 感覺(jué)挺不錯(cuò) 我也買(mǎi)了一本
  •   沒(méi)有時(shí)間全部閱讀,在里面找了好多小例子,還是很有用的。
  •   圖論講解還是比較好的!少了很多枯燥的東西!但是其證明好像太少!
  •   有的題目只有部分代碼,比較難懂
  •   哦給力,還沒(méi)看

推薦圖書(shū)


相關(guān)圖書(shū)

 

250萬(wàn)本中文圖書(shū)簡(jiǎn)介、評(píng)論、評(píng)分,PDF格式免費(fèi)下載。 第一圖書(shū)網(wǎng) 手機(jī)版

京ICP備13047387號(hào)-7