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