图论算法理论、实现及应用

图论算法理论实现及应用目录\h第1章图的基本概念及图的存储\h1.1基本概念\h1.1.1有向图与无向图\h1.1.2完全图、稀疏图、稠密图\h1.1.3顶点与顶点、顶点与边的关系\h1.1.4顶点的度数及度序列\h1.1.5二部图与完全二部图\h1.1.6图的同构\h1.1.7子图与生成树\h1.1.8路径\h1.1.9连通性\h1.1.10权值、有向网与无向网\h1.2图的存储表示\h1.2.1邻接矩阵\h1.2.2邻接表\h1.2.3关于邻接矩阵和邻接表的进一步讨论\h练习\h第2章图的遍历与活动网络问题\h2.1DFS遍历\h2.1.1DFS算法思想\h2.1.2DFS算法的实现及复杂度分析\h2.1.3例题解析\h练习\h2.2BFS遍历\h2.2.1BFS算法思想\h2.2.2BFS算法的实现及复杂度分析\h2.2.3关于DFS算法和BFS算法的说明\h2.2.4例题解析\h练习\h2.3活动网络——AOV网络\h2.3.1AOV网络与拓扑排序\h2.3.2拓扑排序实现方法\h2.3.3关于拓扑排序的进一步说明\h2.3.4例题解析\h练习\h2.4活动网络——AOE网络\h2.4.1AOE网络与关键路径\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算法实现\h3.3.4Boruvka算法\h3.3.5例题解析\h练习\h3.4普里姆（Prim）算法\h3.4.1Prim算法思想\h3.4.2Prim算法实现\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算法实现\h4.1.3关于Dijkstra算法的进一步讨论\h4.1.4例题解析\h练习\h4.2边上权值为任意值的单源最短路径问题—Bellman-Ford算法\h4.2.1算法思想\h4.2.2算法实现\h4.2.3关于Bellman-Ford算法的进一步讨论\h4.2.4例题解析\h练习\h4.3Bellman-Ford算法的改进——SPFA算法\h4.3.1算法思想\h4.3.2算法实现\h4.3.3关于SPFA算法的进一步讨论\h4.3.4例题解析\h练习\h4.4所有顶点之间的最短路径——Floyd算法\h4.4.1算法思想\h4.4.2算法实现\h4.4.3关于Floyd算法的进一步分析\h4.4.4例题解析\h练习\h4.5差分约束系统\h4.5.1差分约束系统与最短路径\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章网络流问题\h6.1网络最大流\h6.1.1基本概念\h6.1.2最大流最小割定理\h6.1.3网络最大流的求解\h6.1.4一般增广路方法——Ford-Fulkerson算法\h6.1.5最短增广路算法\h6.1.6连续最短增广路算法——Dinic算法\h6.1.7一般预流推进算法\h6.1.8最高标号预流推进算法\h6.1.9网络最大流算法总结\h6.1.10例题解析\h练习\h6.2最小割的求解\h练习\h6.3流量有上下界的网络的最大流和最小流\h6.3.1流量有上下界的容量网络\h6.3.2流量有上下界的网络的最大流\h6.3.3流量有上下界的网络的最小流\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点支配集、点覆盖集、点独立集之间的联系\h7.2点支配集、点覆盖集、点独立集的求解\h7.2.1逻辑运算\h7.2.2极小点支配集的求解\h7.2.3极小点覆盖集、极大点独立集的求解\h7.3边覆盖集与边独立集\h7.3.1边覆盖集\h7.3.2边独立集（匹配）\h7.3.3最大边独立集（最大匹配）与最小边覆盖集之间的联系\h7.4匹配问题\h7.4.1完美匹配\h7.4.2二部图的完备匹配与完美匹配\h7.4.3最佳匹配\h7.4.4匹配问题求解的基本概念及思路\h7.5二部图最大匹配问题的求解\h7.5.1网络流解法\h7.5.2匈牙利算法\h7.5.3例题解析\h练习\h第8章图的连通性问题\h8.1基本概念\h8.1.1连通图与非连通图\h8.1.2无向图的点连通性\h8.1.3无向图的边连通性\h8.1.4无向图顶点连通性和边连通性的联系\h8.1.5有向图的连通性\h8.2无向图点连通性的求解及应用\h8.2.1关节点的求解\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区域与边界\h9.1.3极大平面图与极小非平面图\h9.1.4平面图的对偶图\h9.1.5关于平面图的一些定理