图论基础算法

邻接表(adjacency lists)是表示图的标准方法。
如果是稠密图，可以使用邻接矩阵(adjacency matrix)。

BFS(Breadth First Search)，广度优先搜索
DFS(Depth First Search)，深度优先搜索

Topological sort，拓扑排序
适用条件：有向无圈图
DFS方法：将每一次的遍历放在排序数组的末尾（从后往前插，类似树的后续遍历），重复下去。
BFS方法：
1. 计算每个点的入度，将入度为零的点入队。
2. 取队首元素，更新与其相连的剩余点的入度，将新出现的入度为0的点入队。
3. 重复2直到队列为空。

MST(Minimum Spanning Tree)，最小生成树
贪心，适用条件：无向加权图
Kruskal：找权值最小的边，并且所选的边不产生圈。可利用并查集
Prim：每次找一个连接生成树的权值最小的新节点。

Single-Source Shortest Path，单源点最短路径，一个顶点到其他顶点的最短路径。
BFS：多用于无权最短路径
Bellman-Ford：边权值可以为负值，能够判断是否存在负环路，O(VE)，很暴力，效率没有Dijkstra好。
1. 对每条边进行|V|-1次Relax操作
2. 如果存在(u,v)∈E使得dis[u]+w<dis[v]，则存在负权回路，返回False
Dijkstra：边权值不可以为负值，每次新扩展一个距离最短的点，O(V^2)，据说还可以用菲波那契堆来进行优化。
Relax操作

Dijkstra图解


All-Pairs Shortest Paths
Floyd-Warshall：边权可以为负，使用邻接矩阵表示，动态规划的思想，O(V^3)

网络流：一个发点、一个收点，每条边的流量有限制。
最大流问题就是求总流量最大的可行流。
暂时不懂

来自维基、NOCOW和《算法导论》