圖論算法理論、實現(xiàn)及應用

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