一. 欧拉图

1. 定义

2. 性质

• 欧拉图均为连通图；

• 无向连通图 G 是欧拉图，则其不含奇数度结点(所有结点度数均为偶数)；

• 无向连通图 G 是欧拉通路，则其没有或有两个奇数度的结点，这两个节点为欧拉通路的起点与终点；

• 有向连通图 D 是欧拉图，则其每个结点的入度=出度；

• 有向连通图 D 是欧拉通路，则其除起点与终点外，其余每个结点的入度=出度；

• 上述两点两点均满足：起始点的入度 = 出度 - 1 ，结束点的出度 = 入度 - 1 或 两个点的入度 = 出度（主要针对含有欧拉图或欧拉回路的图）。

3. 代码

4. 例题

二. 拓扑排序

1. 定义：

2. 性质：

• 图中无环，否则无法进行拓扑排序。

• 统计所有节点的入度，将入度为 0 的节点分离出来；

• 把分离出的节点指向的节点的入度减一；

• 重复上述操作，直到所有的节点都被分离出来；

• 如果最后不存在入度为 0 的节点，说明有环，不存在拓扑排序，即无解。

3. 代码

4. 例题：

三. 最短路

1. 定义

2. Dijkstra算法：

• 声明一个数组 d 来保存源点到各个顶点的最短距离；

• 声明一个保存已经找到了最短路径的顶点的集合 s ；

• 声明一个保存各节点起始节点的数组 path ；

• 初始化：原点 v0 的路径权重被赋为 0 ( d[ v0 ] = 0) 。将顶点 v0 能直接到达的边( v0 , v )，把 d[ v ] 设为该边权重 w ,把 v0 不能直接到达的顶点路径长度设为无穷大 inf 。初始时，集合 s 只有顶点 v0 ；

• 从 d 数组选择最小值，则该值就是源点 v0 到该值对应的顶点的最短路径，把该点加入到 s 中，此时完成一个顶点；

• 判断新加入的顶点是否可以更新到达其他点的路径长度，如果是则替换这些顶点在 d 中的值。

• 重复上述动作，直到 s 中包含了图的所有顶点。

2.1 代码：

2.1.1 优先队列优化（不能处理负边权）

2.1.2 路径还原（待测试）

2.3 例题：

3. Floyd算法：

• 声明一个数组 d 来各个点到各个顶点的最短距离；

• 声明一个数组 path 来保存各节点到各节点的起始节点 ；

• 初始化：将各节点能直接到达的边( v0 , v1 )，把 d[ v0 ][ v1 ] 设为该边权重 w ，起始节点 path[ v0 ][ v1 ] 值设为 v0 ，把各节点不能直接到达的顶点路径长度设为无穷大 inf ，起始节点 path[ v0 ][ v1 ] 值设为 -1 ；

• 遍历所有节点，判断该顶点是否可以更新到达其他点的路径长度，如果是则替换这些顶点在 d 中的值。

• 重复上述动作，直到所有节点均被遍历。

3.1 代码：

3.2 例题

4. spfa 算法

• 算法用一个队列来进行维护，初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，且该点没有在队列中，则将其入队。直到队列为空时算法结束。

• 判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）

4.1 代码

4.2 例题：

四. 最小生成树

1. 定义

2. 性质

3. kruskal算法

3.1 代码

4. Prim算法：

4.1 代码

5. 例题：

五. 网络流

1. 最大流代码