圖論算法理論、實(shí)現(xiàn)及應(yīng)用

圖論算法理論實(shí)現(xiàn)及應(yīng)用目錄\h第1章圖的基本概念及圖的存儲\h1.1基本概念\h1.1.1有向圖與無向圖\h1.1.2完全圖、稀疏圖、稠密圖\h1.1.3頂點(diǎn)與頂點(diǎn)、頂點(diǎn)與邊的關(guān)系\h1.1.4頂點(diǎn)的度數(shù)及度序列\(zhòng)h1.1.5二部圖與完全二部圖\h1.1.6圖的同構(gòu)\h1.1.7子圖與生成樹\h1.1.8路徑\h1.1.9連通性\h1.1.10權(quán)值、有向網(wǎng)與無向網(wǎng)\h1.2圖的存儲表示\h1.2.1鄰接矩陣\h1.2.2鄰接表\h1.2.3關(guān)于鄰接矩陣和鄰接表的進(jìn)一步討論\h練習(xí)\h第2章圖的遍歷與活動(dòng)網(wǎng)絡(luò)問題\h2.1DFS遍歷\h2.1.1DFS算法思想\h2.1.2DFS算法的實(shí)現(xiàn)及復(fù)雜度分析\h2.1.3例題解析\h練習(xí)\h2.2BFS遍歷\h2.2.1BFS算法思想\h2.2.2BFS算法的實(shí)現(xiàn)及復(fù)雜度分析\h2.2.3關(guān)于DFS算法和BFS算法的說明\h2.2.4例題解析\h練習(xí)\h2.3活動(dòng)網(wǎng)絡(luò)——AOV網(wǎng)絡(luò)\h2.3.1AOV網(wǎng)絡(luò)與拓?fù)渑判騖h2.3.2拓?fù)渑判驅(qū)崿F(xiàn)方法\h2.3.3關(guān)于拓?fù)渑判虻倪M(jìn)一步說明\h2.3.4例題解析\h練習(xí)\h2.4活動(dòng)網(wǎng)絡(luò)——AOE網(wǎng)絡(luò)\h2.4.1AOE網(wǎng)絡(luò)與關(guān)鍵路徑\h2.4.2關(guān)鍵路徑求解方法\h第3章樹與圖的生成樹\h3.1樹與森林\h3.1.1樹\h3.1.2森林\h3.2生成樹及最小生成樹\h3.2.1生成樹\h3.2.2最小生成樹\h3.3克魯斯卡爾（Kruskal）算法\h3.3.1Kruskal算法思想\h3.3.2等價(jià)類與并查集\h3.3.3Kruskal算法實(shí)現(xiàn)\h3.3.4Boruvka算法\h3.3.5例題解析\h練習(xí)\h3.4普里姆（Prim）算法\h3.4.1Prim算法思想\h3.4.2Prim算法實(shí)現(xiàn)\h3.4.3關(guān)于Prim算法的進(jìn)一步討論\h3.4.4例題解析\h練習(xí)\h3.5判定最小生成樹是否唯一\h3.5.1最小生成樹不唯一的原因分析\h3.5.2判定最小生成樹是否唯一的方法\h3.5.3例題解析\h第4章最短路徑問題\h4.1邊上權(quán)值非負(fù)情形的單源最短路徑問題——Dijkstra算法\h4.1.1算法思想\h4.1.2算法實(shí)現(xiàn)\h4.1.3關(guān)于Dijkstra算法的進(jìn)一步討論\h4.1.4例題解析\h練習(xí)\h4.2邊上權(quán)值為任意值的單源最短路徑問題—Bellman-Ford算法\h4.2.1算法思想\h4.2.2算法實(shí)現(xiàn)\h4.2.3關(guān)于Bellman-Ford算法的進(jìn)一步討論\h4.2.4例題解析\h練習(xí)\h4.3Bellman-Ford算法的改進(jìn)——SPFA算法\h4.3.1算法思想\h4.3.2算法實(shí)現(xiàn)\h4.3.3關(guān)于SPFA算法的進(jìn)一步討論\h4.3.4例題解析\h練習(xí)\h4.4所有頂點(diǎn)之間的最短路徑——Floyd算法\h4.4.1算法思想\h4.4.2算法實(shí)現(xiàn)\h4.4.3關(guān)于Floyd算法的進(jìn)一步分析\h4.4.4例題解析\h練習(xí)\h4.5差分約束系統(tǒng)\h4.5.1差分約束系統(tǒng)與最短路徑\h4.5.2例題解析\h練習(xí)\h第5章可行遍性問題\h5.1歐拉回路\h5.1.1基本概念及定理\h5.1.2歐拉回路的判定\h練習(xí)\h5.2歐拉回路的求解\h5.2.1DFS搜索求解歐拉回路\h5.2.2Fleury（佛羅萊）算法\h練習(xí)\h5.3中國郵遞員問題\h5.4漢密爾頓回路\h5.4.1基本概念及定理\h5.4.2漢密爾頓回路求解\h第6章網(wǎng)絡(luò)流問題\h6.1網(wǎng)絡(luò)最大流\h6.1.1基本概念\h6.1.2最大流最小割定理\h6.1.3網(wǎng)絡(luò)最大流的求解\h6.1.4一般增廣路方法——Ford-Fulkerson算法\h6.1.5最短增廣路算法\h6.1.6連續(xù)最短增廣路算法——Dinic算法\h6.1.7一般預(yù)流推進(jìn)算法\h6.1.8最高標(biāo)號預(yù)流推進(jìn)算法\h6.1.9網(wǎng)絡(luò)最大流算法總結(jié)\h6.1.10例題解析\h練習(xí)\h6.2最小割的求解\h練習(xí)\h6.3流量有上下界的網(wǎng)絡(luò)的最大流和最小流\h6.3.1流量有上下界的容量網(wǎng)絡(luò)\h6.3.2流量有上下界的網(wǎng)絡(luò)的最大流\h6.3.3流量有上下界的網(wǎng)絡(luò)的最小流\h6.3.4例題解析\h練習(xí)\h6.4最小費(fèi)用最大流\h6.4.1基本概念\h6.4.2最小費(fèi)用最大流算法\h6.4.3例題解析\h練習(xí)\h第7章支配集、覆蓋集、獨(dú)立集與匹配\h7.1點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集\h7.1.1點(diǎn)支配集\h7.1.2點(diǎn)覆蓋集\h7.1.3點(diǎn)獨(dú)立集\h7.1.4點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集之間的聯(lián)系\h7.2點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集的求解\h7.2.1邏輯運(yùn)算\h7.2.2極小點(diǎn)支配集的求解\h7.2.3極小點(diǎn)覆蓋集、極大點(diǎn)獨(dú)立集的求解\h7.3邊覆蓋集與邊獨(dú)立集\h7.3.1邊覆蓋集\h7.3.2邊獨(dú)立集（匹配）\h7.3.3最大邊獨(dú)立集（最大匹配）與最小邊覆蓋集之間的聯(lián)系\h7.4匹配問題\h7.4.1完美匹配\h7.4.2二部圖的完備匹配與完美匹配\h7.4.3最佳匹配\h7.4.4匹配問題求解的基本概念及思路\h7.5二部圖最大匹配問題的求解\h7.5.1網(wǎng)絡(luò)流解法\h7.5.2匈牙利算法\h7.5.3例題解析\h練習(xí)\h第8章圖的連通性問題\h8.1基本概念\h8.1.1連通圖與非連通圖\h8.1.2無向圖的點(diǎn)連通性\h8.1.3無向圖的邊連通性\h8.1.4無向圖頂點(diǎn)連通性和邊連通性的聯(lián)系\h8.1.5有向圖的連通性\h8.2無向圖點(diǎn)連通性的求解及應(yīng)用\h8.2.1關(guān)節(jié)點(diǎn)的求解\h8.2.2重連通分量的求解\h8.2.3頂點(diǎn)連通度的求解\h練習(xí)\h8.3無向圖邊連通性的求解及應(yīng)用\h8.3.1割邊的求解\h8.3.2邊雙連通分量的求解\h8.3.3邊連通度的求解\h練習(xí)\h8.4有向圖強(qiáng)連通性的求解及應(yīng)用\h8.4.1有向圖強(qiáng)連通分量的求解算法\h8.4.2有向圖強(qiáng)連通分量的應(yīng)用\h練習(xí)\h第9章平面圖及圖的著色問題\h9.1基本概念\h9.1.1平面圖與非平面圖\h9.1.2區(qū)域與邊界\h9.1.3極大平面圖與極小非平面圖\h9.1.4平面圖的對偶圖\h9.1.5關(guān)于平面圖的一些定理