图论小结

图的存储

• 邻接矩阵
• 邻接表

图的遍历

• DFS（双向DFS）
• BFS（剪枝）

单源最短路径算法

dij

条件：无负权边
贪心思想
分已确定最短路径点，未确定最短路径点。
找已确定点中离起点最近的点，确定边指向的点。
若 w[u,v] <= w[u, vi]，w[,]>0
则 w[u,v] <= w[u, vi] + w[vi, v]
时间复杂度：
邻接矩阵：O(V^2)
V个点*松弛到V点距离

spfa

条件：无
维护无重复元素队列Q
Q初始只有起点

1. 出队得到点A
2. 松弛 d[a] + w[a,i] < d[i]，把被松弛的点i加入队列Q

时间复杂度：
邻接矩阵：O(E) ~ O(V^2)
V个点*松弛到V点距离

不等式组可转换成图
A+n<=B
即有一条从A指向B的边，边权为n

有向图强连通分量G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。