图的存储

1. 一般来说，图的存储方式有两种：邻接矩阵和邻接表

2. 对无向图来说，邻接矩阵是一个对称矩阵

3. 邻接矩阵只适用于顶点数目不太大（一般不超过1000）的题目

4. 邻接表：vector<int> Adj[N]   //每个Adj[i]都是一个变长数组vector

图的遍历

const int MAXV = 1000;  //最大顶点数

const int INF = 1000000000;     //设INF为一个很大的数

DFS

DFS遍历图

BFS

BFS遍历图

BFS输出顶点层号

最短路径

最小生成树MST

1. 最小生成树是在一个给定的无向图G(V,E)中求一棵树T，使得这棵树拥有图G中的所有顶点，且所有边都是来自图G中的边，并且满足整棵树的边权之和最小

2. 最小生成树是树，因此其边数等于顶点数减一，且树内一定不会有环

3. 对给定的图G(V,E)，其最小生成树可以不唯一，但其边权之和一定是唯一的

4. 求解最小生成树一般有两种算法，即prim算法与kruskal算法。这两个算法都采用了贪心法的思想，只是贪心的策略不太一样

5. 如果是稠密图（边多）则用prim算法；如果是稀疏图（边少）则用kruskal算法

prim算法--邻接矩阵

prim算法--邻接表

kruskal算法

拓扑排序

拓扑排序一个很重要的应用就是判断一个给定的图是否是有向无环图。

拓扑排序

关键路径

1. AOE网中的最长路径被称为关键路径（强调：关键路径就是AOE网的最长路径），而把关键路径上的活动称为关键活动，显然关键活动会影响整个工程的进度

2. 关键活动是那些不允许拖延的活动，因此这些活动的最早开始时间必须等于最迟开始时间