挖矿网站开发,树莓派做影视网站,深圳上市公司排名,南宁公司网站建设目录
1、dfs(深度优先搜索)
1.1 排列数字
1.2 n皇后问题
搜索顺序1
搜索顺序2
2、bfs(广度优先搜索)
2.1 走迷宫
2.2 八数码
3、树与图的存储
4、树与图的遍历
4.1 树的重心
4.2 图中点的层次
5、拓扑排序
6、最短路问题
6.1 朴素Dijkstra算法
6.2 堆优化Dijks…目录
1、dfs(深度优先搜索)
1.1 排列数字
1.2 n皇后问题
搜索顺序1
搜索顺序2
2、bfs(广度优先搜索)
2.1 走迷宫
2.2 八数码
3、树与图的存储
4、树与图的遍历
4.1 树的重心
4.2 图中点的层次
5、拓扑排序
6、最短路问题
6.1 朴素Dijkstra算法
6.2 堆优化Dijkstra算法
6.3 Bellman ford算法
6.4 spfa算法
spfa求最短路
spfa判断负环
6.5 Floyd算法
7、最小生成树
7.1 概念
7.2 Prim算法
7.3 Kruskal算法
8、二分图
8.1 概念
8.2 染色法
8.2 匈牙利算法 首先我们先整体说一下dfs和bfs。dfs是深度优先遍历是一直往下搜索搜索的路径是一颗树到达叶节点就回溯每次只需要保存路径上的点即可不具有最短路性质。bfs是宽度优先搜索是一层一层搜索的每次需要保存一层的结点具有最短路性质所以当题目有最小步数、最短距离、最少操作数等问题时都可考虑使用dfs。
1、dfs(深度优先搜索)
dfs是深度优先搜索是一条路走到结束再去另一条路 图中数字就是遍历到的顺序。其实现是利用数据结构栈来实现的注意并不是真的创建一个栈而是用内存中的栈。其空间复杂度是O(h)h是树的高度因为每次只需要记录一条路径上的所有结点。不具有最短性也就是说第一次遍历到一个点时不是起点到这个点的最短路径上面那幅图无法演示因为是树路径是唯一的。 将树改为图会发现起点A到H的最短距离为3而第一次遍历到H是路径为4 dfs最重要的两点就是回溯和剪枝
我们以题目为例讲解
1.1 排列数字
842. 排列数字 - AcWing题库 这道题需要用一个path数组来记录当前的这条路径的状态用一个bool数组来记录那些值没有被用过true说明已经被用过了。当数组中的树的个数等于输入的n时则输出然后回溯注意回溯的时候一定要恢复状态
#includeiostream
using namespace std;
const int N 10;
int n 0;
int path[N]; // 记录当前路径的情况
bool st[N]; // 记录数是否被使用过若为true则被使用过
void dfs(int u)
{if (u n) // 当u等于n时说明全部都填满了可以输出了{for (int i 0; i n; i) printf(%d , path[i]);printf(\n);return;}for (int i 1; i n; i){if (!st[i]) // 若st[i]是false表示没用过{path[u] i;st[i] true;dfs(u 1);st[i] false; // 恢复,path数组的值不需要恢复因为会被覆盖}}
}
int main()
{scanf(%d, n);dfs(0);return 0;
}
1.2 n皇后问题
843. n-皇后问题 - AcWing题库
搜索顺序1
我们可以枚举每一行皇后放的位置 此时可能会出现有皇后在同一条对角线的情况所以没得到一种方案就需要判断一下是否有皇后在同一对角线若有说明这个方案不行。 也可以一边放入一遍检查如 此时有2个皇后位于同一对角线上就不需要再往后走了这个过程称为剪枝。剪枝就是判断当前路径不合法或者一定不如最优解时让这条路径不再往下搜索直接回溯
这道题的代码实现中需要使用bool数组来记录每一条对角线上是否有皇后所以这里先介绍一下正对角线和反对角线以及这些对角线在图中的编号
假设棋盘行数为n则对角线条数 2 * n - 1
#include iostreamusing namespace std;const int N 20;int n;
char g[N][N]; // 用来存放棋盘
bool col[N], dg[N * 2], udg[N * 2]; // 记录某一位置的列、正反对角线上是否有元素void dfs(int u)
{if (u n) // 8行全放满了{for (int i 0; i n; i ) puts(g[i]);puts();return;}for (int i 0; i n; i )if (!col[i] !dg[u i] !udg[n - u i]) // 若当前位置所在列、正反对角线都没有元素则放入{g[u][i] Q;col[i] dg[u i] udg[n - u i] true;dfs(u 1);col[i] dg[u i] udg[n - u i] false; // 恢复状态g[u][i] .;}
}int main()
{cin n;for (int i 0; i n; i )for (int j 0; j n; j )g[i][j] .;dfs(0);return 0;
}
搜索顺序2
枚举每一个格子每个格子都有放和不放两种选择一行一行枚举
#include iostreamusing namespace std;const int N 10;int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];void dfs(int x, int y, int s) // s是记录当前放了几个皇后
{if (s n) return; // 若s n说明放多了1个不需要再往下走并且在上一层递归s n时没有x n此时这种情况是不合法的所以没有必要继续往下走if (y n) y 0, x ; // 当y越界时到下一行的第一列if (x n) // 当x n时说明整个棋盘遍历完了{if (s n) // 若此时s n说明是一种正确情况{for (int i 0; i n; i ) puts(g[i]);puts();}return;}// 当前位置不放直接前往下一个位置g[x][y] .;dfs(x, y 1, s);// 若当前位置所在行、所在列、所在正反对角线都没有皇后则可以放if (!row[x] !col[y] !dg[x y] !udg[x - y n]){row[x] col[y] dg[x y] udg[x - y n] true;g[x][y] Q;dfs(x, y 1, s 1); // 前往下一个格子此时s要加1g[x][y] .; // 恢复现场row[x] col[y] dg[x y] udg[x - y n] false;}
}int main()
{cin n;dfs(0, 0, 0);return 0;
}
2、bfs(广度优先搜索)
2.1 走迷宫
844. 走迷宫 - AcWing题库
广度优先搜索是一层一层搜索的每次向最近的一个搜索 这是使用广度优先搜索来遍历迷宫红色代表这个点是第几个走到的点会发现bfs具有最短性也就是每一个点第一次被遍历到时所走的路径都是从起点到这个点的最短路径。当然最短性只有当边的权重都是1时才具有也就是说最短路问题只有当所有边的权重都是1时才能用深搜做 深搜的实现是利用队列来实现的。
#include iostream
#include algorithm
#include queue
#include cstring
using namespace std;
typedef pairint, int PII; // 使用pair来存储在地图中的位置const int N 110;int n, m;
int g[N][N], d[N][N]; // g数组用来存储地图d数组用来存储起点到这个点的最短距离int bfs()
{queuePII q;memset(d, -1, sizeof(d)); // 将d初始化为-1当d上一个位置为-1时说明这个点没有走过d[0][0] 0;q.push({0, 0});int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; // 这两个数组是为了方便向当前位置的四个方向走while (q.size()) // 只要队列不为空就继续走不为空说明还有地方可走{auto t q.front(); // 队头就是当前所处的位置q.pop();for (int i 0; i 4; i ) // 检查四个方向是否合法若合法则可走将位置加进队列{int x t.first dx[i], y t.second dy[i];if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1) // 若位置合法则可以走{d[x][y] d[t.first][t.second] 1;q.push({x, y});}}}return d[n - 1][m - 1];
}int main()
{scanf(%d%d, n, m);for(int i 0;i n;i)for(int j 0;j m;j)scanf(%d, g[i][j]);cout bfs() endl;return 0;
}
2.2 八数码
845. 八数码 - AcWing题库
这道题是求最少交换次数所以使用bfs。 我们每次都让x与上下左右的数交换直到变成有序。第一个难点在于如何在x移动到某个位置后对二维数组进行表示难道是queue里面存二维数组吗显然不是的我们可以使用一个字符串来存储这个二维数组并通过坐标关系实现一维和二维、二维和一维之间的相互转换。第二个难点在于如何在x移动到某个位置后表示出这个位置是从起始状态移动了几次到达这个状态的也就是之前的dist数组这里我们可以直接使用一个哈希表。
在3*3矩阵中一维坐标与二维坐标的相互转换 (1)假设一维坐标k转换成二维坐标后是(k / 3, k % 3) (2)假设二维坐标(x, y)转换成一维坐标后是3 * x y
#include iostream
#include algorithm
#include unordered_map
#include queueusing namespace std;int bfs(string state)
{queuestring q;unordered_mapstring, int d;q.push(state);d[state] 0;int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};string end 12345678x; // 若字符串成了这样说明移动好了直接返回结果while (q.size()){auto t q.front();q.pop();if (t end) return d[t];// 当前t不与end相同需要进行状态转移// 状态转移首先需要知道当前状态的x在什么位置如何将其上下左右移动成新的状态int distance d[t];int k t.find(x); // k就是x在一维中的坐标int x k / 3, y k % 3; // 转换成二维坐标for (int i 0; i 4; i ){int a x dx[i], b y dy[i];if (a 0 a 3 b 0 b 3){swap(t[a * 3 b], t[k]); // 交换x与上下左右的某一个值if (!d.count(t)) // 若更新后的状态之前没有搜索过就加入队列和unordered_map{d[t] distance 1;q.push(t);}swap(t[a * 3 b], t[k]); // 一定要恢复现场}}}return -1;
}int main()
{char s;string state; // state是起始状态for (int i 0; i 9; i ){cin s;state s;}cout bfs(state) endl;return 0;
}
3、树与图的存储
树是无环连通图也就是一种特殊的图所以我们看图的存储即可。无向图是一种特殊的有向图所以看有向图即可。有向图的存储方式有两种邻接矩阵和邻接表
邻接矩阵
邻接矩阵就是一个二维数组g[a][b]存储的是a - b的信息若边有权重则g[a][b]存的就是权重若没有权重g[a][b]存的就是一个bool值。邻接矩阵不能存储重边只能保留1条。
邻接表
邻接表就是给每一个结点都开一个单链表每个单链表存的就是这个点可以走到哪些点。若一个图中有n个结点则邻接表中就有n个单链表在前面学习单链表时我们给head初始化为-1现在就给h都初始化为-1
#includeiostream
#includestring
#includealgorithm
using namespace std;const int N 1e5 10, M 2 * N; // 因为是有向图所以e和ne需要开2倍的N
int h[N], e[M], ne[M], idx; // h存的是n个链表的链表头void add(int a, int b) // 插入边a - b
{e[idx] b, ne[idx] h[a], h[a] idx ;
}int main()
{memset(h, -1, sizeof(h)); // 将链表头都初始化为-1表示每一个链表都没有元素return 0;
}
4、树与图的遍历
与树与图的存储类似这里只看有向图的遍历
有向图的遍历有深度优先遍历和广度优先遍历两种。 无论是深度优先遍历还是广度优先遍历每个结点都只会遍历一遍所以在实现时会开一个bool数组来存哪些点已经被遍历过了。
4.1 树的重心
846. 树的重心 - AcWing题库
我们以这个案例来看 所以这道题的思路就是遍历每个点并将遍历到的那个点删除统计一下删除了每个点之后剩下的连通块中点数的最大值最后再取所有最大值中的最小值即可。
现在的问题就是如何在删除了一个结点之后求剩下的连通块中点数的最大值。 使用dfs因为dfs能够知道子树的大小。遍历到4时是从1下来的所以只会向下4向下走的过程中就能够知道3、6这两颗子树的点数再1就是4这颗子树的点数了。 删除一个结点后它的子树都会是一个连通块
#includeiostream
#includestring
#includealgorithm
#includecstring
using namespace std;const int N 1e5 10, M 2 * N; // 因为是有向图所以e和ne需要开2倍的N
int h[N], e[M], ne[M], idx; // h存的是n个链表的链表头
bool st[N]; // st记录那些结点被遍历过那些没有true表示被遍历过了
int ans N, n; // ans存的是最大值的最小值也就是最终结果void add(int a, int b) // 插入边a - b
{e[idx] b, ne[idx] h[a], h[a] idx ;
}// 以u为根的子树中点的数量
int dfs(int u)
{st[u] true; // 标记一下已经被搜过了// sum用来记录当前子树点的个数并且当前所在的这个结点也算1个所以sum从1开始// res存把当前结点删除后剩下连通块中点的最大值int sum 1, res 0;for(int i h[u]; i ! -1; i ne[i]) // 遍历当前结点的所有孩子{int j e[i];if(!st[j]) // 如果这个孩子没有被搜索过则去搜索{// s是当前树的子树的大小int s dfs(j);res max(res, s);sum s;}}// 循环中res只是与当前结点的子树相比较结点删除后上面的一大块也是连通块所以也要与之比较res max(res, n - sum);ans min(ans, res);return sum;}int main()
{cin n;memset(h, -1, sizeof(h)); // 将链表头都初始化为-1表示每一个链表都没有元素for(int i 0;i n - 1;i){int a, b;cin a b;add(a, b), add(b, a);}dfs(1); // dfs(1)表示从第1个点开始搜索cout ans endl;return 0;
}
4.2 图中点的层次
847. 图中点的层次 - AcWing题库
所有边的长度都是1说明可以使用宽搜来求最短路 这里会用一个d数组来存起点搜索到一个点的最短距离。思路首先将起点放进队列写一个while循环只要队列不为空就一直循环每次取出队头t拓展t的所有邻点x注意只有当x没有被遍历过时才会去拓展因为若x没有被遍历过走过去就是最短路若已经被遍历过了再走就不是最短路了若x没有被遍历过则将x放进队列并且d[x] d[t] 1
#include cstdio
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n, m;
int h[N], e[N], ne[N], idx;
int d[N]; // d是用来存距离的void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}int bfs()
{// 将d数组都初始化为-1这样可以不需要开bool数组只要d数组的值是-1说明这个点还没有被搜索过memset(d, -1, sizeof(d)); queueint q;d[1] 0; // 从1号结点出发q.push(1);while (q.size()) // 只要队列不为空就继续搜索{int t q.front();q.pop();for (int i h[t]; i ! -1; i ne[i]) // 搜索队头的邻点{int j e[i];if (d[j] -1) // 若邻点没有被搜索过则搜索{d[j] d[t] 1; q.push(j);}}}return d[n];
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof(h));for (int i 0; i m; i ){int a, b;scanf(%d%d, a, b);add(a, b);}cout bfs() endl;return 0;
}
5、拓扑排序
848. 有向图的拓扑序列 - AcWing题库
图宽搜的一个重要应用就是求拓扑序列拓扑序列若一个由图中所有点构成的序列 AA 满足对于图中的每条边 (x,y)(x,y)xx 在 AA 中都出现在 yy 之前则称 AA 是该图的一个拓扑序列。图的拓扑排序只有有向无环图才有有向无环图也被称为拓扑图
任何一个入度为0的点都可以作为拓扑排序的起点。正是因为这个宽搜才可获取拓扑序列。具体做法是首先我们将入度为0的点全都放进队列中也就是说这些入度为0的点全都是我们搜索的起点。然后再依次取出队头的点去搜索它的邻点注意因为队头已经放进拓扑序列所以它的邻点的入度都需要-1当邻点的入度是0时就将邻点放进拓扑序列若到最后全部点都放进了队列则这个图是有拓扑序列的并且队列中的就是拓扑序列因为我们是先放入度为0的点然后慢慢往入度为0的点周边搜索的所以队列中的序列就是拓扑序列 若一个图中存在环则这个环上的点一定不会入队列的。一个无环图一定存在一个入度为0的点
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010;int n, m;
int h[N], e[N], ne[N], idx;
int d[N]; // d[i]表示的是i这个点的入度
int q[N]; // 队列void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}bool topsort() // 返回值是这个图是否有拓扑序列
{int hh 0, tt -1;for (int i 1; i n; i ) // 遍历一下图所有顶点if (!d[i]) // 若入度为0则说明这个点可以进入序列了将其放进队列中q[ tt] i;while (hh tt){int t q[hh ]; // 获取队头元素并弹出队头元素这里只是让hh所以后面依然可以打印出来for (int i h[t]; i ! -1; i ne[i]) // 搜索队头元素的邻点{int j e[i];// 因为队头这个点已经被放进拓扑序列里了所以它的邻点的入度要-1if (-- d[j] 0) // 若邻点的入度-1后变成0说明也可以进入队列了q[ tt] j;}}return tt n - 1; // 若全部点都放进了队列则这个图是有拓扑序列的
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof(h));for (int i 0; i m; i ){int a, b;scanf(%d%d, a, b);add(a, b);d[b] ;}if (!topsort()) puts(-1);else{for (int i 0; i n; i ) printf(%d , q[i]);puts();}return 0;
}
注意一个有向无环图的拓扑序列不一定是唯一的此题可输出任何一个拓扑序列
6、最短路问题 说明几个名词源点起点 汇点终点 n 点数 m 边数 稠密图通常指的是m约等于n^2的图此时使用邻接矩阵存储更好 稀疏图通常指的是m约等于n的图此时使用邻接表存储更好
最短路问题重点是如何将原问题抽象成最短路如何定义点和边难点是建图
6.1 朴素Dijkstra算法
849. Dijkstra求最短路 I - AcWing题库
朴素版本的Dijkstra算法和堆优化的Dijkstra算法思想是一致的只是在实现的时候堆优化的Dijkstra算法使用了堆来进行优化。不是说堆优化的Dijkstra算法一定比朴素版本的Dijkstra算法更好当图为稠密图时朴素版本的Dijkstra算法更好当图为稀疏图的时候堆优化的Dijkstra算法更好。
接下来就来讲解Dijkstra算法的过程。假设我们现在有下面这张图从0号点出发要求求出0到每个点的最短路径 这张图的存储可以使用邻接矩阵或者邻接表。此外还需要开另外两个数组dist数组和bool类型的st数组。dist数组用来存储每个结点的最短路径st数组存放每个结点是否已经确定了最短路径。dist数组初始化为全是正无穷并dist[0] 0因为起点是0号点此时不需要标记0号结点为已经确定最短路径st数组初始化为全为false。进入循环每层循环获取一个点的最短路径。每次循环首先在没有确定最短路径的点中找一个距离起点最近的点并将其标记为已经确定最短路径然后更新这个点的邻点到起点的距离假设我们现在找到的这个点编号为t它的一个邻点是jt到j的边的权重是x更新t这个点的邻点j的距离意思就是dist[j] min(dist[j], dist[t] x)。这里注意一个点如果现在所在这个点的某个邻点已经确定了最短路径可以不用取更新这个邻点的最短路径当然更新也没事因为已经确定了最短路径那么一定是最短路径不会被更新。
我们现在来演示一下上面的过程 首先我们进行初始化:dist数组初始化为全是正无穷并dist[0] 0因为起点是0号点此时不需要标记0号结点为已经确定最短路径st数组初始化为全为false。 进入循环此时在没有确定最短路径的点中(也就是st为false的点中)找一个距离起点最近的点(也就是dist最小的点)很明显这里就是0号点选中0号点后将0号点标记成已经确定了最短路径。然后看0号点的邻点也就是1号点和7号点0到1的边的权重是40到7的边的权重是8所以dist[1] min(inf, dist[0] 4) 4,dist[7] min(inf, dist[0] 8) 8 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是1号点选中1号点将1号点标记为已经确定了最短路径。然后看1号点的邻点是2和7。dist[2] min(inf, dist[1] 8) 12, dist[7] min(8, dist[1] 11) 8 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是7号点选中7号点将7号点标记为已经确定了最短路径。然后看7号点的邻点是1、6、8。dist[1] min(4, dist[7] 11) 4, dist[6] min(inf, dist[7] 1) 9, dis[8] (inf, dist[7] 7) 15实际上这里的1已经是确定了最短路径可以不看的为了与后面代码相关联这里就看了也可以说明即使看了也是不会再更新的。 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是6号点选中6号点将6号点标记为已经确定了最短路径。然后看6号点的邻点是5、7、8。dist[5] min(inf, dist[6] 2) 11, dist[7] min(8, dist[6] 1) 8, dis[8] (15, dist[6] 6) 15 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是5号点选中5号点将5号点标记为已经确定了最短路径。然后看5号点的邻点是2、3、4。dist[2] min(12, dist[5] 4) 12, dist[3] min(inf, dist[5] 14) 25, dis[4] (inf, dist[5] 10) 21 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是2号点选中2号点将2号点标记为已经确定了最短路径。然后看2号点的邻点是1、3、5、8。dist[1] min(4, dist[2] 8) 4, dist[3] min(25, dist[2] 7) 19, dis[5] (11, dist[2] 4) 11, dist[8] min(15, dist[2] 2) 14 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是8号点选中8号点将8号点标记为已经确定了最短路径。然后看8号点的邻点是2、6、7。dist[2] min(12, dist[8] 2) 12, dist[6] min(9, dist[8] 6) 9, dis[7] (8, dist[8] 7) 8 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是3号点选中3号点将3号点标记为已经确定了最短路径。然后看3号点的邻点是2、4、5。dist[2] min(12, dist[3] 7) 12, dist[4] min(21, dist[3] 9) 21, dis[5] (11, dist[3] 14) 11 再进入一次循环在没有确定最短路径的点中找一个距离起点最近的点很明显就是4号点选中4号点将4号点标记为已经确定了最短路径。然后看4号点的邻点是3、5。dist[3] min(19, dist[4] 9) 19, dist[5] min(11, dist[4] 10) 11 这就是最终结果
会发现每进行一次循环就能够确定一个点的最短距离
这道题是一个稠密图所以使用邻接矩阵。有向图与无向图是类似的。这道题有重边因为邻接矩阵不能存储重边所以存储一条权重最小的即可。自环是不需要管的因为对于权重都为正的图自环一定不会出现在最短路中。
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 510;int n, m;
int g[N][N]; // 邻接矩阵
int dist[N]; // 存放每个结点的最短路径
bool st[N]; // 存放每个结点是否已经确定了最短路径int dijkstra()
{memset(dist, 0x3f, sizeof(dist)); // 给每个结点的最短路径都初始化为无穷大dist[1] 0; // 从1号点出发所以1号点的距离为0for (int i 0; i n - 1; i ){// 找到没有确定最短路径的点中距离起点最近的点int t -1;for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;// 这道题是找的到n号点的最短距离如果提前确定n号点的最短距离可以直接出循环if(t n) break;// 更新找到的点的邻点的距离for (int j 1; j n; j )if(!st[j]) dist[j] min(dist[j], dist[t] g[t][j]); // 只有当点没有确定距离才更新// 将找到的点标记为已经确定了最短路径st[t] true;}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf(%d%d, n, m);memset(g, 0x3f, sizeof(g));while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);// 会有重边邻接矩阵中存放最短的边即可g[a][b] min(g[a][b], c);}printf(%d\n, dijkstra());return 0;
}
一共有n个点所以为了确定这n个点的最短路径会进行n次循环而每次循环内部在找每个点的邻点时也会进行一次次数为n的循环所以朴素Dijkstra算法的时间复杂度是O(n^2)
6.2 堆优化Dijkstra算法
850. Dijkstra求最短路 II - AcWing题库
我们先来分析一下前面朴素Dijkstra算法的每一步的时间复杂度 (1)外层有一个次数为n的for循环对于每一次循环要找到没有确定最短距离的点中距离起点最近的点一共有n个点要循环n次所以这一个步骤总体的时间复杂度就是O(n^2) (2)更新找到点的邻点的距离若加上只有当邻点没有确定最短距离才去更新的话外层循环n次会遍历到所有的边时间复杂度是O(m) (3)将每个点标记为已经确定了最短路径一共有n个点时间复杂度是O(n)
Dijkstra算法主要就做了这几件事情可以看出其中时间复杂度最高的就是找没有确定最短距离的点中距离起点最近的点这一步操作。在一堆数中找一个最小的点此时就可以使用小根堆来存储所有点到起点的最短距离。此时上面的操作(1)时间复杂度就变成了O(n)但此时(2)的时间复杂度会有变化因为修改堆中的一个值时间复杂度是O(logn)而一共有m次时间复杂度就是O(mlogn)。此时整个算法的时间复杂度就是O(mlogn)
这里的堆可以使用CSTL中的priority_queue但priority_queue不能修改一个点的值也就是我们如果更新了一个点到起点的距离不能直接修改只能插入一个新的结点这样堆中的结点个数不是n可能是m所以真正要算时间复杂度的话使用priority_queue的时间复杂度是O(mlogm)但因为m n^2logm 2logn随意mlogn和mlogm是一个等级的所以通常说堆优化的Dijkstra算法的时间复杂度是O(mlogn)。若是使用我们前面手写的堆就可以修改堆中的值从而保证堆中结点个数永远是n
在这道题中因为n是1e5级别的如果使用朴素Dijkstra算法一定会超时所以使用堆优化Dijkstra算法。这道题是稀疏图所以使用邻接表。
优先队列中可能会存在很多冗余如1号点可能存在有距离为10也可能存在有距离为15。若遇到已经确定了最短距离的直接continue
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;typedef pairint, int PII; const int N 1e6 10;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}int dijkstra()
{memset(dist, 0x3f, sizeof(dist));dist[1] 0;priority_queuePII, vectorPII, greaterPII heap; // 创建小根堆用来存放一个结点的最短距离// pair的second存储的是几号点first存储的是second号点到起点的距离heap.push({0, 1});while (heap.size()){auto t heap.top();heap.pop();int ver t.second, distance t.first;if (st[ver]) continue; // 若ver号点已经确定了最短路径则continuest[ver] true;for (int i h[ver]; i ! -1; i ne[i]) // 遍历找到的这个点的所有邻点{int j e[i]; // j是邻点的编号if (dist[j] dist[ver] w[i]){dist[j] dist[ver] w[i];heap.push({dist[j], j}); // 更新了j号点的最短距离所以将其放入堆}}}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof(h));while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}printf(%d\n, dijkstra());return 0;
}
6.3 Bellman ford算法
853. 有边数限制的最短路 - AcWing题库
bellman ford算法是用来求存在负权边的最短路问题的算法。 在bellman ford算法中存储一个图并不一定要使用邻接表、邻接矩阵可以使用一个结构体数组来存储每个结构体内有a、b、w三个参数表示a - b这条边的权重是w负权回路是指一个回路中所有边的权重相加是负数有负权回路时不一定存在最短路 像这幅图中2、3、4这三个点构成的回路就是负权回路假设我们现在要求1到5的最短路径若不绕圈路径长度是10绕一圈路径长度是9绕两圈路径长度是8若绕无数圈则长度可以是负无穷也就不存在最短路了。 上面说了是不一定存在最短路所以也是有可能存在的 假设现在从1号点出发要求到6号点的最短距离很明显就是7是存在的。所以存在负权回路时只有当负权回路在要求最短距离的点的路径上才不存在最短距离
在Bellman ford算法中我们也是需要先定义一个dist数组并将其初始化为权都是正无穷dist[1] 0Bellman ford算法主要的步骤如下 外层的for循环需要循环n次假设我们现在循环了k次此时的dist数组的意义是从1号点出发结果不超过k条边到每个点的最短距离。当迭代到第n次时若还更新了某个点的最短距离说明起点到这个点的路径上有n条边有n 1个点而点一共就n个所以在这条路径上一定有重复的点也就是有环并且这个环一定是一个负环。应用这个性质Bellman ford算法也可以用来判断是否有负环。
spfa算法是Bellman ford算法的优化在各方面都优于Bellman ford算法但是这道题只能使用Bellman ford算法因为spfa算法是要求图中一定不能有负环的。这道题因为最多只能经过k条边也就是说在环中最多转k圈所以可以忽略负环的影响。并且这道题是有边数限制的spfa算法也无法完成
注意在上面的松弛操作中更新dist[b]时不能直接使用dist[a]来进行更新 k 1是指从1出发最多经过1条边到达其他点的最短距离会发现dist[3]出错了出错的原因是dist[2]更新了。所以我们不应该使用dist[a]因为当dist[a]更新了就会出错若dist[a]更新了我们应该使用原先的值所以我们再开一个数组last来进行备份存放原先的值。
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 510, M 10010;struct Edge
{int a, b, c;
}edges[M]; // edge数组用来存储图int n, m, k;
int dist[N]; // 存储最短路径
int last[N]; // 存储备份void bellman_ford()
{memset(dist, 0x3f, sizeof(dist));dist[1] 0;for (int i 0; i k; i ){memcpy(last, dist, sizeof dist); // 备份for (int j 0; j m; j ){auto e edges[j];dist[e.b] min(dist[e.b], last[e.a] e.c);}}
}int main()
{scanf(%d%d%d, n, m, k);for (int i 0; i m; i ){int a, b, c;scanf(%d%d%d, a, b, c);edges[i] {a, b, c};}bellman_ford();if (dist[n] 0x3f3f3f3f / 2) puts(impossible);else printf(%d\n, dist[n]);return 0;
}
这里讲解一下为什么main函数中判断没有经过k条边从1到n的最短路径不是dist[n] 0x3f3f3f3f 减的话不会减太多边的长度最长是10000最多也就减500次
Bellman ford算法的时间复杂度是O(mn)
6.4 spfa算法
spfa算法是基于Bellman ford算法的一个优化只要没有负环就可以使用spfa算法而99.9%的最短路问题都是没有负环的所以有负权边的图推荐使用spfa算法 Bellman ford算法每一次迭代都需要去遍历所有的边去更新但每次迭代不一定所有的边都会更新也就是dist[b]不一定每次都会变小spfa就是对这个进行优化 我们会发现dist[b]变小一定是由于dist[a]变小了。所以我们可以用一个队列来存储所有变小了的结点初始时将起点放入队列。每一次操作将队列中的1个元素拿出更新其后继元素的最短路径距离若后继元素的最短路径距离变小了就放入队列。只要队列不为空就一直操作也就是更新过谁就拿谁来更新别人。 注意将一个结点放入队列时若这个队列中已经有这个点了不需要重复放入所以要开一个bool数组来存放队列中有那些元素
大部分正权图的最短路问题也可以使用spfa算法有可能会被卡就使用堆优化的Dijkstra算法并且没有被卡时使用spfa算法的时间还能更快
spfa求最短路
851. spfa求最短路 - AcWing题库
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N]; // 存储一个点是否在队列中防止重复加入void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}int spfa()
{memset(dist, 0x3f, sizeof(dist));dist[1] 0;queueint q;q.push(1);st[1] true;while (q.size()){int t q.front();q.pop();st[t] false;for (int i h[t]; i ! -1; i ne[i]) // 遍历减小的点的所有后继结点{int j e[i];if (dist[j] dist[t] w[i]){dist[j] dist[t] w[i];if (!st[j]){q.push(j);st[j] true;}}}}return dist[n];
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof(h));while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}int t spfa();if (t 0x3f3f3f3f) puts(impossible);else printf(%d\n, t);return 0;
}
spfa判断负环
852. spfa判断负环 - AcWing题库
spfa算法也可以用来判断一个图中是否有负环 我们使用dist数组来存储结点的最短路径长度使用cnt存储从起点到某一点的最短路径经过了几条边。如dist[x]是1到x的最短路径长度cnt[x]是1到x的最短路径这条路径上有几条边。假设边t - x,权重为wdist[x] dist[t] xcot[x] cnt[t] 1 若更新到某一个点kcnt[k] n也就是说从起点到这个点之间有n条边也就有n 1个点而一共就n个点所以一定有重复的点也就一定有环而这是最短路正权回路是一定不会进去的只有负权回路会进去也就一定存在负环
这道题不需要将dist初始化因为一开始并不是只将1放入队列这道题是判断图中是否有负环而不是判断是否存在从1开始的负环负环可能有1号点到不了 如这个情况1号点无法加入负环。所以一开始就直接将所有点都放入队列。
6.5 Floyd算法
Floyd算法是处理多源汇最短路问题的算法Floyd算法我们使用邻接矩阵来存储图 其核心步骤是3层for循环 3层for循环结束之后d[i][j]存的就是从i到j的最短路的距离 Floyd算法可以处理负权图但不能处理有负权回路的图 这道题的输入中有自环因为不存在负权回路所以自环的边权重一定是正的重边存最小的即可 初始化时d[i][i]初始化为0其余为正无穷
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 210, INF 1e9;int n, m, Q;
int d[N][N];void floyd()
{for (int k 1; k n; k )for (int i 1; i n; i )for (int j 1; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);
}int main()
{scanf(%d%d%d, n, m, Q);for (int i 1; i n; i )for (int j 1; j n; j )if (i j) d[i][j] 0;else d[i][j] INF;while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);d[a][b] min(d[a][b], c);}floyd();while (Q -- ){int a, b;scanf(%d%d, a, b);int t d[a][b];if (t INF / 2) puts(impossible);else printf(%d\n, t);}return 0;
}
7、最小生成树
7.1 概念
先来看一下最小生成树的概念最小生成树就是一颗树也就是一个无环连通图若有n个点则有n - 1条边。一般是从一个无向图中求出一颗最小生成树此时这颗树要满足的是所以边的权重相加是最小的。从一个无向图中求出最小生成树的算法有Prim算法和Kruskal算法 从时间复杂度可看出稠密图适合使用朴素版的Prim算法。对于稀疏图使用另外两个因为m n^2所以O(mlogn)和O(mlogm)是一个级别的因为堆优化版的Prim算法相较于Kruskal算法写起来更复杂所以我们通常不会使用堆优化版Prim算法而是使用Kruskal算法 一个图也是有可能不存在最小生成树的是当所有点不连通时 图中有无负权边都可以求
7.2 Prim算法
858. Prim算法求最小生成树 - AcWing题库
Prim算法也可称为加点法。步骤是随意选一个点其他点还没有拓展到每次从我们没有拓展到的点中找一个距离已经拓展到的点最近的点(找已经拓展的点与没有拓展的点之间的边中权重最小的)连接最近的这个点让其变成已经拓展到直到将所有的点都拓展到此时就是最小生成树
我们以下面这幅图为例我们从0号点出发已经拓展到的点用红色标记拓展的边用绿色标记 我们从0号点出发 此时拓展到的点只有0与没有拓展到的点有3条边我们从中选择权重最小的(也就是连接距离最近的点)很明显最短的就是0和2中间权重为1的边连接并将2变成已经拓展的点 此时拓展到的点有0和2与没有拓展到的点间有6条边其中权重最小的是4会发现有2条2和3之间、2和5之间此时随便选一条即可这也说明了一个图的最小生成树是不唯一的我们选择拓展3 依据上面的步骤可以最终得到 如果我们在上面不选择连接2和3选择连接2和5的话可以得到 这两个都是最小生成树
我们来看是如何使用代码来实现这个过程的。我们将所有的点分成两个部分一部分是已经拓展到的另一部分是还没有拓展到的。使用dist数组来存储还没拓展到的点到已经拓展到的点的最短距离(这里的意思是指还没拓展到的点到已经拓展到的点的这个集合的最短距离)初始化全为正无穷因为最先开始是没有一个点被拓展到的。使用st数组来表示一个点是否被拓展到。共n次循环每一次循环拓展一个点。因为这道题要求返回最小生成树所有边权重之和所以用一个变量res存储最小生成树中所有边权重之和。每一次遍历我们从还没有拓展到的点中选择一个距离已经拓展到的点最近的点如果我们找到的这个点距离还没拓展到的点的距离是正无穷说明这个图是不连通的也就不存在最小生成树如果不是正无穷那就继续进行下一步操作。我们将这个点变成已经拓展到的点并去更新所有还没拓展到的点到已经拓展到的点的距离。循环n次即可得到最小生成树。
可能会觉得与Dijkstra算法非常像但是是有区别的。 1Dijkstra算法在最先开始时已经确定了dist[1] 0所以只需要循环n - 1次而Prim算法最先开始是所有都初始化为正无穷所以要循环n次 2在每次循环中Dijkstra算法找的点是还没确定最短距离的点中距离起点最近的点而Prim算法中找的点是还没拓展到的点中距离已经拓展到的点最近的点 3Dijkstra算法在更新距离时是更新选中的点的邻点的距离而Prim算法是更新所有还没拓展到的点到已经拓展到的点的距离
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 510, INF 0x3f3f3f3f;int n, m;
int g[N][N];
int dist[N]; // 存储还没拓展到的点到已经拓展到的点的最短距离
bool st[N]; // st表示一个点是否被拓展到了false表示没有int prim()
{// dist初始化为正无穷因为都还没拓展到memset(dist, 0x3f, sizeof(dist));int res 0; // res存储最小生成树中边的权重之和for (int i 0; i n; i ) // 最小生成树有n个点所以迭代n次{int t -1; // t是还没拓展到的点中距离已经拓展到的点最近的点for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;// 如果还没拓展到的点中距离已经拓展到的点最近的点到已经拓展到的点的距离为正无穷说明不连通if (i dist[t] INF) return INF; if (i) res dist[t]; // 因为加入第一个点时并没有边所以i 0时不需要res dist[t]st[t] true;// 更新还没拓展到的点到已经拓展到的点的距离for (int j 1; j n; j ) dist[j] min(dist[j], g[t][j]);}return res;
}int main()
{scanf(%d%d, n, m);memset(g, 0x3f, sizeof(g));while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);g[a][b] g[b][a] min(g[a][b], c);}int t prim();if (t INF) puts(impossible);else printf(%d\n, t);return 0;
}
注意代码实现中一定要先更新res再更新其他点到集合的距离因为若当前这个点存在自环且为负权可能会先更新时将自己更新了而最小生成树中不应该有自环。当然也可以直接将自环都不加入图这样res更新与更新其他点到集合的距离的顺序就无所谓了
堆优化的思路与Dijkstra算法是类似的。用一个堆来存放dist数组
7.3 Kruskal算法
859. Kruskal算法求最小生成树 - AcWing题库
Kruskal算法也称为加边法。步骤一开始假设有所有的点但是一条边没有我们从小到大去遍历这些边若这条边的两个端点不在同一个连通分量中则这条边是最小生成树的边若这条边的两个端点在同一个连通分量中则去遍历吓一跳边直到有了n - 1条边这样所有点都在一个连通分量中了最小生成树也就完成了。
我们还是以这个图为例 会看到最小的边是1并且0和2并不在一个连通分量中所以这条边可以连接 现在最小的边是2并且3和5不在一个连通分量中所以这条边可以连接 现在最小的边是3并且1和4不在一个连通分量中所以这条边可以连接 现在最小的边是4有两条假设我们先遍历到2和3之间那一条此时2和3不在一个连通分量中所以这条边可以连接 现在最小的边还是4但是2和5在一个连通分量中所以直接看下一条边 吓一跳边是5只有1和2是不在一个连通分量中的
我们来看是如何使用代码来实现这个过程的。Kruskal算法不需要使用邻接表或邻接矩阵来存储图只需要存所有边即可所以直接用一个结构体数组并且这个结构体还需要operator方便根据边的权重进行排序。因为在加入边时要判断边的两个端点是否连通所以需要使用并查集。首先将结构体数组根据边的权重进行排序res存储最小生成树中边的权重之和cnt存储当前最小生成树中有几条边然后从小到大遍历所有的边若这条边的两个端点不在一个连通分量中我们就将两个端点所在的两个连通分量连接cnt。循环结束后若cnt n - 1就说明已经求出了最小生成树若不等于说明这个图不连通不存在最小生成树
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M 200010, INF 0x3f3f3f3f;int n, m;
int p[N];struct Edge
{int a, b, w;bool operator (const Edge W)const // 重载小于号方便根据权重排序{return w W.w;}
}edges[M]; // 使用结构体数组来存储图int find(int x) // 并查集
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges m); // 根据边的权重进行排序for (int i 1; i n; i ) p[i] i; // 初始化并查集// res存储最小生成树中边的权重之和cnt存储当前最小生成树中有几条边int res 0, cnt 0;for (int i 0; i m; i ) // 根据边的权重从小到大遍历所有边{int a edges[i].a, b edges[i].b, w edges[i].w;a find(a), b find(b);if (a ! b) // 若a和b不在一个集合中{p[a] b;res w;cnt ;}}if (cnt n - 1) return INF; // 循环结束最小生成树中还没有n - 1条边说明这个图不连通return res;
}int main()
{scanf(%d%d, n, m);for (int i 0; i m; i ){int a, b, w;scanf(%d%d%d, a, b, w);edges[i] {a, b, w};}int t kruskal();if (t INF) puts(impossible);else printf(%d\n, t);return 0;
}
8、二分图
8.1 概念
二分图如果无向图的n个结点可以分成AB两个不相交的非空集合并且同一集合内的点没有边相连那么就称该无向图为二分图。 像这两个图左边的是二分图右边的不是二分图。左边的图可将1、4两点放入一个集合2、3、5放入另一个集合此时每一个集合内的点都没有边相连所以是二分图。右边的图无论如何划分都无法将4个点分成两个集合并保证每一个集合内的点都没有边相连所以不是二分图。
8.2 染色法
860. 染色法判定二分图 - AcWing题库
染色法是用来判断一个图是否是二分图的一个算法。 在二分图中有一个定理二分图不存在奇环。 我们要判断一个图是否是二分图运用的就是这个定理。染色法就是尝试使用两种颜色来标记图中的结点当一个结点被标记后所有与它相邻的结点应该标记为与它相反的颜色若标记过程中产生冲突(也就是相邻的两个点颜色是一样的)就说明图中存在奇环这个图不是二分图。可以用DFS或BFS实现。 可以看到第2幅图1和3是邻点但是被染的颜色却是相同的说明不是二分图
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M 200010;int n, m;
int h[N], e[M], ne[M], idx;
int color[N]; // 存储每个点的颜色0表示没染色1和2分别代表一种颜色void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}bool dfs(int u, int c)
{color[u] c; // 将u号点染成c这种颜色for (int i h[u]; i ! -1; i ne[i]) // 遍历u号点的所有邻点{int j e[i];if (!color[j]) // 若这个邻点没有染色则向下进行深搜{if (!dfs(j, 3 - c)) return false; // 3 - c将1变成2将2变成1因为邻点染的颜色要与当前点不同}else if (color[j] c) return false; // 若这个邻点的颜色与u相同说明出现矛盾了}return true;
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof(h));while (m -- ){int a, b;scanf(%d%d, a, b);add(a, b), add(b, a);}bool flag true; // flag记录是否有染色失败for (int i 1; i n; i ) // 对图中所有的点都进行一次深搜if (!color[i]) // 若这个点还没有染色则以这个点为起点进行深搜{if (!dfs(i, 1)){flag false;break;}}if (flag) puts(Yes);else puts(No);return 0;
}
8.2 匈牙利算法
861. 二分图的最大匹配 - AcWing题库
匈牙利算法是解决二分图最大匹配问题的一种算法。 二分图的最大匹配设G为二分图若在G的子图M中任意两条边都没有公共节点那么称M为二分图G的一组匹配。在二分图中包含边数最多的一组匹配称为二分图的最大匹配。
假设我们要计算下面这个图的最大匹配现在使用匈牙利算法来完成 首先我们看1号点是否有匹配的点发现有6和8并且6和8都没有被匹配过所以随便匹配一个这里选择匹配6 看2号点与其匹配的点有5号点和7号点并且5号点和7号点都没有被匹配这里我们选择5号点 看3号点会发现3号点有且仅有一个匹配的点6号点并且这个匹配的点已经被匹配过了这个时候我们就要去看与6号点匹配的点1号点是否还有其他选择会发现1号点还可以选择8所以我们让1号点匹配8号点3号点匹配6号点 看4号点发现其与7号点匹配并且7号点并没有被匹配过所以我们连接4号点和7号点
所以匈牙利算法就是每次匹配时若匹配的点已经被匹配过了就去看与匹配的点匹配的点是否有其他选择一直递归直到找到或没有其他选择。
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 510, M 100010;int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true;if (match[j] 0 || find(match[j])){match[j] x;return true;}}}return false;
}int main()
{scanf(%d%d%d, n1, n2, m);memset(h, -1, sizeof(h));while (m -- ){int a, b;scanf(%d%d, a, b);add(a, b); // 虽然是无向图但是我们加入a - b即可}int res 0; // 存匹配的数量for (int i 1; i n1; i ){memset(st, false, sizeof(st));if (find(i)) res ;}printf(%d\n, res);return 0;
}
