图论

$\space\space\space\space\space$图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
$\space\space\space\space\space$图论从整体上分为有向图和无向图 我们也将围绕这些讨论

1.如何建图

$\space\space\space\space\space$图的建立大体分为两种 一种是邻接矩阵建图 一种是邻接表建图

贪心上来说 在数据范围足够小或者稠密图的时候 我们用邻接矩阵 而稀疏图的时候我们用邻接表存储
1. 邻接矩阵建图 g[a][b] 存 a -> b
2. 邻接表建图

int h[N], w[M], e[M], ne[M], idx;  链式前向星存图

void add(int a, int b, int c) //从 a->b插入权值为c的边
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
//初始化
void int()
{
    idx = 0;
    memset(h, -1, sizeof h);
}

2.如何跑图

$\space\space\space\space\space$图论大体上分为三个方法

1.dijkstra 时间复杂度 O($n^2 + m$)

2.Bellman-Ford O(n*m)

3.Floyd O($n ^ 3$)

3.图论问题划分

1.最短路问题

2.Floyd拓展应用 – 初步完成

3.最小生成树问题

4.差分约束问题 – 初步完成

5.最近公共祖先问题 –初步完成

6.树上前缀和与差分 –初步完成

6.强连通分量 – 初步完成

7.双连通分量

8.二分图

9.欧拉回路和欧拉路径

10.拓扑排序

11.二SAT