1.最小生成树
1.1.最小生成树的概念
- 边的权值之和最小的生成树,称为最小生成树
- 最小生成树不唯一
- 连通图本身就是一棵树,则它就是最小生成树
- 最小生成树需连通图,非连通图只能是生成森林
1.2.Prim算法
从某一个顶点开始构建最小生成树,依次加入当前剩余顶点中代价最小的顶点,直到加入所有顶点
时间复杂度:O(||)
适用:稠密图(E大)
每一轮开始都循环遍历所有节点,找到当前代价最低且并没有加入树的结点,再次遍历,更新各个结点的代价
1.3.Kruskal算法(库鲁斯卡尔)
每次选择代价最小的一条边,使该边的两个顶点相通,但是,如果原本就相通的两个顶点的边就不选,直到所有顶点相通
时间复杂度:O()
适用:稀疏图(E小)
共执行e轮,每轮判断两个结点是否属于同一个结点
2.最短路径
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:有权图各个顶点间最短路径