Chapter-6 GraphTheory 第6章 图论

Chapter-6 Graph Theory

第6章 图论

GraphTheory.png

1. Traverse - 遍历

   1. DepthFirstSearch(DFS) - 深度优先搜索

   2. BreadthFirstSearch(BFS) - 广度优先搜索

   3. TopologicalSort - 拓扑排序

   4. EulerCycle - 欧拉回路

2. MinSpanningTree - 最小生成树

   1. Kruskal - Kruskal算法

   2. Prim - Prim算法

3. ShortestPath - 最短路径

   1. BellmanFord - BellmanFord算法

   2. Dijkstra - Dijkstra算法

   3. FloydWarshall - FloydWarshall算法

   4. DifferentConstraints - 差分约束

4. StronglyConnectedComponents - 强连通分支

   1. Kosaraju - Kosaraju算法

   2. Tarjan - Tarjan算法

   3. 2-SAT - 2-SAT问题

5. NetworkFlow - 网络流

   1. EdmondsKarp - EdmondsKarp算法（最大路径增广算法）

   2. PushRelabel - 压入与重标记算法

   3. Dinic - Dinic算法

   4. MinimumCostFlow - 最小费用流

   5. MultipleSourceMultipleSinkMaxflow - 多源点多汇点最大流

6. BinaryMatch - 二分匹配

   1. Hungarian - 匈牙利算法

   2. HopcroftKarp - Hopcroft-Karp算法

   3. MatchToMaxflow - 二分匹配转化为最大流

   4. KuhnMunkres - Kuhn-Munkres算法

   5. Introduction-Domination_Independent_Covering_Clique - 支配集、独立集、覆盖集、团的介绍

   6. WeightedCoveringAndIndependentSet - 最小点权覆盖和最大点权独立集

   7. MinDisjointPathCovering - 最小不相交路径覆盖

   8. MinJointPathCovering - 最小可相交路径覆盖

   9. Coloring - 染色问题

公共代码

Util.h

Util.cpp