南京医院手机网站建设,wordpress主页布局,专业开发小程序公司,网页和网站的关系文章目录 图的概念图的概念图的分类有向图和无向图 连通性连通块重边和自环稠密图和稀疏图参考资料 图的存储方式邻接表代码 邻接矩阵 DFS全排列问题题目描述思路回溯标记剪枝代码时间复杂度 [N 皇后问题](https://www.luogu.com.cn/problem/P1219)题目描述全排列思路 O ( n ! … 文章目录 图的概念图的概念图的分类有向图和无向图 连通性连通块重边和自环稠密图和稀疏图参考资料 图的存储方式邻接表代码 邻接矩阵 DFS全排列问题题目描述思路回溯标记剪枝代码时间复杂度 [N 皇后问题](https://www.luogu.com.cn/problem/P1219)题目描述全排列思路 O ( n ! ) O(n!) O(n!)代码 枚举思路 O ( n ! ) O(n!) O(n!)代码 树的重心**题目描述**思路 O ( n ) O(n) O(n)代码参考资料 相关题目 BFS二叉树的层序遍历思路 O ( n ) O(n) O(n)代码参考资料 走迷宫思路 O ( n m ) O(nm) O(nm)代码 相关题目 有向无环图的拓扑序列有向无环图拓扑序列BFS 思路 O ( n m ) O(nm) O(nm)代码 参考资料相关题目 最短路径问题单源最短路径问题朴素 Dijkstra 算法 O ( n 2 m ) O(n^2m) O(n2m)代码 堆优化 Dijkstra 算法 O ( ( n m ) l o g n ) O((nm)logn) O((nm)logn)代码补充参考资料 Bellman-Ford 算法 O ( n m ) O(nm) O(nm)代码参考资料 SPFA O ( k m ) / O ( n m ) O(km)/O(nm) O(km)/O(nm)代码参考资料 相关题目 最小生成树朴素 Prim 算法 O ( n 2 m ) O(n^2 m) O(n2m)代码 堆优化 Prim 算法 O ( ( n m ) l o g n ) O((nm)logn) O((nm)logn)代码参考资料 Kruskal 算法 O ( m l o g m ) O(mlogm) O(mlogm)代码参考资料 相关题目 二分图染色法判定二分图 O ( n m ) O(nm) O(nm)代码补充参考资料 二分图最大匹配匈牙利算法 O ( n m ) O(nm) O(nm)代码参考资料 相关题目 阅读前导
本文默认读者有数据结构和图论基础本文是对图论的几个代表性算法的入门虽然题目的解法比较朴素但是比较好理解。
图的概念
首先简单复习一下离散数学中图论的相关概念。
图的概念
图是由顶点和边组成顶点一般表示对象边一般表示对象之间的关系。
在图论中多个顶点或边组成的集合叫做顶点集Vertices Set或边集Edges Set。例如图 G 可以写成 G (V, E)其中 V 是图 G 的顶点集E 是图 G 的边集。
树是一种特殊的图。
图的分类
有向图和无向图
根据边是否有方向可以将图分为有向图和无向图。
无向图 有向图 通常情况下只对有向图进行讨论因为无向图的每一条无向边相当于两条方向相反的有向边组成的。
连通性
无向图的连通性如果无向图中任意两个顶点之间都有一条无向路径则称该图为连通图。有向图的连通性如果有向图中任意两个顶点之间都有一条有向路径则称该图为强连通图。 如果将有向图的所有边替换成无向边后得到一个连通图则称该有向图为弱连通图。
连通块
连通块是指无向图中的一个子图它满足以下两个条件
子图中的任意两个顶点都能通过路径相连即可以沿着图中的边互相可达。子图中的所有顶点都不和原图中的其他顶点连通即子图是原图的一个独立部分。
当左边灰色区域中最右边的节点被移除时这个图就变得不连通了 当虚线边被移除时这个图就会不连通 有顶点 0这个图就是非连通的。该图的其余部分是连通的 重边和自环
重边是两条或多条与同一对顶点相连接的边。例如 自环是一条顶点与自身连接的边。例如顶点 1 稠密图和稀疏图
若一张图的边数远小于其点数的平方那么它是一张稀疏图 (sparse graph)。
若一张图的边数接近其点数的平方那么它是一张稠密图 (dense graph)。
区分稠密图和稀疏图的主要依据是看题目给的数据是否呈以上两种关系之一这么做的原因是算法在稠密图和稀疏图中的效率不同。
参考资料
图的概念与存储方式|哔哩哔哩
图的存储方式
在计算机中图的存储就是用数据结构来表示图的顶点集和边集的方法。根据图的稀疏或稠密主要分为邻接表或邻接矩阵。
邻接表
用一个一维数组和一个链表来存储图中顶点和边的信息一维数组中的每个元素对应一个顶点每个元素指向一个链表链表中存储与该顶点相邻的顶点或者边的权重很像哈希桶。邻接表适合表示稀疏图即边数较少的图空间复杂度为 O ( N E ) O (NE) O(NE)其中 N N N为顶点数 E E E为边数。
可以用 链式前向星 来存储邻接表。
无向图链表记录的是顶点的邻居结点 有向图链表记录的是顶点的出度 由于我们解决的问题主要是关于“路径长度”的问题枚举每一条边就是枚举每个顶点的出边。因此研究的单位应该是边一条边需要两个点和一个边长来表示分别用三个数组来存储
head[]存储每个顶点ver[]head[i] 这个点指向的终点edge[]head[i] 点指向 ver[i] 这条边的长度
除此之外邻接表本身是一个链表而链表的实现有几种在算法题目中通常用占用内存较小的数组模拟逻辑上的链表。
next[]记录边集数组的下标
以上面这个有向图为例四个数组的关系是这样的 在分析时应该注意每个数组的含义例如从 head[i] 这个顶点出发到 ver[i] 这个边边长为 edge[i]下一个结点的位置是 next[i]。
代码
const N 100010, M N * 2; // 无向图需要两条有向边
int head[N], ver[M], edge[M], Next[M], idx;// 插入一条从 x 到 y 长度为 z 的有向边
void add(int x, int y, int z)
{idx;ver[idx] y;edge[idx] z;// 头插Next[idx] head[x];head[x] idx;
}// 读入一条有向边
add(x, y, z);// 读入一条无向边一对有向边一条无向边
add(x, y, z);
add(y, x, z);// 枚举从 x 顶点出发的所有边
for (int i head[x]; i ! 0; i Next[i])
{// 能提供循环条件则说明还有边int y ver[i];int z edge[i];// 后续操作
}// 清零只需要处理链表和计数器
memset(head, 0, sizeof(head));
idx 0;邻接矩阵
用一个二维数组来存储图中顶点之间的关系数组的行和列分别对应图中的顶点数组的元素表示两个顶点之间是否有边或者边的权重。邻接矩阵适合表示稠密图即边数较多的图但是空间复杂度较高为 O ( N 2 ) O (N^2) O(N2) 其中 N N N为顶点数。 在这个矩阵中不论是有向图还是无向图顶点到它本身的距离为 0。如果两个顶点不是直接连通的那么规定距离为无穷 ∞ ∞ ∞。
无向图矩阵记录每个顶点到它邻居结点的距离关于对角线对称。
有向图矩阵记录每个顶点的出度结点的距离。
二维矩阵的存储只需要用一个二维数组a[i][j]表示从 i 指向 j 的一条边这个二维下标对应的数组元素则为边的权重。
DFS
深度优先搜索Depth-first search DFS是一种图算法它的基本思想是从一个顶点开始沿着一条路径不断向前探索直到不能再继续为止然后回溯到上一个顶点再从另一条路径继续探索直到遍历完所有的顶点和边。
DFS 中的“深度”体现在它的搜索策略上即优先选择未访问过的相邻顶点进行探索形成一条尽可能长的路径所谓“一条路走到黑不撞南墙不回头”。DFS 的思想天然地与递归契合每次递归调用相当于向深处探索一层每次返回相当于回溯一层。 对于 DFS最重要的是“顺序”即用何种顺序把所有情况遍历一次。由于 DFS 的特点每一个 DFS 路径都对应着一颗搜索树什么意思呢就是说 DFS 在走到不能走的时候就说明此时已经找到了一个结果具体这个结果正确与否取决于问题对这个结果的限制。
全排列问题
题目描述
按照字典序输出自然数 1 1 1 到 n n n 所有不重复的排列即 n n n 的全排列要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 n n n。
输出格式
由 1 ∼ n 1 \sim n 1∼n 组成的所有不重复的数字序列每行一个序列。
每个数字保留 5 5 5 个场宽。
样例输入
3样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1提示 1 ≤ n ≤ 9 1 \leq n \leq 9 1≤n≤9。
思路
如果只问你 1/2/3 这三个数字最多能有多少种排列方式相信你会很快得到答案3*2*16这个算法的本质是枚举每一个位置上能够取哪些数字。例如个位数能取到 1/2/3那么十位数只能取到其中两个数字百位数只能取一个数字。
这和朴素的递归思想是类似的因为递归执行的是同一种操作只是它的规模在不断缩小当规模缩小到不能再小时就“撞到南墙”了也就得到一个结果了。
首先用一个递归树来演示 DFS 的过程
初始状态是三个空位置第一位有 3 种填法第二位有 2 种填法因为不能和第一位相同第三位只有一种填法。
视角在每一层中递归应该看的是下一层还能填什么数字如果没得填了就说明走到最后了。
回溯
当得到一个结果时相当于这条分支已经被使用过了但是从这递归树来看它的父结点的另一个孩子可能还未使用即当前结点的兄弟结点所以要回溯到上一层以还原“现场”。
因为要回溯所以我们需要用栈来保存当前结点的父结点在递归树中的位置不过递归天然地使用了系统中函数栈帧所以递归调用的返回就是一次回溯。
标记
为了保证能够一次性枚举图中的所有元素当得到结果的同时为这个叶子结点打上标记。这应该在回溯之前完成。
剪枝
在 DFS 中不一定所有结果都是符合题目要求的例如在递归的过程中第二个数字和第一个数字相同那么此时就可以直接返回此路径作废以此提高效率这就是剪枝。
代码
数据结构
path[]存储递归树中从根结点到叶子结点的路径也就是保存一个结果以供打印。如果只问结果的个数可以不需要它visited[]存储 path 这条路径中已经访问过的结点。
注意visited[i] 这个标记当回溯时也要被还原因为回溯的前提是上一次递归返回了。结合递归树理解为什么要标记呢因为递归的下一层仍然是一个类似的递归树。递归从 x 结点进入下一层时x 结点对于本次递归就算是访问过了当跳出此次递归后还得访问另一边的子树所以恢复 x 结点的状态以通过进入递归的判断条件。
递归终止条件当计数器和数字的长度相等时即得结果打印路径。
#include iostream
using namespace std;const int N 100010;
int path[N];
bool visited[N];
int n;void dfs(int x)
{// 当填满时打印if (x n){for (int i 0; i n; i) printf( %d, path[i]);printf(\n);return;}for (int i 1; i n; i){// 如果这个结点还没有被访问过if (visited[i] ! true){path[x] i; // 记录到路径中visited[i] true; // 标记它被使用过dfs(x 1); // 递归下一层visited[i] false; // 递归返回后才能走到这一步回溯还原现场}}
}int main()
{while (cin n){dfs(0); // 注意从第 0 个元素开始}return 0;
}递归必须从第 0 个格子开始其次是这个例子的剪枝体现的不明显在下面的例子中会有比较深刻的体会。
时间复杂度
这个 DFS 的思路的时间复杂度是 O ( n ! ) O(n!) O(n!)因为它要枚举每一行的每一列然后检查是否满足条件。如果满足条件就继续递归下一行。如果不满足条件就回溯到上一行。这样的过程相当于在 n n n 个数中选出 n n n 个数的全排列。
N 皇后问题
题目描述
一个如下的 6 × 6 6 \times 6 6×6 的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线包括两条主对角线的所有平行线上至多有一个棋子。 上面的布局可以用序列 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5 来描述第 i i i 个数字表示在第 i i i 行的相应位置有一个棋子如下
行号 1 2 3 4 5 6 1\ 2\ 3\ 4\ 5\ 6 1 2 3 4 5 6
列号 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出解按字典顺序排列。 请输出前 3 3 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n n n表示棋盘是 n × n n \times n n×n 大小的。
输出格式
前三行为前三个解每个解的两个数字之间用一个空格隔开。第四行只有一个数字表示解的总数。
样例
样例输入
6样例输出
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4对于 100 % 100\% 100% 的数据 6 ≤ n ≤ 13 6 \le n \le 13 6≤n≤13。
全排列思路 O ( n ! ) O(n!) O(n!)
八皇后在每行每列还有两条对角线中只允许一个皇后棋子存在那么我们可以枚举每一列皇后的位置只要满足条件就可以进入递归。
增加的逻辑是八皇后不仅限制同行同列还限制两条对角线。由于枚举的是每行的情况那么就用一个数组col[]记录列格子的状态用dg[[]和antidg[]来保存对角线Diagonal和反对角线Antidiagonal格子的状态。
代码
#include iostream
#include vector
#include algorithm
using namespace std;const int N 20;
int n;
bool col[N], dg[N], antidg[N];
int path[N];
vectorvectorint ans; // 用一个二维数组来保存所有的解// 枚举每一行x 表示一列中第 x 格
void dfs(int x)
{if (x n) {ans.push_back(vectorint(path, path n)); // 把当前解放入数组中return;}// 枚举 x 格所在行的这一列for (int i 0; i n; i){// 如果 x 格在它所在列/对角线/反对角线都没有被访问过if (col[i] ! true dg[x i] ! true antidg[n - x i] ! true){path[x] i; // 记录到路径中col[i] dg[x i] antidg[n - x i] true; // 标记dfs(x 1); // 进入递归col[i] dg[x i] antidg[n - x i] false; // 回溯 }}
}int main()
{cin n;dfs(0);sort(ans.begin(), ans.end()); // 对所有的解进行排序for (int i 0; i min(3, (int)ans.size()); i) // 输出前三个解或者所有的解如果小于三个{for (int j 0; j n; j){printf(%d , ans[i][j] 1);}cout endl;}cout ans.size() endl;return 0;
}枚举思路 O ( n ! ) O(n!) O(n!)
上面的思路是枚举每一行中的每个列的格子下面的思路是直接枚举每一个格子是比较朴素的思路。
对于每一个格子有两种选择选或不选。那么每一个格子都会分为两个分支形成一棵递归树。
对于每个格子
不放皇后直接递归到下一个格子放皇后 这个格子所在的行和列以及两个对角线不能有皇后存在更新状态记录此行此列和两个对角线上已经有皇后了递归到下一个格子跳出递归回溯恢复现场
注意在枚举每个格子时需要注意数组越界的问题也就是当每一行走完后就必须让它走到下一行的第一个位置了。
终止条件这个朴素的思路是枚举每个格子那么终止条件就是当找到所有符合条件的皇后时即得到一个结果。
代码
#include iostream
#include vector
#include algorithm
#include cstring
using namespace std;const int N 20;
int n;
bool row[N], col[N], dg[N], antidg[N];
int path[N][N];
vectorvectorint ans;// 将当前放置的皇后位置保存到结果中
void saveResult()
{vectorint queenPos;for (int i 0; i n; i){for (int j 0; j n; j){if (path[i][j] 1){queenPos.push_back(j);break;}}}ans.push_back(queenPos);
}// 枚举每一个格子坐标是 (x, y), count 表示已经放下的皇后数量
void dfs(int x, int y, int count)
{if (y n){ // 当此行走到最后一个格子y 0; // 让 y 回到最左x; // 让 x 走到下一行}if (x n){ // 当走到最后一行if (count n) // 所有皇后都被放下saveResult(); // 将结果保存到 ans 中return;}// 不放皇后dfs(x, y 1, count);// 放皇后if (row[x] ! true col[y] ! true dg[x y] ! true antidg[x - y n] ! true){path[x][y] 1; // 记录到路径中row[x] col[y] dg[x y] antidg[x - y n] true; // 标记dfs(x, y 1, count 1); // 进入递归path[x][y] 0; // 回溯撤销放置的皇后row[x] col[y] dg[x y] antidg[x - y n] false; // 回溯撤销标记}
}int main()
{cin n;memset(path, 0, sizeof(path));dfs(0, 0, 0);sort(ans.begin(), ans.end()); for (int i 0; i min(3, (int)ans.size()); i) {for (int j 0; j n; j){printf(%d , ans[i][j] 1);}cout endl;}cout ans.size() endl;return 0;
}[注] 这段代码是最原始的版本是比较好理解的但是在处理大规模数据时OJ可能会超时这是因为代码中存在一些不必要的操作。例如在每次递归调用时都会检查所有的行和列这实际上是不必要的因为已经知道这一格在哪一行和哪一列。
此外在保存结果时遍历了整个棋盘来找到皇后的位置这也增加了额外的计算量。实际上可以在放置皇后时就记录下皇后的位置这样在保存结果时就不需要再次遍历棋盘。
下面是优化后的版本
const int N 20;
int n;
bool col[N], dg[2 * N], udg[2 * N];
int path[N];
vectorvectorint ans;// 将当前放置的皇后位置保存到结果中
void saveResult()
{vectorint queenPos(path, path n);ans.push_back(queenPos);
}// 枚举每一个格子坐标是 (x, y), count 表示已经放下的皇后数量
void dfs(int x)
{if (x n){saveResult(); // 将结果保存到 ans 中return;}for (int y 0; y n; y){if (!col[y] !dg[x y] !udg[x - y n]){path[x] y;col[y] dg[x y] udg[x - y n] true;dfs(x 1);col[y] dg[x y] udg[x - y n] false;}}
}在最坏的情况下需要尝试所有的放置方式所以这两段代码的时间复杂度是 O ( n ! ) O(n!) O(n!)。但是枚举思路在平均效率上还是比全排列思路低的。
树的重心
题目描述
给定一颗树树中有 n n n 个节点编号 1 ∼ n 1∼n 1∼n 。 请你找到树的重心并输出树的重心的节点编号。
重心定义重心是指树中的一个节点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。
如下图所示的树的重心为 1 号节点。 输入
第 1 行读入一个整数 n代表树的节点的数量 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105
接下来 n − 1 n−1 n−1 行每行读入两个整数 x x x 和 y y y 表示节点 x x x 和 y y y 之间有一条边注意不确定 x x x 和 y y y 的父子关系。
输出
请输出树的重心的节点编号如果树有多个重心请按照编号从小到大依次输出数字之间用空格隔开。
输入样例
9
1 2
1 7
2 8
2 5
4 3
1 4
3 9
4 6输出样例
1思路 O ( n ) O(n) O(n)
为了找到树的重心centroid我们需要知道每个节点的子树大小即以该节点为根的子树包含的节点数。这个值可以通过一次DFS 来求出。
枚举每个节点记录下如果删除这个节点后剩余连通块的点数最大值 如何求某个连通块的点数––通过对某个子树的根节点做 DFS 在这些最大值中找到最小值然后根据最小值找到对应的节点
举个例子 现在问题来了这样需要对每个结点都要做一次 DFS那么时间复杂度是 O ( n 2 ) O(n^2) O(n2)的为了简化需要使用到下面的结论。
通过图示中连通块数量之间的关系我们可以总结出以下规律树中的连通块也是树
某一子树的节点数量 subNum[i]等于它的子树节点数量之和。某一子树的节点数量 subNum[i]等于整棵树的节点数减去除了这棵子树外的其他所有节点之和。这是因为树是一个连通无环的图所以任意两个节点之间有且仅有一条路径因此每个节点都只属于一个子树。
下面对这两点举个例子 利用这样的结论我们只需要 DFS 一次就能找到所有节点的子树大小就这个例子而言DFS 得到结果的刚开始顺序是自上而下的然后再向上返回递归
向下的过程我们是可以理解的就是通过递归来统计某一棵子树的大小但是当向上递归时DFS 目前只求出了下边的子树大小那么就通过上面的结论来求出向上递归过程时的子树大小。这样就不用再对上面的节点再各来一次 DFS 了。
每个子树的点数将被存储在 subNum[] 数组中以便复用入口可以是任意的。可以从任意一个节点开始是因为树是一个连通无环的图所以每个节点都可以作为根节点不影响树的结构。无论从哪个节点开始都可以遍历到树的所有节点计算出每个节点的子树大小。只是从不同的节点开始可能会导致不同的遍历顺序但是最终的结果是一样的。
代码
总之要找到树的重心首先要知道每个子树的大小为了减少时间复杂度那么就要用到「不论树的连通块的数目或大小如何变化整体节点数不变」这个结论这样就能在 DFS 递归的同时计算出所有子树的大小。 #include iostream
#include cstring
#include algorithm
#include vector
using namespace std;const int N 100010, M N * 2;int n;
int head[N], ver[M], Next[M], idx;
bool visited[N];int centroidVal N; // 重心的值
int subNum[N]; // 保存每个节点最大子树的个数
vectorint centroids; // 用一个向量来存储所有的重心
void add(int x, int y)
{idx;ver[idx] y;Next[idx] head[x];head[x] idx;
}int dfs(int x)
{visited[x] true; // 标记 x 点已经被访问过// sum 用来保存 x 子树的大小默认包含它本身, subMax 用来保存当删除节点 x 后剩下较大的孩子子树的大小int sum 1, subMax 0; for (int i head[x]; i ! -1; i Next[i]) // 遍历 x 的孩子{int j ver[i], subNum;if (visited[j] ! true) // 如果当前节点没有被访问过{ subNum dfs(j); // 对它进行 DFS, 并且取出这棵子树的大小subMax max(subMax, subNum); // 当删除当前节点 x 后保存较大的那个孩子子树的大小sum subNum; // 更新 x 的孩子数量}}// 每个节点只会执行一次subMax max(subMax, n - sum); // 求出当删除节点 x 后剩下最大连通块的大小centroidVal min(centroidVal, subMax); // 重心的值更新为{每个节点的最大连通块的大小}这个集合中的最小值subNum[x] subMax; // 记录 x 的最大子树大小return sum; // 返回 x 的父节点告诉它 x 这棵子树的大小
}int main()
{cin n;memset(head, -1, sizeof(head));memset(visited, false, sizeof(visited));for (int i 0; i n - 1; i){int a 0, b 0;cin a b;add(a, b);add(b, a);}if (n 1) // 处理 n 为 1 的特殊情况{// cout 1 endl;cout 1 endl;return 0;}dfs(1); // 入口可以任意// cout centroidVal endl; // 输出重心的值for (int i 1; i n; i){if (subNum[i] centroidVal) // 如果 i 的最大子树大小等于重心的值{centroids.push_back(i); // 将 i 加入到重心的向量中}}for (int i 0; i centroids.size(); i) // 输出所有的重心{cout centroids[i] endl;}return 0;
}注意
需要考虑到树的重心可能有两个的情况用一个数组或向量来存储所有的重心然后在最后输出它们。处理树的大小为 1 的特殊情况这时候重心的值应该为 1可以在 dfs 之前判断一下 n 是否为 1如果是的话直接输出 1 即可。
这个思路的时间复杂度是 O ( n ) O(n) O(n)其中 n n n 是树的节点数。在遍历的过程中每个节点只会被访问一次每条边也只会被访问两次一次正向一次反向。
[补充]
关于树的重心的一些结论
如果以某个节点为整棵树n 个节点的重心它的每棵子树的大小都小于等于 n/2。重心到其他节点的距离和最小如果有两个重心那么距离和相同。一棵树添加或删除一个节点树的重心最多只移动一条边的位置。把两棵树通过某个点相连那么新树的重心必定存在于这条相连的路径上。
参考资料
树的重心|哔哩哔哩DFS 求树的重心|哔哩哔哩算法学习笔记 (72): 树的重心|知乎树的重心|AcWing
相关题目
LuoguP1157 组合的输出「JY/DFS - Part I」|Luogu 题单DFS 题单|LeetCodeDFS–基本入门模板 和 例题 |CSDN【DFS 入门题小集】深度优先搜索-DFS|OJ
BFS
广度优先搜索Breadth-First SearchBFS和 DFS 一样也是一种图搜索算法。它的思想是从一个顶点开始访问它的所有相邻顶点然后再依次访问这些相邻顶点的相邻顶点直到访问完所有的顶点。
BFS 可以用来寻找图中的最短路径、连通分量、拓扑排序等问题。它使用一个队列来存储待访问的顶点每次从队列中取出一个顶点访问它并将它的未访问过的相邻顶点入队直到队列为空。
这和 DFS 不同DFS 使用的是系统维护的函数栈帧通过递归建立而 BFS 需要自己维护一个队列。 对于一棵二叉树而言BFS 就是层序遍历下一次搜索的范围就是在原有的基础上扩大一个单位的长度。
二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[]思路 O ( n ) O(n) O(n)
由于 BFS 每次只会对与当前节点距离为 1 的节点进行扩展所以 BFS 遍历树的结果也就是树的层序遍历。 但是需要注意的是BFS 的队列中在某一刻得到的序列并不一定都在同一层假如第二层的最后一个节点 X 还没有出队列下一层的节点就已经进队列了所以原生的 BFS 会有「元素分层」的现象。 树的层序遍历使得我们需要增加一些限制使得队列中如果有元素那么它们在树中一定是同一层的。办法是在遍历当前层的元素时先把这一层元素的数量即队列大小保存下来因为 BFS 每访问一个元素时都会将它出队列那么队列的大小是在不断变化的。
代码
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint res;if (root nullptr) return res;queueTreeNode* q;q.push(root);while (!q.empty()){vectorint curLevel; // 记录当前层的元素值int n q.size(); // 注意队列的大小必须在操作它之前保存才能完整地遍历下一层的所有结点for (int i 0; i n; i){TreeNode* node q.front();q.pop();curLevel.push_back(node-val);if (node-left) q.push(node-left);if (node-right) q.push(node-right);}res.push_back(curLevel);}return res;}
};这个思路的时间复杂度是 O ( n ) O(n) O(n)其中 n n n是树节点的个数。
参考资料
以上图片源自此题的题解BFS 的使用场景总结层序遍历、最短路径问题
BFS 的入门同时也是此题解的视频解析【111 广搜 宽搜 (BFS) 算法】
走迷宫
给定一个 n ∗ m n*m n∗m的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。
最初有一个人位于左上角 (1, 1) 处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问该人从左上角移动至右下角 (n, m) 处至少需要移动多少次。
数据保证 (1, 1) 处和 (n, m) 处的数字为 0且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行每行包含 m 个整数0 或 1表示完整的二维数组迷宫。
输出格式
输出一个整数表示从左上角移动至右下角的最少移动次数。
数据范围 1 ≤ n , m ≤ 100 1≤n,m≤100 1≤n,m≤100
样例 输入样例
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0输出样例
8思路 O ( n m ) O(nm) O(nm)
初始化队列们需要一个队列来存储待处理的节点将起始点放入队列中。处理队列中的节点处理队列中的节点。对于队列中的每一个节点都要检查它的四个方向左、上、右、下。如果某个方向上的节点是可达的即值为 1并且没有被访问过那么就将其加入到队列中并标记该节点为已访问。记录路径为了能够找到从起始点到终点的路径需要在每个节点中记录从起始点到当前节点的路径。使用一个二维数组 path 来存储路径信息其中 path[i][j] 表示从起始点到点 (i, j) 的路径。找到终点当从队列中取出终点时就表示已经找到了一条从起始点到终点的路径可以直接从 path 数组中获取并输出这条路径。处理所有路径由于题目要求输出所有可能的路径所以不能在找到第一条路径后就停止搜索。而是需要继续处理队列中的其他节点直到队列为空。无法到达终点如果队列为空但此时还没有找到终点说明从起始点无法到达终点输出 -1。
下面是得到这个样例输出的过程图中省略了部分扩展方向例如只有左和下实际上需要有四个方向荧光绿表示它是未被使用并且可以走的但是此次查找不走它 在搜索的过程中要用队列维护元素的状态
入队表示排队等待扩展出队扩展出队元素的邻居结点
数据结构
用一个队列保存将要扩展的结点这个结点应该是由上一个结点扩展决定的默认是起点用数组gra[][]来读取地图用数组dis[x][y]来表示 (x, y) 这个点距离原点的距离
通过对 (x, y) 坐标的加减操作实现对这个点周围的四个点的访问可以用两个数组分别保存对 x 和 y 坐标的变换距离x[4] {-1, 0, 1, 0} 和 y[4] {0, 1, 0, -1}注意它们是组合使用的例如要访问 (x, y) 点的左边那个点那么就需要这么做matrix[i x[2] ][j y[2] ] matrix[i 1][y 0]。
如果要输出路径可以用Prev[][]来保存路径小写的 prev 可能会和头文件中的变量冲突它保存的是当前节点的上一个节点。
代码
#include iostream
#include cstring
#include queueusing namespace std;const int N 110;queuepairint, int q;
int n, m;
int gra[N][N];
int dis[N][N]; // 记录某点到原点的距离
pairint, int Prev[N][N]; // 记录当前元素的上一个结点void printPath()
{int x n - 1;int y m - 1;while (x ! 0 || y ! 0){printf (%d %d\n, x, y);auto t Prev[x][y];x t.first;y t.second;}
}int bfs()
{int dx[4] {-1, 0, 1, 0};int dy[4] {0, 1, 0, -1};memset(dis, -1, sizeof(dis));dis[0][0] 0; // 初始化距离q.push({0, 0}); // 将起点入队while (!q.empty()){auto t q.front(); // 取出队头元素 tq.pop(); // 出队for (int i 0; i 4; i) // 访问 t 的 4 个邻居{int x t.first dx[i], y t.second dy[i];// 如果坐标合法且不是墙并且没有被访问过则入队if ((x 0 x n y 0 y m) gra[x][y] 0 dis[x][y] -1){// path[x][y] t; // 记录路径dis[x][y] dis[t.first][t.second] 1;Prev[x][y] t; // 记录上一个合法的元素q.push({x, y});}}}// 打印printPath();return dis[n - 1][m - 1];
}int main()
{cin n m;for (int i 0; i n; i)for (int j 0; j m; j)scanf(%d, gra[i][j]);cout bfs() endl;return 0;
}空间复杂度这段代码需要存储迷宫本身距离数组前驱数组和队列。迷宫本身距离数组和前驱数组都占用 O ( n m ) O(nm) O(nm) 的空间队列的最大长度为 O ( n m ) O(nm) O(nm)最坏情况下所有的点都入队一次。时间复杂度为 O ( n m ) O(nm) O(nm)这段代码需要遍历迷宫中的所有点每个点最多被访问一次每次访问需要 O ( 1 ) O(1) O(1) 的时间。另外每个点最多有四个邻居每次访问邻居需要 O ( 1 ) O(1) O(1) 的时间。
相关题目 BFS 题单|LeetCode 广度优先搜索-BFS|OJ
有向无环图的拓扑序列
有向无环图
在图论中如果一个有向图从任意顶点出发无法经过若干条边回到该点则这个图是一个有向无环图DAGDirected Acyclic Graph。––有向无环图|维基百科 图片来源––图的拓扑排序|掘金
在一个有向图中一个顶点的**「出度」指的是由该顶点指出的边的总数一个顶点的「入度」**为指向该顶点的边的总数。
拓扑序列
拓扑排序是一种对有向无环图DAG中的所有顶点进行线性排序的方法使得对于任意一条有向边 (u,v)顶点 u 都排在顶点 v 的前面。拓扑排序可以用来表示一些有依赖关系的任务的执行顺序例如课程的选修顺序。
以一个生活中的例子理解拓扑排序在大学中的第一年我们学习的课程都是通识课例如高等数学概率论和线性代数等。只有学了这些前导课程才有可能学习后续的专业课。也就是说我们在不同阶段学习的课程是有先后顺序、依赖关系的。这也是有向图才会有拓扑序列的原因。
例如学习本科算法的前导课程不考虑 C 语言是高等数学-概率论-数据结构那么当学习高等数学时它是没有前导课程的所以我们可以直接学习它当学习完高等数学以后对于概率论而言我们已经学习了它的前导课程那么我们也可以直接开始学习概率论。… 因此在一个合法的拓扑序列中对于每一个当前元素而言它的所有依赖元素我们都已经访问过也就是它的入度为 0即它无需依赖任何元素。如果遍历了图中每个元素都符合这一规则那么这就是这个 DAG 的一种合法的拓扑序列。
BFS 思路 O ( n m ) O(nm) O(nm)
Kahn 算法是一种基于广度优先搜索BFS的拓扑排序算法它的切入点是拓扑序列的定义即一个元素的入度表示了它的依赖关系。BFS 的思想是枚举所有可能其实也是一种不断假设并尝试的过程BFS 能够一次遍历图中所有元素同时能够假设当前元素在何种条件下是复合某种规则的。那么元素的出度拿来做什么呢––出度是对于当前元素而言的它用来寻找这个元素后面的元素。
数据结构
二维数组ver[x][y]存储 x 元素的下一个邻居即x, y/x-y这条有向边。数组in[x]存储 x 元素的入度数组topo[]存储当前合法的拓扑序列[算法核心] 队列q维护一个入度为 0 的元素的集合
算法流程
枚举图中每个顶点把所有入度为 0 的顶点添加到队列q中。当队列q不为空时 在队列q中任取一个顶点 x一般为了方便取队头将 x 添加到到数组topo[]中将顶点 x 的所有出边x-y删除即删除边 (x, y)那么顶点 y 的入度就为 0将 y 入队q 循环结束队列为空如果数组topo[]的有效元素个数为 n那么说明所有元素都执行了上述步骤也就是说每个顶点都可以作为入度为 0 的点压入队列q中所以这是一个合法的拓扑序列否则说明图中存在环。
以一个简单的例子演示算法流程
假如图中有环 注意拓扑序列是不唯一的这取决于每次从队列取出元素的顺序。
代码
#include iostream
#include queue
using namespace std;const int N 100010;
int n, m;
int in[N];
vectorint ver[N], topo;bool TopoSort()
{queueint q;// 将所有入度为 0 的顶点入队for (int i 1; i n; i)if (in[i] 0) q.push(i);while (!q.empty()){// 取出队头元素 x理论上可以取队列中任意元素int x q.front();q.pop();topo.push_back(x);// 将 x 顶点的出边 (x, y) 全部删除// 当 y 顶点的入度为 0, 则入队for (auto y : ver[x])if (--in[y] 0) q.push(y);}return topo.size() n;
}int main()
{// 读入顶点数 n,m 行数据cin n m;for (int i 0; i m; i){int a, b;cin a b;// 读取 (a, b) 有向边b 的入度则1ver[a].push_back(b);in[b];}if (!TopoSort()) puts(-1);else for (auto e : topo) printf(%d , e);return 0;
}注意
ver 是一个二维数组它存储的是 x-y 有向边当读入这条边时y 顶点的入度要加 1。拓扑序列不是唯一的在一些 OJ 为了答案的一致性要求取出队列中编号较小的那一个这就需要用一个优先队列或栈来维护这个队列中的最大或最小值了。如果图中存在孤立点那么说明它是没有依赖某个顶点的所以它可以出现在拓扑序列的任意位置。在这个写法中算法的第一步就将所有入度为零的顶点入队包括孤立点。
这个算法的时间复杂度是 O ( n m ) O(nm) O(nm)其中 n n n 是顶点数 m m m 是边数。
遍历所有顶点计算每个顶点的入度并将入度为 0 的顶点入队。这一步的时间复杂度是 O ( n m ) O(n m) O(nm)不断从队列中取出一个顶点将其加入拓扑序列并将其所有出边删除即将其相邻顶点的入度减 1并将入度变为 0 的顶点入队。这一步的时间复杂度是 O ( n m ) O(n m) O(nm)因为每个顶点和每条边都只被访问一次。
参考资料 有向无环图|维基百科 图的拓扑排序|掘金 拓扑排序|哔哩哔哩
相关题目
确定比赛名次|HDOJ课程表|LeetCode题单拓扑排序|LeetCode
最短路径问题
最短路径问题是对于含有边权的图而言的主要分为以下几种分类的根据是已知的起点和终点的数量 确定起点的最短路径问题也叫单源最短路问题即已知一个起点求到其他所有点的最短路径。 边权为正 朴素 Dijkstra 算法 O ( n 2 ) O(n^2) O(n2)堆优化 Dijkstra 算法 O ( m l o g n ) O(mlogn) O(mlogn) 存在负权边 Bellman-Ford 算法 O ( n m ) O(nm) O(nm)SPFA 算法一般 O ( m ) O(m) O(m)最坏 O ( n m ) O(nm) O(nm) 它们的基本思想是动态规划/贪心思想即利用已知的最短路径信息更新其他点的最短路径。 全局最短路径问题也叫多源最短路问题即求图中任意两点之间的最短路径。 Floyd-Warshall 算法等方法解决。 它的基本思想是逐步扩展中间点的集合更新两点之间的最短路径。
值得注意的是在学习图论时经常会使用到贪心思想和动态规划问题在于证明它们的正确性尤其是贪心不是一件容易的事所以希望读者在初学过程中能够通过一定数量的经典案例来体会这两种思想适用于何种问题。 贪心和动态规划这两种思想在某些问题中往往难以明确地划分它们的区别但是它们的着眼点有所不同贪心关注问题的局部最优每一步都是最优的那么结果也是最优的如果贪心是正确的话动态规划虽然操作的是局部但是关心的是整体它不会漏掉任何一种情况而贪心可能会因为局部选择最优而漏掉一些情况。 单源最短路径问题
在单源最短路径问题Single Source Shortest Path中给定一张有向图 G ( V , E ) G(V, E) G(V,E)。 V V V是点集 E E E是边集 ∣ V ∣ n |V|n ∣V∣n ∣ E ∣ m |E|m ∣E∣m节点以 [ 1 , n ] [1, n] [1,n]之间的连续整数编号 ( x , y , z ) (x, y, z) (x,y,z)描述一条从 x x x出发到达 y y y权值/长度为 z z z的有向边。设 1 1 1号点位起点求长度为 n n n的数组 d i s t [ ] dist[ ] dist[]其中 d i s t [ i ] dist[i] dist[i]表示从起点 1 1 1到节点 i i i的最短路径长度。––算法竞赛进阶指南
题目描述
给定一个 n n n 个点 m m m 条有向边的带非负权图请你计算从 s s s 出发到每个点的距离。
数据保证你能从 s s s 出发到任意点。
输入格式
第一行为三个正整数 n , m , s n, m, s n,m,s。 第二行起 m m m 行每行三个非负整数 u i , v i , w i u_i, v_i, w_i ui,vi,wi表示从 u i u_i ui 到 v i v_i vi 有一条权值为 w i w_i wi 的有向边。
输出格式
输出一行 n n n 个空格分隔的非负整数表示 s s s 到每个点的距离。
样例输入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4样例输出
0 2 4 3其中 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105 1 ≤ m ≤ 2 × 1 0 5 1 \leq m \leq 2\times 10^5 1≤m≤2×105 s 1 s 1 s1
朴素 Dijkstra 算法 O ( n 2 m ) O(n^2m) O(n2m)
它的基本思想是从源点开始每次选择一个距离源点最近的未访问过的点然后用它来更新其他点的距离直到所有的点都被访问过或者找到了目标点。
数据结构
数组dist[]保存当前已经确定的最短路径的点下标从 s 开始下标 0 用作哨兵位。数组visited[]保存已经访问过的点。
具体步骤如下
初始化数组dist[]初始时源点到自己的距离为 0即dist[1]0源点到其他点的距离为无穷大用一个很大且不容易溢出的正整数表示如1e9或0x3f3f3f3f。初始化数组visited[]所有的点都未被访问过。重复以下操作直到所有的点都被访问过或者找到了目标点 从未访问过的点中也就是不在visited[]中选择一个距离源点最近的点记为 x。**[松弛操作]**将 x 标记为已访问并用 x 来更新其他未访问过的点 y 的距离即遍历即如果通过 x 到达某个点 y 的距离比原来的距离更短就更新距离数组中 x 的值为源点到 y 的距离加上 x 到 y 的距离。
注意x 就是当前最短路径的最新的那个点也是当前离原点最远的点不断地这样找下一个最近的点就能找到整张图中离原点的最短路径。 每次用 x 找最近的下一个点就好像在一个以 x 为起点的子图中找最短路径那么递归地从倒数第二个点往前看每一个子图连上一个最近的点就是更大的那个子图的最短路径。 松弛操作
松弛操作是最短路径算法中的一种基本步骤用于更新顶点之间的最短距离估计值。松弛操作的原理是如果从源点 s s s到顶点 u u u的最短距离加上从顶点 u u u到顶点 v v v的边的权重小于从源点 s s s到顶点 v v v的最短距离那么就可以用前者替换后者从而缩短从 s s s到 v v v的路径。
对边 ( u , v ) (u, v) (u,v)用 d i s t ( u ) dist(u) dist(u)和 l ( u , v ) l(u, v) l(u,v)的和尝试更新 d i s t ( v ) dist(v) dist(v)即 d i s t ( v ) m i n ( d i s t ( v ) , d i s t ( u ) l ( u , v ) ) dist(v)min(dist(v),dist(u) l(u, v)) dist(v)min(dist(v),dist(u)l(u,v))
例如下面就是一次成功的松弛操作 松弛操作的名称来源于一个类比把最短距离估计值看作是一根弹簧的长度初始时弹簧是被拉伸的随着最短路径的发现弹簧的长度会缩短也就是松弛。
松弛操作也可以理解为减少对变量的约束使得满足三角不等式在下面会提到它的条件更加宽松。松弛操作是很多最短路径算法的核心比如 Dijkstra 算法和 Bellman-Ford 算法它们都是通过不同的方式来确定边的松弛顺序从而求解最短路径问题。
用一个例子理解算法流程
注意在每轮更新时都是找 dist 数组中值最小的那个对应的顶点的出边来更新其它点的而不是按 dist 数组的顺序。 这个“其他点”指的是最小值对应的顶点的邻居顶点。在这步中B 的 dist 值被松弛更新为 3在目前对于 B 而言这是一条道起点的最短路径。
那么现在已经有两个点S 和 A 点已经被访问过了它们将会作为最短路径的顶点之一以后更新最短路时无需再访问它们。用蓝色路线标记。 这样 便找到了最短路径S-A-B-D-C-E。
算法的核心步骤是在 dist 中未访问过的顶点中用距离最小的那个来更新它自己的邻居顶点。
代码
#include iostream
#include cstringusing namespace std;int n, m, s;
const int N 10010, INF 1e9, M 2 * N;
int gra[N][N], dist[M];
bool visited[N];void dijkstra(int s)
{// 初始化memset(dist, 0x3f, sizeof(dist));memset(visited, false, sizeof(visited));dist[s] 0;// 重复操作 n 次每次选择一个最近的点for (int i 0; i n; i){// 在未被访问过的点中选择一个最近的点 x// min_dist 记录最小距离int x, min_dist INF;for (int j 1; j n; j){// 没有被访问过且距离更小则更新if (!visited[j] dist[j] min_dist){x j;min_dist dist[j];}}visited[x] true; // 标记 x 已被访问// 用 x 来更新其他未访问过的点的距离for (int y 1; y n; y) // 松弛操作dist[y] min(dist[y], dist[x] gra[x][y]);}if (dist[n] 0x3f3f3f3f) puts(-1);else for (int i 1; i n; i) cout dist[i] ;
}int main()
{cin n m s; // 读入点数/边数/起点memset(gra, 0x3f, sizeof(gra));// 如果图中可能存在重边或自环那么只读取那个较小的for (int i 0; i m; i) // 注意是读入边所以是 m{int x, y, z;cin x y z;gra[x][y] min(gra[x][y], z);}for (int i 1; i n; i) gra[i][i] 0;dijkstra(s);return 0;
}注意这段代码无法通过 OJ原因是朴素的 Dijkstra 算法时间复杂度很高OJ 限制了内存。Dijkstra 算法的时间复杂度取决于实现方式如果使用邻接矩阵即二维数组来存储图那么时间复杂度为$ O(n^2)$其中 n n n 是图中的点数。
OJ 题的限制是一回事使用邻接矩阵来存储图的原因是这个图是稠密图也就是边数 ∣ E ∣ |E| ∣E∣接近 ∣ V ∣ |V| ∣V∣稀疏图反之。主要是因为使用了二维数组来存储图的邻接矩阵这样会占用很多空间尤其是当图的边数远小于点数的平方时。可以使用邻接表来优化代码这样只需要存储每个点的相邻点和边权可以节省很多空间。
堆优化 Dijkstra 算法 O ( ( n m ) l o g n ) O((nm)logn) O((nm)logn)
堆优化 Dijkstra 算法解决了
二维数组占用过多内存遍历顶点效率低
思路和朴素的 Dijkstra 算法是一样的只不过是把二维数组中的数据交给堆来维护遍历的操作通过堆来实现。这么做就不能用二维数组来存储图了需要用链式前向星来存储图的邻接表在本文的「图的存储方式」中有介绍。
数据结构
数组dist[]和数组visited[]保存当前已经确定的最短路径的点和是不是第一次第一次出队这和朴素 Dijkstra 中的 visited 数组的含义是不同的。堆priority_queuepairint, int heap存储没有被访问过的点堆自动会将最小值放在堆顶。first 存储距离second 存储节点本身的编号不是数组的下标。链式前向星存储邻接表。
具体步骤如下
初始化数组dist[]和数组visited[]。重复以下操作直到堆heap为空 从堆heap中取出堆顶元素 x即距离当前路径最短的顶点取出后弹出它。判断 x 是否已经被访问过如果是则跳过这个点因为它可能是一个重复的点或者是一个已经确定最短距离的点。如果 x 没有被访问过就将其标记为已访问并遍历 x 的所有出边即从邻接表中找到所有与 x 相连的点 y 和边权 z。**[松弛操作]**将 x 标记为已访问并用 x 来更新其他未访问过的点 y 的距离也就是要遍历堆中每个元素符合条件则更新点 y 的距离dist[y]再将更新后的点 y 压入堆heap中。
代码
#include iostream
#include queue
#include cstringusing namespace std;int n, m, s;
const int N 100010, M N * 2;
int head[N], ver[M], edge[M], Next[M], idx;
int dist[N];
bool visited[N];// pair-dist[x], x
priority_queuepairint, int heap;
// 加边
void add(int x, int y, int z)
{idx;ver[idx] y;edge[idx] z;Next[idx] head[x];head[x] idx;
}void dijkstra(int s)
{// 初始化memset(dist, 0x3f, sizeof(dist));memset(visited, false, sizeof(visited));dist[s] 0;heap.push(make_pair(0, s));while (!heap.empty()){int x heap.top().second;heap.pop();if (visited[x]) continue;visited[x] true;for (int i head[x]; i ! 0; i Next[i]){int y ver[i], z edge[i];if (dist[y] dist[x] z){dist[y] dist[x] z;heap.push(make_pair(-dist[y], y));}}}if (dist[n] 0x3f3f3f3f) puts(-1);else for (int i 1; i n; i) cout dist[i] ;
}int main()
{cin n m s; // 读入点数/边数/起点for (int i 0; i m; i){int x, y, z;cin x y z;add(x, y, z);} dijkstra(s);return 0;
}注意 堆的元素的 first 值是负数是因为优先队列默认按照大根堆的方式排序也就是每次输出的是最大的元素。但是最短路径问题需要取最小值所以把正值取反这样就可以利用大根堆的性质实现小根堆的效果。 如果想修改优先队列以小根堆排序在定义优先队列的时候指定第三个模板参数 priority_queueint, int, greaterint heap; heap.pop();
if (visited[x]) continue;
visited[x] true;第一句和第三句表示x 顶点第一次出队时就给它打上「已访问」标记第二句表示除了第一次以外再出队就直接跳过 x。 这是因为堆顶维护的是当前两个集合相连边的最小权值第一次出队一定是当前堆中的最小值如果是第二次出队 说明在它之前还有更小的值那就不能再选 x 了。也就是说如果一个顶点被访问了多次那么则意味着有比之前找到的更短的路径到达该节点这与算法的保证相矛盾。这就保证了从起点到每个节点的最短路径只会被访问一次。即一张含有 n n n个顶点的图中最短路径经过的最多顶点数是 n − 1 n-1 n−1。 即使节点 x 已经被访问过也需要将它从优先队列堆中弹出吗 需要这是因为 Dijkstra 算法使用优先队列来存储待访问的节点而优先队列中的节点是根据到起点的距离排序的。如果一个已经被访问过的节点仍然留在优先队列中则会影响算法的效率。 [注] 实际上删除堆顶元素会破坏堆的结构这可能会降低效率一种做法是将它置为无效值使它不会成为堆顶但是会增加代码的复杂度好在建堆的时间复杂度是$ O(log n)$所以还是直接删除。
时间复杂度
朴素的 Dijkstra 算法中的松弛操作需要遍历二维数组的所有点来找到最小距离的点这样的时间复杂度是 O ( n 2 ) O(n^2) O(n2)其中 n n n是点的个数。如果用堆来优化就可以用一个优先队列来存储未确定最短距离的点每次从队列中取出距离最小的点这样的时间复杂度是 O ( l o g n ) O(logn) O(logn)然后再用 O ( l o g n ) O(logn) O(logn)的时间来更新其他点的距离总的时间复杂度是 O ( ( n m ) l o g n ) O((nm)logn) O((nm)logn)其中 m m m是边的个数。这样可以提高效率尤其是当图比较稀疏的时候。
补充
“无穷”的表示
在使用 Dijkstra 算法解决「最短路径问题」时使用到了数学上“无穷”的概念计算机的内存有限只能用一个绝对值很大的数字通常是整数来表示。
算法题目在设计时数据的数量级的上限一般取 1 0 9 10^9 109不超过即1e9。“无穷”的取值也可以是0x3f3f3f3f或0x7f7f7f7f或130它们的绝对值是 1061109567 1061109567 1061109567和 2139062143 2139062143 2139062143和 1073741824 1073741824 1073741824这么做的原因是有时候会对这个“无穷大”的数字做运算例如“无穷大的无穷大”那么它们的两倍不会让 int-32bit 4294967295 4294967295 4294967295溢出。在代码中这个很大的整数通常用INF来表示意为“无穷”。
memset函数按字节初始化空间只要数组中每个字节都是3f或者7f那么数组的所有元素都是“无穷”就无需使用循环来初始化数组了。
另外在全局的变量是有默认值的布尔类型的 visited 数组默认值是 false在代码中为了对应思路仍然显式地初始化了可以省略。
Dijkstra 算法的局限性
Dijkstra 算法的一个重要条件是图中的边的权重必须为正否则算法可能会得到错误的结果。这是因为算法的贪心策略是基于假设每次选择最近的点都不会导致之后的路径变长。如果存在负权重的边那么可能会出现通过更远的点反而使得路径变短的情况从而违反了算法的贪心策略。
参考资料
Dijkstra 求最短路算法|CSDN301 最短路 Dijkstra 算法|哔哩哔哩Dijkstra 算法堆优化|哔哩哔哩
Bellman-Ford 算法 O ( n m ) O(nm) O(nm)
题目P3385 【模板】负环
Bellman-Ford 算法可以解决 Dijkstra 算法不能处理负权边的情况和 Dijkstra 算法不同的是它是基于「迭代」的思想这一次不行那就算下一次。它的核心思路是对所有的边进行 n − 1 n-1 n−1轮松弛操作这样可以保证每个点的最短距离是正确的。因为在一个含有 n n n个顶点的图中任意两点之间的最短路径最多包含 n − 1 n-1 n−1边一条链。下一次迭代的结果是在本次的基础上进行的。
换句话说第 1 1 1轮在对所有的边进行松弛后得到的是源点最多经过一条边到达其他顶点的最短距离第 2 2 2轮在对所有的边进行松弛后得到的是源点最多经过两条边到达其他顶点的最短距离依此类推直到第 n − 1 n-1 n−1轮得到的是源点到其他所有顶点的最短距离。如果在第 n n n轮时也可能是之后还有可以松弛的边那么说明存在负权回路。
如果没有负权回路那么所有点的最短距离在 n − 1 n-1 n−1轮之后就不会再变化了反之沿着这个负权回路走一圈就可以使得某些点的最短距离变得更小理论上能到数学意义上的无穷小这样就会导致松弛操作无法收敛到一个确定的值。 算法流程
初始化数组dist[]。执行多轮迭代每次迭代都对图上所有边尝试一次松弛操作。当某一次迭代松弛操作失败即某一次迭代中所有顶点的dist[x]都没有发生变化算法终止。
下面用一个例子来理解算法流程
第一轮迭代 枚举每条边也就是遍历每个顶点然后枚举它们的所有出边理论上这个顺序可以是任意的通常按照编号来枚举边也就是例子中 S-E 这个顺序。 注意当枚举 B 的出边之前B 到起点的距离仍然是无穷的所以在这个基础上再扩展一次也没有任何意义所以先跳过它。如果 B 点是其他点的下一个点那么可能后面的点或者下一轮迭代可以用其他点来更新 B 点的 dist这样就能枚举 B 的出边了。 事实证明这么做是可行的最后的 E 点的出边指向了 D 点那么它可以更新 D 点的 dist。那么下一轮迭代就可以枚举 D 点的出边了。
第二轮迭代 可见随着迭代的继续有许多顶点都不能再更新它的出边的 dist 值了这说明算法接近尾声最短路逐渐确定。
为了演示的方便第三次迭代中只显示松弛操作成功的顶点不成功的顶点编号不会被染色。 那么在最短路存在的情况下一次迭代会使最短路的边数至少1而起点到每个顶点的最短路经过的边数最多为 n − 1 n-1 n−1因此这个算法最多会进行 n − 1 n-1 n−1轮迭代例如一条链。每轮迭代最坏可能要枚举所有边每轮迭代时间复杂度为 O ( m ) O(m) O(m)整体时间复杂度为 O ( n m ) O(nm) O(nm)。
判断图中是否存在负环
通过上面这个例子我们可以知道这个算法最多进行 n − 1 n-1 n−1轮迭代而且迭代这么多次以后就不会有顶点的 dist 值发生变化了。在『扩展最短路径』的意义下如果图中存在负环那么最短路径的长度理论上是无穷小这意味着循环会迭代无穷次。所以要找到负环只要在 n − 1 n-1 n−1的基础上再循环一次如果这一次循环中某个顶点的 dist 值发生了变化则说明有环。这在代码中体现了
代码
#include iostream
#include queue
#include cstringusing namespace std;int n, m, s;
const int N 100010, M 2 * N;
int head[N], ver[M], edge[M], nxt[M], idx;
int dist[N];void add(int x, int y, int z)
{idx;ver[idx] y;edge[idx] z;nxt[idx] head[x];head[x] idx;
}void BellmanFord(int s) // s 是起点
{memset(dist, 0x3f, sizeof(dist));dist[s] 0;bool relax; // 标记是否松弛成功// 进行 n-1 次迭代最后一次检验是否有环for (int i 1; i n; i) // 枚举每条边{relax false; // 初始化for (int x 1; x n; x) // 枚举每个顶点{// 距离为无穷大说明它肯定不是 x 经过的最短路径if (dist[x] 0x3f3f3f3f) continue; // 枚举以 x 为起点的所有出边for (int i head[x]; i ! 0; i nxt[i]){int y ver[i], z edge[i];if (dist[y] dist[x] z) // 松弛操作{dist[y] dist[x] z;relax true; // 成功后标记}}}// 如果没有任何松弛操作发生就提前结束循环因为已经找到了最优解if (!relax) break;}// 第 n 轮循环松弛失败说明有环if (relax false) cout NO endl;else cout YES endl;
}int main()
{int t;cin t;while (t--){idx 0, memset(head, 0, sizeof(head));cin n m;for (int i 0; i m; i){int u, v, w;cin u v w;add (u, v, w);if (w 0) add (v, u, w);}BellmanFord(1); // 以 1 为起点}return 0;
}注意
if (dist[x] 0x3f3f3f3f) continue; 这一行的作用是提高效率因为没有它的话后面的松弛操作会失败。这是因为如果一个点的距离为无穷大那么它不可能通过任何边来更新它的距离所以没有必要遍历它的出边。这样可以节省一些时间尤其是当图中有很多不连通的点时。在这道 OJ 中如果没有这一步优化会卡数据
参考资料
302 最短路 Bellman-Ford 算法 SPFA 算法|哔哩哔哩Bellman-Ford 算法|知乎Bellman-Ford 算法|知乎
SPFA O ( k m ) / O ( n m ) O(km)/O(nm) O(km)/O(nm)
题目
P3385 【模板】负环AB19**【模板】单源最短路 1**|牛客
在 Bellman-Ford 算法中存在负权边的图可能存在负环只有途经负环的图没有意义也就是不存在最短路径。所以每个顶点最多只能扩展一次为了保证这一点借鉴 Dijkstra 算法的堆优化即考虑使用堆来实现这个效果。
如果有负权边那么每个点只更新一次的话可能无法保证路径是最短的这样就会造成效率低下办法是取消“一次”的限制。
算法流程其实就是将 Bellman-Ford 算法中枚举顶点的操作用堆来维护
算法停止条件如果没有负环每个边都能成功进行松弛操作即都符合三角不等式。如果存在负边堆的存在并不能使得取最小值这个操作是最优的也就是说负边的存在可能会使得后面还会出现更小的值。那么这样不得不一直取堆顶元素直到取出最小的元素。但是这是本末倒置的因为使用堆来取最小值时间复杂度是 O ( 1 ) O(1) O(1)现在变成了 O ( l o g n ) O(logn) O(logn)。
因此不能使用堆来维护顶点集合考虑使用一个队列维护所有未被扩展的边。类似地为了判断顶点 x 是否被扩展过使用一个布尔类型的数组visited[]标记。
上面只是一个算法改进的尝试过程下面是大多数教程介绍的思路。
通过 BellmanFord 算法中的例子我们知道除了第一轮迭代之外常常会有一些顶点无法更新它的邻居顶点的 dist 值这是因为每一次迭代进行的松弛操作的参数值都是基于上一次迭代的结果而言的。
换句话说只有在上一次迭代中被更新了 dist 的顶点才有可能去更新其他顶点你可以再看看那个例子验证。因此在每一次迭代时将更新过 dist 的顶点用一个队列维护如果已经在队列中则不加在下一次迭代时只需要遍历队列中的顶点的出边即可。这样就可以省去很多重复且失败的松弛操作。
使用队列优化的 BellmanFord 算法即 SPFAThe Shortest Path Faster Algorithm的算法流程
初始化变量当队列不为空时重复以下步骤 取出队首元素 x并将其出队将 visited[x] 设为 false。遍历以 x 为起点的所有边 (x, y) 进行松弛操作 如果 y 不在队列中将 y 入队并将 visited[y] 设为 true。如果 y 入队的次数 cnt[y] 超过了顶点数 n说明存在负权环返回 true。 如果没有发现负权环返回 false。
SPFA 算法的核心思想是利用队列来存储待松弛的点每次从队列中取出一个点对其相邻的点进行松弛操作如果有更新就将相邻的点入队。这样可以避免对所有的边进行多次松弛提高了效率。
代码
#include iostream
#include queue
#include cstringusing namespace std;int n, m, s;
const int N 100010, M 2 * N;
int head[N], ver[M], edge[M], nxt[M], idx;
int dist[N], cnt[N]; // cnt 数组存储各个点入队的次数
bool visited[N];
queueint q; // 用于存储待松弛的点void add(int x, int y, int z)
{idx;ver[idx] y;edge[idx] z;nxt[idx] head[x];head[x] idx;
}bool spfa(int s)
{memset(cnt, 0, sizeof(cnt)); memset(dist, 0x3f, sizeof(dist));memset(visited, false, sizeof(visited));dist[s] 0;q.push(s);visited[s] true; // 将源点入队并标记为已访问while (!q.empty()) // 当队列不为空时循环执行{int x q.front(); q.pop(); visited[x] false; // 取出队首元素 x并出队标记为未访问for (int i head[x]; i ! 0; i nxt[i]) // 遍历以 x 为起点的所有边{int y ver[i], z edge[i]; // y 是边的终点z 是边的权值if (dist[y] dist[x] z) // 如果可以通过 x 到 y 的边松弛 y{dist[y] dist[x] z; // 更新 y 的最短距离if (cnt[y] n) return true; // 如果 y 入队的次数超过了 n说明存在负权环返回 trueif (!visited[y]) // 如果 y 不在队列中q.push(y), visited[y] true; // 将 y 入队并标记为已访问}}}return false; // 如果没有发现负权环返回 false
}int main()
{int t;cin t;while (t--){idx 0, memset(head, 0, sizeof(head));cin n m;for (int i 0; i m; i){int u, v, w;cin u v w;add (u, v, w);if (w 0) add (v, u, w);}if (spfa(1) true) puts(YES);else puts(NO);}return 0;
}注意
由于 OJ 是在循环中进行多次询问的所以在执行算法之前要将全局的变量清空。在将顶点 x 入队和出队后要立刻更新 visited[x] 的状态。
SPFA 的最坏时间复杂度是 O ( n m ) O(nm) O(nm) n n n是顶点数 m m m是边数。最坏情况发生在图中存在大量的负权边导致每个点都要入队多次或者存在特殊构造的边使得 SPFA 算法的队列顺序不利于松弛操作总之要入队多次。在图中没有或负权边很少的情况下SPFA 的效率可以达到 O ( k m ) O(km) O(km) k k k是每个点的平均入队次数在稀疏图中通常小于 2是一个常数。
参考资料
302 最短路 Bellman-Ford 算法 SPFA 算法|哔哩哔哩
相关题目 最短路题单|Luogu 最短路题单|LeetCode
最小生成树
题目描述
如题给出一个无向图求出最小生成树如果该图不连通则输出 orz。
输入格式
第一行包含两个整数 N , M N,M N,M表示该图共有 N N N 个结点和 M M M 条无向边。
接下来 M M M 行每行包含三个整数 X i , Y i , Z i X_i,Y_i,Z_i Xi,Yi,Zi表示有一条长度为 Z i Z_i Zi 的无向边连接结点 X i , Y i X_i,Y_i Xi,Yi。
输出格式
如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
样例
样例输入
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3样例输出
7图论知识回顾 子图是节点集和边集分别是某一图的节点集的子集和边集的子集的图。 生成子图是一个包含图中全部顶点的子图。也就是说每个顶点都是连通的。 生成树是一个包含图中全部顶点即含有 n n n个顶点而且由 n − 1 n-1 n−1条边组成的无环子图。 最小生成树Minimum Spanning TreeMST是最小权重生成树Minimum Weight Spanning Tree的简称是一副连通加权无向图中一棵权值最小的生成树。权值最小是指边的权值之和小于或者等于其它生成树的边的权值之和。 如果原图不连通则没有最小生成树。因为不满足生成子图的条件自然无法构成最小生成树。
最小生成树的分类主要有以下几种
根据图的稀疏或稠密最小生成树可以用 Kruskal 算法Prim 等算法求得。这些算法的基本思想都是从小到大或从大到小选择边使得构成的子图是连通的且没有环路。
在学习这两个算法之前你可以参看这个 动画演示 作为引入以更好地理解算法的流程。
朴素 Prim 算法 O ( n 2 m ) O(n^2 m) O(n2m)
朴素Prim 算法是一种求解图的最小生成树的贪心算法它的基本思想是从一个顶点开始逐步扩展生成树每次选择权值最小的边和顶点加入到生成树中直到所有的顶点都被覆盖。这和朴素的 Dijkstra 算法非常类似不同的是 Prim 算法的目的是求最小生成树它只关心边的权值而不关心路径的长度。
Prim 算法的核心思路是将图中顶点根据是否在最小生成树中划分为两个集合这可以通过一个 bool 数组visited[]来实现。每次在加入新顶点到最小生成树集合中时都是根据这两个集合之间的最小权值的边来选择下一个顶点的。
Prim 算法的流程如下
初始化一个数组visited[x]用于存储已经加入生成树的顶点 x以及一个数组minDist[]用于存储从visited[]集合到其他顶点的最小权值。将任意一个顶点加入visited[]并将其对应的 minDist 值设为 0将其他顶点的 minDist 值设为无穷大。重复以下步骤直到visited[]包含所有的顶点 从minDist[]数组中选择一个权值最小的顶点 x并将它加入到visited[]集合中标记 visited 值为 true。遍历 x 的所有邻接顶点 y如果 y 不在visited[]中且 x 到 y 的权值小于 y 的 minDist 权值就更新 y 的 minDist 值为 x 到 y 的权值表示 x 是 y 的父节点。 [可选] 最后根据 minDist 数组和父节点的信息输出最小生成树的边和权值。
用一个例子来理解算法的流程 注意这里的 minDist 数组和最短路径算法中的 dist 数组的含义是不同的。 这个算法需要将顶点视为两个集合每次扩展的都是两个集合之间权值最小的边。找的时候是通过顶点编号在第二行的 minDist 数组中找到两个集合之前的最小权值。 当找到这条边时还需要用这条边的蓝色顶点来更新它的蓝色邻居顶点的 minDist 值。 当所有点都被选择进最小生成树集合中算法停止。因为最小生成树的顶点数和图的顶点数相同。 代码
#include iostream
#include cstringusing namespace std;const int N 5010;
int n, m, ans, cnt;
// minDist 存储每个顶点到已选集合的最短距离pre 存储每个顶点的前驱
int gra[N][N], minDist[N], pre[N];
bool visited[N]; // 标记顶点是否已经加入已选集合最小生成树中
bool prim(int s)
{memset(minDist, 0x3f, sizeof(minDist));minDist[s] 0, ans 0; // ans 是最小生成树的权值和for (int i 0; i n; i) // 循环 n 次每次选择一个顶点加入到已选集合中{int x -1; // x 表示当前要选择的顶点for (int y 1; y n; y) // 遍历所有顶点找到距离已选集合最近的顶点{// 如果顶点 y 没有被访问过且距离比当前的 x 小就更新 x 为 yif (!visited[y] (x -1 || minDist[y] minDist[x]))x y;}if (i) ans minDist[x]; // 如果不是第一次循环就将 x 的距离累加到权值和中if (i minDist[x] 0x3f3f3f3f) return false; // 如果找不到最小的边说明图不连通返回 false// 更新其他顶点到已选集合的距离for (int y 1; y n; y){if (minDist[y] gra[x][y]) // 如果通过 x 能够缩短距离{minDist[y] gra[x][y]; // 更新 minDist 数组pre[y] x; // 更新 pre 数组记录 y 的前驱节点是 x}}visited[x] true;}return true; // 如果找到了 n-1 条边说明图连通返回 true
}int main()
{cin n m;memset(gra, 0x3f, sizeof(gra));for (int i 0; i m; i){int x, y, z;cin x y z;if (x ! y) // 排除自环{gra[x][y] min(gra[x][y], z); // 取最小的权重gra[y][x] min(gra[y][x], z);}}if (prim(1)) cout ans endl;else puts(orz);// 打印路径// for (int i 1; i n; i) // 对于每个顶点// {// for (int v i; v ! 0; v pre[v]) // 从当前顶点开始反向追踪// cout v - ;// cout 1 endl; // 源顶点是路径的起点// }return 0;
}
注意
需要考虑到图中可能存在重边和自环的情况在输入边的时候加上一句 gra[x][y] min(gra[x][y], z); 来保证取最小的权重加上一个判断 if (x ! y) 来排除自环。本题不存在图中可能有多个连通分量的情况也就是图不是连通的而是由若干个子图组成。这样在求最小生成树的时候应该对每个连通分量都进行一次 Prim 算法而不是只对一个节点为起点的连通分量进行。代码中使用了矩阵存储图这是因为朴素的 Prim 算法适用于稠密图当然也可以使用邻接表来存储表。在 minDist 中找一个最小值的顺序可以是任意的这是因为最小生成树已经被确定了如果存在的话顺序不会影响。
堆优化 Prim 算法 O ( ( n m ) l o g n ) O((nm)logn) O((nm)logn)
和朴素的 Dijkstra 算法类似朴素的 Prim 算法的时间复杂度是 O ( n 2 m ) O(n^2m) O(n2m) 最多需要 n 2 n^2 n2次找到一个 mindist 值 m m m条边都会被扩展一次。瓶颈在于每次从未标记的顶点中选择一个距离已选集合最近的顶点这个过程需要遍历所有的顶点所以需要 O ( n ) O(n) O(n)的时间。如果使用堆来维护两个集合之间的最小距离可以将时间复杂度降低到 O ( ( n m ) l o g n ) O((nm)logn) O((nm)logn) 其中 n n n是图中的点数 m m m是图中的边数。
需要注意的地方和堆优化的 Dijkstra 算法也是一样的
visited[]数组表示的是顶点是不是第一次出队。在 x 出队后要立刻标记 x 已经出了一次队。堆int, int存储的是-minDist[x], x默认以大根堆存储已选集合和未选集合之间的 minDist 用负数存储。
代码
#include iostream
#include cstring
#include queueusing namespace std;int n, m, ans, cnt;
const int N 5010;int gra[N][N], minDist[N];
bool visited[N]; // 标记 x 顶点是否是第一次出队
// -minDist[x], x 距离编号
priority_queuepairint, int heap;bool prim(int s)
{memset(minDist, 0x3f, sizeof(minDist));minDist[s] 0, ans 0;heap.push(make_pair(0, s));while (!heap.empty()){int x heap.top().second; heap.pop(); // 出队if (visited[x]) continue; // 只对第一次出队的顶点操作visited[x] true; // 标记ans minDist[x]; cnt; // 累计权值记录出队过的顶点数for (int y 1; y n; y)if (minDist[y] gra[x][y]) // 如果通过 x 能够缩短距离{minDist[y] gra[x][y]; // 更新 minDist 数组heap.push(make_pair(-minDist[y], y)); // 可以更新则入队}}return cnt n;
}int main()
{cin n m;memset(gra, 0x3f, sizeof(gra));for (int i 0; i m; i){int x, y, z;cin x y z;if (x ! y) // 排除自环{gra[x][y] min(gra[x][y], z); // 取最小的权重gra[y][x] min(gra[y][x], z);}}if (prim(1)) cout ans endl;else puts(orz);return 0;
}堆优化的 Prim 算法适用于稀疏图时间复杂度和 Kruskal 算法在同一个水平但是前者的思路和代码更复杂所以堆优化的 Prim 算法常被 Kruskal 算法替代。
参考资料
最小生成树 (Kruskal克鲁斯卡尔和 Prim普里姆) 算法动画演示|哔哩哔哩311 最小生成树 Prim 算法|哔哩哔哩
Kruskal 算法 O ( m l o g m ) O(mlogm) O(mlogm)
Kruskal 算法是一种求解图的最小生成树的贪心算法。它的基本思想是将所有点看作不同的集合将所有边按权值从小到大排列然后按顺序选取每条边如果这条边的两个端点不属于同一集合那么就将它们合并并将这条边添加到最小生成树的边集中直到所有的点都属于同一个集合为止。
值得注意的是在 Kruskal 算法中在查找最小生成树的意义下「集合」指的是一个「连通块」。合并两个集合需要使用并查集实现也就是从两个连通块中各自取出一个顶点将它们相连这样就合并为一个更大的连通块即一个集合。在并查集中通常用一个「代表元」来作为其他元素的父亲节点所以判断元素是否在同一个集合中只需要判断它们的代表元是否相同。
数据结构
edges[i]数组每个元素是一个结构体struct edge存储了第i条边 ( x , y ) (x,y) (x,y)以及权值 w w w。在这个结构体edge中重载了操作符operator()以支持调用库函数sort()进行排序。fa[x]数组存储的是 x 顶点并查集的代表元。
在 动画演示 中人手动操作起来还是比较简单的就是从排序好的边集中选取一条边x-y使得它在当前最小生成树边集中不构成环。转换成图论语言就是x和y不在一个集合中。 关于并查集的实现可以在我的博客 第 2 章数据结构【AcWing】 中查看。 算法流程
初始化并查集将 n 个顶点存入 n 个独立的集合将所有边按权值从小到大排序选边直到将 n-1 条边全部选取为止按顺序枚举每一条边 如果这条边连接的两个顶点x和y通过并查集得知不在同一集合就将这条边加入最小生成树的边集中并合并x和y所在的集合查找x和y的代表元。如果这条边连接的两个顶点x和y通过并查集得知在同一集合跳过它。
用一个例子来理解算法流程在演示的过程中同时记录了并查集的路径压缩。 在图中的红色路径表示这条边加入到最小生成树的边集中。 在演示过程中默认用编号小的那个顶点作为并查集的父节点但是在合并两个高度相差悬殊的集合时通常按秩合并即小集合并入大集合按高度。为了后续查找的方便通常会压缩路径即尽量将并查集的高度保持在 2 层所有孩子节点都是「代表元」。这是因为并查集在查找时是通过指定元素往前找父亲节点直到找到「代表元」。 省略了路径压缩的步骤这不是重点只要合并后的集合的代表元是同一个即可。 当每个顶点的集合都是同一个时算法停止 代码
#include iostream
#include algorithm
#include cstringusing namespace std;const int N 200010;
int n, m, ans, cnt, fa[N];
struct edge
{int x, y, w;bool operator (const edge e) const{return w e.w;}
}edges[N];// 并查集查找路径压缩
int find(int x)
{if (fa[x] x) return x;return fa[x] find(fa[x]);
}bool kruskal()
{sort(edges, edges m); // 排序for (int i 1; i n; i) fa[i] i; // 初始化并查集for (int i 0; i m; i) // 枚举每条边{// 取出这条边的两个顶点所在集合的代表元int x find(edges[i].x);int y find(edges[i].y);if (x ! y) // 不在同一个集合{fa[x] y; // 将 x 所在集合合并到 y 的ans edges[i].w;cnt; // 加入最小生成树边集中}}return cnt n - 1;
}int main()
{cin n m;for (int i 0; i m; i){int x, y, z;cin x y z;edges[i] {x, y, z};}if (kruskal()) cout ans endl;else puts(orz);return 0;
}注意
在算法流程的演示过程中为了方便演示使用了按秩合并但是算法中没有可选实际上通过路径压缩最后也能达到类似的效果。将 y 所在集合的代表元赋值给 x 的代表元这就直接 x 插入到了 y 所在集合。在算法的最后要用计数器判断是否 n-1 条边都被加入到了最小生成树边集中。
Kruskal 算法的思路和代码都不复杂甚至核心逻辑只需要用一个循环枚举所有边这个操作的时间复杂度是 O ( m ) O(m) O(m)当然也可以在这个循环中判断 cnt 是否提前达到了 n-1使得时间复杂度优化到 O ( n ) O(n) O(n)那么这个算法的性能瓶颈就是库函数sort()函数它的时间复杂度是 O ( m l o g m ) O(mlogm) O(mlogm) m m m是边数 n n n是点数。
实际上sort()的数量级虽然在 O ( m l o g m ) O(mlogm) O(mlogm)但是它的系数在各种情况下都是比较小的仍然是最快的排序算法。这使得 Kruskal 算法在多数情况下稀疏图能比其他求最小生成树的算法更优秀。
参考资料
312 最小生成树 Kruskal 算法|哔哩哔哩
相关题目
LeetCode1584. 连接所有点的最小费用LeetCode1334. 阈值距离内邻居最少的城市
二分图
二分图Bipartite Graph也叫偶图或二部图它的顶点可以分成两个互斥的独立集 U 和 V 的图使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价地二分图可以被定义成图中所有的环都有偶数个顶点。––二分图|维基百科 还记得小学的连线题吗它就是一个二分图。也就是说蓝色或绿色顶点之间没有边相连。 判断一个图是否是二分图的常用方法
染色法可以用 DFS 或 BFS 实现最大匹配数等于最小点覆盖数Hopcroft-Karp 算法
染色法判定二分图 O ( n m ) O(nm) O(nm)
性质二分图不存在长度为奇数的环简称奇环。 假设这个图中存在一个奇数环那么我们可以沿着这个环顺时针或逆时针遍历每次遇到一个顶点就给它染上与前一个顶点不同的颜色。由于这个环的长度是奇数那么当我们回到起点时它的颜色必然和第一个顶点的颜色相同这就产生了矛盾因为相邻的顶点颜色应该不同。所以这个图中不存在奇数环。 也就是说所有边的两个顶点一定属于两个不同的集合从一个顶点出发只有走偶数次才可能回到出发的那个集合。 染色法判定二分图图能够被染成黑白两种颜色且相邻的顶点颜色不同即这个图是二分图。
其正确性的简单证明
假设一个图中不存在奇数环可以用深度优先搜索或广度优先搜索来进行染色。
任选一个未染色的顶点给它染上任意一种颜色比如黑色。然后遍历它的所有邻接顶点如果有未染色的顶点就给它染上与当前顶点相反的颜色比如白色并继续遍历它的邻接顶点。如果遇到已经染色的顶点就检查它的颜色是否和当前顶点相同如果相同就说明染色失败返回 false如果不同就继续遍历。重复这个过程直到所有顶点都被染色返回 true。
要证明这个染色过程不会产生矛盾即不会出现两个相邻的顶点被染成相同的颜色。假设出现了这样的情况那么可以从这两个顶点出发沿着它们的染色路径向上回溯直到找到一个公共的祖先顶点或者回到起点。这样我们就构造了一个环且这个环的长度是奇数因为每次回溯都改变了一次颜色。这就和假设矛盾因为这个图中不存在奇数环。所以这个染色过程不会产生矛盾即这个图是二分图。
数据结构
邻接表存储图。数组color[i]数组存储第i个顶点的颜色。1是白色2是黑色。或者说颜色是1或2。
算法流程
初始化颜色color[]为0表示未染色。每次选择一个未被染色的顶点x先将它染为1然后用 DFS 枚举x的邻居顶点y。 如果y未染色DFS 进入。如果返回「有奇环」则将y顶点所在的 DFS 路径往上一路返回「有奇环」。如果y已染色且颜色与x相同返回「有奇环」。 枚举完x的所有邻居顶点如果没有发现奇环则返回「没有奇环」。即这是一个二分图。
用一个例子理解算法流程 注意当判断已经染色后还需要判断y的颜色是否和xx 是 DFS 进入的入口顶点的相同。在这个例子中不存在奇环的情况。 这是一个极端且显然的例子如果在 DFS 时遇到了已经染色并且颜色和 DFS 入口顶点颜色相同那么说明它们是同一个集合中的并且这会形成一个奇边数的环。
代码
#include iostreamusing namespace std;const int N 100010, M 2 * N;
int head[N], ver[M], nxt[M], idx;
int color[N]; // 表示每个点的颜色
int n, m;void add(int x, int y)
{idx;ver[idx] y;nxt[idx] head[x];head[x] idx;
}
// x 表示当前节点col 表示当前点的颜色
bool dfs(int x, int col)
{color[x] col; // 将当前节点染色for (int i head[x]; i ! 0; i nxt[i]) // 枚举 x 的所有邻点 y{int y ver[i];if (!color[y]) // 如果 y 已经染色{if (dfs(y, 3 - col)) return true; // 连通块中出现了奇环}else if (color[y] col) return true; // 如果 y 和 x 的颜色相同说明是奇环}return false; // 没有奇环
}int main()
{cin n m; // 读入点数和边数for (int i 0; i m; i){int x, y;cin x y;add(x, y);add(y, x);}bool flag false; // 标记奇环for (int i 1; i n; i) // 枚举所有顶点{if (!color[i]) // 没有染色则 DFS{if (dfs(i, 1)) // DFS 入口染 1{flag true; // 返回有环break; // 提前结束}}}if (flag) puts(No); // 有奇环则不是二分图else puts(Yes);return 0;
}注意代码中的dfs(y, 3 - col)col 是当前顶点 x 的颜色那么它的意思是让 y 的颜色和 x 的不同例如 col 是 1那么 y 就是 2如果 col 是 2y 就是 1。
DFS 遍历所有点对路径上的点交替染色时间复杂度是 O ( n m ) O(nm) O(nm) n n n是点数 m m m是边数。
题目
785. 判断二分图|LeetCode
补充
二分图有以下性质
二分图的最大匹配数等于最小点覆盖数。其中最小点覆盖数是指选取最少的点使得每条边至少有一个端点被选中。二分图的最大独立集大小等于顶点数减去最小点覆盖数。其中最大独立集是指选取最多的点使得这些点之间没有边相连。二分图的最小点覆盖数等于顶点数减去最大匹配数。二分图的最小割等于最大流。
参考资料
381 二分图判定 染色法|哔哩哔哩
二分图最大匹配
题目描述
给定一个二分图其左部点的个数为 n n n右部点的个数为 m m m边数为 e e e求其最大匹配的边数。
左部点从 1 1 1 至 n n n 编号右部点从 1 1 1 至 m m m 编号。
输入格式
输入的第一行是三个整数分别代表 n n n m m m 和 e e e。
接下来 e e e 行每行两个整数 u , v u, v u,v表示存在一条连接左部点 u u u 和右部点 v v v 的边。
输出格式
输出一行一个整数代表二分图最大匹配的边数。
样例
样例输入
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1样例输出
2相关概念 一组匹配在二分图 G G G的一个子图 M M M中任意两条边都没有公共顶点那么称 M M M为 G G G的一组匹配。 最大匹配在二分图中包含边数最多的一组匹配。即在一个二分图中找出一个最大的边集使得这些边没有公共的顶点。二分图最大匹配的大小等于最小点覆盖的大小也等于最大独立集的补集的大小。 例如在一个有若干男和女的集合中两两配对最大匹配就是最多能配对的男女。 交错路/交替路指一条从未匹配顶点出发依次经过非匹配边和匹配边交替出现的路。增广路指一条从未匹配顶点出发起点和终点都未被匹配的交错路。 增广路也是一种贪心思想。通过这个例子我们还可以知道一下结论假设所有边的两个点集分为「左边」和「右边」那么一条交错路径必定会从左边走到右边。所以枚举所有的交错路径交错路径本身就是从未匹配点出发的必定能访问二分图中的所有顶点。
因此为了阐述算法流程和执行的方便只需要枚举左边的未匹配点即可。
常用的求解二分图最大匹配的算法有 匈牙利算法 KM 算法
在本节中介绍比较入门的匈牙利算法。
匈牙利算法 O ( n m ) O(nm) O(nm)
匈牙利算法是基于增广路的思想每次从左边未匹配点出发寻找一条交错路径如果能找到右边未匹配点就可以增加一条匹配边否则就尝试给已匹配的点换一个匹配对象直到找不到增广路为止此时意味着达到最大匹配。这可以用 DFS 和 BFS 实现。
数据结构 x在左边y在右边。 ans记录最大匹配数。 邻接表存储表。 数组visited[y]标记y顶点是否被访问过不是被匹配。 数组match[y]存储y匹配的另一个顶点x。
算法流程
从二分图中任选一个匹配作为初始匹配。对于每个未匹配的点尝试从它出发寻找一条增广路。如果找到了增广路就将增广路上的匹配边和非匹配边交换从而增加一个匹配边然后继续寻找下一个未匹配的点。如果找不到增广路就说明当前的匹配已经是最大匹配算法结束。
DFS
枚举左边n个顶点每轮都要初始化visited[]为false表示对于左边每个顶点右边每个顶点都是可选的。DFS 返回「可配对」计数ans。枚举左边第x个顶点的邻点y 如果y已访问过跳过。如果y没有被访问且没有配对即match[y]是 0那么将y和x配对标记y已访问。如果y没有被访问过且配对即match[y]是xy 的原配那么对x进行 DFS如果返回值是「可配对」那么就将x和y配对第三者y和x抛弃。标记y已访问。否则枚举x的下一个邻点。 当枚举完x的邻点后全都无法配对返回false。
用一个例子理解算法流程 每个 DFS 右边绿色的边表示目前已经被配对的边右边红色的边表示目前的最大匹配紫色边表示被废弃的边。当 DFS(2) 时增广路是 2-6-1-7将原本的匹配 1-6 增加到 1-7 和 2-6那么 1-6 这条边就相当于被废弃了。 代码
#include iostream
#include cstring
using namespace std;const int N 100010, M N * 2;
int head[N], ver[M], ntx[M], idx;
int n, m, k, ans;
bool visited[N]; // 标记右边顶点 y 是否被访问过
int match[N]; // 记录右边顶点 y 匹配的右边顶点 xvoid add(int x, int y)
{idx;ver[idx] y;ntx[idx] head[x];head[x] idx;
}
// dfs: 尝试为左边顶点 x 找到一个匹配的右边顶点 y
bool dfs(int x)
{for (int i head[x]; i ! 0; i ntx[i]) // 枚举 x 的所有邻接边{int y ver[i]; // 取出当前邻接边的右边顶点 yif (visited[y]) continue; // 如果 y 已经被访问过说明已经尝试过匹配 y跳过这个顶点visited[y] true; // 否则标记 y 为已访问if (!match[y] || dfs(match[y])) // 如果 y 没有匹配的左边顶点 x或者 x可以找到另一个匹配的右边顶点{match[y] x; // 那么就将 x 和 y 匹配起来return true; // 并返回 true表示找到了一个匹配}}return false; // 如果遍历完所有邻接边都没有找到匹配返回 false表示没有找到匹配
}int main()
{// n 和 m 表示左右点集数量cin n m k; // 变量 k 表示左右两边顶点之间的边的个数for (int i 0; i k; i){int x, y;cin x y;add(x, y);}// 遍历每一个左边顶点 xfor (int i 1; i n; i){// 对于每个 x, 右边都是可访问的memset(visited, 0, sizeof(visited));if (dfs(i)) ans; // 尝试为 x 找到一个匹配的右边顶点}// 遍历完所有的 xans 即二分图的最大匹配数cout ans endl;return 0;
}注意
再次强调这个算法是将二分图视为两个点集和一个边集只需要枚举其中一个边集通过 DFS 就可以枚举从左边顶点出发的连通块因为是二分图每一条边的顶两个顶点一定是一左一右所以必定可以访问到右边的顶点然后回到左边未匹配的顶点。DFS 的框架很明显枚举 x 的邻边 y然后看 y 是不是被访问过没有访问过的话就标记已访问 y然后判断 y 是否符合某种条件决定对其继续 DFS 还是直接返回。算法的核心在于if (!match[y] || dfs(match[y]))这是一个让 y 退而求其次的过程。 如果 y 没有匹配的左边顶点 x’那么 y 和 x’就可以直接匹配。或者 x’可以找到另一个匹配的右边顶点。也就是 x’可能不止一个心仪的 y’但是都还没确定关系所以让 x’放弃 y即标记 y 已经匹配现在 x 就能和 y 配对了。
这个算法的时间复杂度是 O ( n m ) O(nm) O(nm)其中 n n n是左边顶点的个数 m m m是右边顶点的个数。这是因为每次调用 DFS 函数都会遍历一个左边顶点的所有邻接边而每个右边顶点最多被访问一次。
参考资料
382 二分图最大匹配 匈牙利算法|哔哩哔哩
相关题目
二分图题单|Luogu
