1.1.最小生成树的概念
- 边的权值之和最小的生成树，称为最小生成树
- 最小生成树不唯一
- 连通图本身就是一棵树，则它就是最小生成树
- 最小生成树需连通图，非连通图只能是生成森林
1.2.Prim算法
从某一个顶点开始构建最小生成树，依次加入当前剩余顶点中代价最小的顶点，直到加入所有顶点
时间复杂度：O(|
|)
适用：稠密图（E大）
每一轮开始都循环遍历所有节点，找到当前代价最低且并没有加入树的结点，再次遍历，更新各个结点的代价
1.3.Kruskal算法（库鲁斯卡尔）
每次选择代价最小的一条边，使该边的两个顶点相通，但是，如果原本就相通的两个顶点的边就不选，直到所有顶点相通
时间复杂度：O(
)
适用：稀疏图（E小）
共执行e轮，每轮判断两个结点是否属于同一个结点
2.1.BFS
BFS能求无权图的单源最短路径：用额外两个数组分别存储该顶点的前驱和距离源顶点的距离
#define MaxVertexNum 100
void BFS(Graph G, int v){
Queue Q;
InitQueue(Q);
EnQueue(v);
int q, p;
//dist数组用来存放当前顶点到源顶点的距离，pre存放当前顶点的前驱顶点
int dist[MaxVertexNum] = { 0 }, pre[MaxVertexNum] = { 0 };
bool visited[MaxVertexNum] = { false };
//源顶点的前驱置为-1
pre[v] = -1;
//源顶点标记已访问
visited[v] = true;
//cur标记当前距离顶点的距离
int cur = 0;
while(!IsEmpty(Q)){
DeQueue(Q, p);
cur++;
for (q = FirstNeighbor(G, p); q >= 0; q = NextNeighbor(G, p, q)){
if (!visited[q]) {
//将q设置为已标记
visited[q] = true;
//入队q
EnQueue(Q, p);
//更新q距离源顶点的距离
dist[q] = cur;
//更新q的前驱
pre[q] = p;
}//if
}//for
}//while
}BFS算法求最短路径的局限：仅能求无权图或者各条边权值都相同的图
2.2.Dijkstra算法
2.2.1.Dijkstra算法的基本概念
在求最短路径（单源）的过程中，需要新建四个数组：path（存储到此点路径的上个结点）、dist（距离源点的最短距离）、顶点集S和final（标记是否已经找到最短路径）
第一轮以0为源点，更新以0为起点到各个顶点的数据，如果当前还没有道路能通往该顶点（2，3），则前驱为-1，且距离为 ∞，并把源点0的final标记为已找到
第一轮
第二轮以当前未找到最短路径且当前路径最低的顶点，即顶点4，将其final改为已找到。以0→4的路径更新各个顶点数据。
第二轮
第三轮以当前未找到最短路径且当前路径最低的顶点，即顶点1，将其final改为已找到。以0→4→3的路径更新各个顶点数据。
第三轮
第四轮以当前未找到最短路径且当前路径最低的顶点，即顶点3，将其final改为已找到。以0→4→3→1的路径更新各个顶点数据。
第四轮
第四轮以当前未找到最短路径且当前路径最低的顶点，即顶点5，将其final改为已找到。
第五轮
2.2.2.Dijkstra的时间复杂度
每轮都需要遍历两边数组（顶点集），第一遍查找当前距离最短且未被标记的顶点，第二遍更新以该顶点为路径的信息，一共要执行n - 1轮，因此，时间复杂度为O(
)，即O(
)（与Prime算法的思想很类似）
2.2.3.Dijkstra的不适用情况
当图中边的权值存在负值时，Dijkstra算法并不适用
2.3.Floyd算法
2.3.1.Floyd算法的基本概念
Floyd算法用于计算有向图/无向图的任意两个结点的最短路径
Floyd算法需要新建两个二维数组，A（保存当前最短路径长度）和path（最短路径的前驱）
初始化A和path数组，不允许任何中转
A
| V0 | V1 | V2 | V3 | V4 |
| V0 | 0 | ∞ | 1 | ∞ | 10 |
| V1 | ∞ | 0 | ∞ | 1 | 5 |
| V2 | ∞ | 1 | 0 | ∞ | 7 |
| V3 | ∞ | ∞ | ∞ | 0 | 1 |
| V4 | ∞ | ∞ | ∞ | ∞ | 0 |
path
| V0 | V1 | V2 | V3 | V4 |
| V0 | -1 | -1 | -1 | -1 | -1 |
| V1 | -1 | -1 | -1 | -1 | -1 |
| V2 | -1 | -1 | -1 | -1 | -1 |
| V3 | -1 | -1 | -1 | -1 | -1 |
| V4 | -1 | -1 | -1 | -1 | -1 |
第一轮：允许在V0中转
A
| V0 | V1 | V2 | V3 | V4 |
| V0 | 0 | ∞ | 1 | ∞ | 10 |
| V1 | ∞ | 0 | ∞ | 1 | 5 |
| V2 | ∞ | 1 | 0 | ∞ | 7 |
| V3 | ∞ | ∞ | ∞ | 0 | 1 |
| V4 | ∞ | ∞ | ∞ | ∞ | 0 |
path
| V0 | V1 | V2 | V3 | V4 |
| V0 | -1 | -1 | -1 | -1 | -1 |
| V1 | -1 | -1 | -1 | -1 | -1 |
| V2 | -1 | -1 | -1 | -1 | -1 |
| V3 | -1 | -1 | -1 | -1 | -1 |
| V4 | -1 | -1 | -1 | -1 | -1 |
第二轮：允许在V0、V1中转，更新V2→V3、V2→V4
A
| V0 | V1 | V2 | V3 | V4 |
| V0 | 0 | ∞ | 1 | ∞ | 10 |
| V1 | ∞ | 0 | ∞ | 1 | 5 |
| V2 | ∞ | 1 | 0 | 2 | 6 |
| V3 | ∞ | ∞ | ∞ | 0 | 1 |
| V4 | ∞ | ∞ | ∞ | ∞ | 0 |
path
| V0 | V1 | V2 | V3 | V4 |
| V0 | -1 | -1 | -1 | -1 | -1 |
| V1 | -1 | -1 | -1 | -1 | -1 |
| V2 | -1 | -1 | -1 | 1 | 1 |
| V3 | -1 | -1 | -1 | -1 | -1 |
| V4 | -1 | -1 | -1 | -1 | -1 |
第三轮：允许在V0、V1、V2中转，更新V0→V1、V0→V4、V0→V3
A
| V0 | V1 | V2 | V3 | V4 |
| V0 | 0 | 2 | 1 | 3 | 8 |
| V1 | ∞ | 0 | ∞ | 1 | 5 |
| V2 | ∞ | 1 | 0 | 2 | 6 |
| V3 | ∞ | ∞ | ∞ | 0 | 1 |
| V4 | ∞ | ∞ | ∞ | ∞ | 0 |
path
| V0 | V1 | V2 | V3 | V4 |
| V0 | -1 | 2 | -1 | 2 | 2 |
| V1 | -1 | -1 | -1 | -1 | -1 |
| V2 | -1 | -1 | -1 | 1 | 1 |
| V3 | -1 | -1 | -1 | -1 | -1 |
| V4 | -1 | -1 | -1 | -1 | -1 |
第四轮：允许在V0、V1、V2、V3中转，更新V0→V4、V1→V4、V2→V4
A
| V0 | V1 | V2 | V3 | V4 |
| V0 | 0 | 2 | 1 | 3 | 4 |
| V1 | ∞ | 0 | ∞ | 1 | 2 |
| V2 | ∞ | 1 | 0 | 2 | 3 |
| V3 | ∞ | ∞ | ∞ | 0 | 1 |
| V4 | ∞ | ∞ | ∞ | ∞ | 0 |
path
| V0 | V1 | V2 | V3 | V4 |
| V0 | -1 | 2 | -1 | 2 | 3 |
| V1 | -1 | -1 | -1 | -1 | 3 |
| V2 | -1 | -1 | -1 | 1 | 3 |
| V3 | -1 | -1 | -1 | -1 | -1 |
| V4 | -1 | -1 | -1 | -1 | -1 |
第五轮：允许在V0、V1、V2、V3中转
A
| V0 | V1 | V2 | V3 | V4 |
| V0 | 0 | 2 | 1 | 3 | 4 |
| V1 | ∞ | 0 | ∞ | 1 | 2 |
| V2 | ∞ | 1 | 0 | 2 | 3 |
| V3 | ∞ | ∞ | ∞ | 0 | 1 |
| V4 | ∞ | ∞ | ∞ | ∞ | 0 |
path
| V0 | V1 | V2 | V3 | V4 |
| V0 | -1 | 2 | -1 | 2 | 3 |
| V1 | -1 | -1 | -1 | -1 | 3 |
| V2 | -1 | -1 | -1 | 1 | 3 |
| V3 | -1 | -1 | -1 | -1 | -1 |
| V4 | -1 | -1 | -1 | -1 | -1 |
2.3.2.Floyd算法的复杂度
空间复杂度：创建两个二维数组O(n2)
时间复杂度：三个for循环O(n3)
2.4.最短路径小结
- 无权图：BFS、Dijkstra算法、Floyd算法
- 带权图：Dijkstra算法、Floyd算法
- 带负权值图：Floyd算法
- 带负权值回路图：无
5.时间复杂度：
- BFS：O(|V^2|)（邻接矩阵）或者O(|V|+|E|)（邻接表）
- Dijkstra：O(|V^|2)
- Floyd：O(|V|^3)
6.通常应用场景：
- BFS：无权图单源最短路径
- Dijkstra：有权图单源最短路径（也可以求任意两点路径，重复V次，O(|V|^3）
- Floyd：有权图各个顶点间最短路径
