最小生成树
最小生成树针对无向图,有向图不会用到
Prim
求解稠密图的最小生成树
和Dijkstra的思想相似,两者都是基于贪心
区别在于Dijkstra求单源最短路,而Prim求最小生成树
最小生成树:用最少的边连通图中所有的点,使得这些边的权值和也最小
Prim中的dis数组
含义:点到集合的最短距离,注意与Dijkstra对比,不是点到源点的最短距离!
外循环迭代n次,每次选择一个点加入集合
也可以理解为迭代n次,每次选择一条与集合距离最短的边加入集合,不过第一次迭代无法选择边,只能随便选一个点作为集合中的元素,后续的迭代就是选择边(选择一条边,连接集合内的点与集合外的点,并且该边的权值最小)
选择完一个点后,更新集合外的点到集合的距离
由于新的点加入了集合,连接集合内外点的边发生了变化,需要更新dis数组
,使集合外的点到集合的距离最小
总结下:
- 迭代n次
- 根据
dis数组
每次选择一个与集合距离最近的点 - 用该点更新
dis数组
由于要求最小生成树,所以迭代的过程中用res
记录最小生成树的权值和
当找不到距离集合最近的点时(距离为正无穷),退出迭代,因为无法找到最小生成树
模板:
const int INF = 0x3f3f3f3f;
int g[N][N], dis[N], st[N];
int prim()
{
memset(dis, 0x3f, sizeof(dis));
int res = 0;
for (int i = 0; i < n; ++ i )
{
int t = -1;
for (int j = 1; j <= n; ++ j)
if (!st[j] && (t == -1 || dis[j] < dis[t])) t = j;
if (i && dis[t] == INF) return INF;
if (i) res += dis[t];
st[t] = true;
for (int j = 1; j <= n; ++ j )
dis[j] = min(dis[j], g[t][j]);
}
return res;
}
用堆优化prim算法,可以求解稀疏图的最小生成树。不过稀疏图的最小生成树有更优的解法——Kruskal
Kruskal
求解稀疏图的最小生成树
- 将所有边按权值从小到大排序
- 枚举每条边,x,y,d ,若两点位于不同的集合,合并两集合(选择这条边)
1为该算法的效率瓶颈,时间复杂度为O(logn),2的时间复杂度为 O(m)
开始时每个点自成集合(可以理解为连通块),贪心地选择权值最小且连接两个连通块的边,直到边的数量为n - 1(点的数量 - 1),最小生成树构造完成
其中:合并集合与查找某个元素所在集合的操作为并查集的基本操作,很简单
不需要用邻接矩阵或邻接表存储边,直接用结构体存储边,简单且方便排序。重载该结构体的小于运算符,按照权值进行小于比较
const int INF = 0x3f3f3f3f;
int p[N];
struct Edge
{
int x, y, w;
bool operator<(const Edge& e)
{
return w < e.w;
}
}edges[M];
int find(int x)
{
if (x != p[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;
int x, y, w;
int cnt = 0, res = 0;
for (int i = 0; i < m; ++ i )
{
auto t = edges[i];
x = t.x, y = t.y, w = t.w;
x = find(x), y = find(y);
if (x != y)
{
res += w;
cnt ++ ;
p[x] = y;
}
}
if (cnt == n - 1) return res;
return INF;
}
二分图
二分图:将所有点划分成两个集合,使得所有边连接两个集合,即集合内没有边
一个图是二分图,当且仅当图中不含奇数环
图中不含有奇数环,那么图是二分图
必要性:遍历一个奇数环,假设起点属于集合A,那么下一个点一定属于集合B,下一个点一定属于集合A…这样推导到最后,结果是起点属于集合B,与二分图的性质矛盾
充分性:由于图中不不存在奇数环,所以染色过程不会出现矛盾,那么所有的点都能正确染色,使点集被分为两个集合
反证法:假设染色过程出现了矛盾,能否推出图中一定含有奇数环?
染色法
判断二分图
通过深搜或者广搜将每个点染上颜色
出现矛盾,不是二分图
不出现矛盾,就是二分图
维护一个color数组
,由于需要染两种颜色,用1和2表示这两种颜色,0表示该点为染色
从任意一个点开始进行染色,染色的过程是一个dfs。先对当前点染色,若下一个要遍历的点未染色,那么染上和当前点相反的颜色。然后需要判断这个递归是否出现矛盾,若出现矛盾返回false
若下一个要遍历的点染色了,判断其颜色是否和当前点相同,若相同则说明该图不是一个二分图,返回false
dfs最后返回true
由于需要判断的图可能是非连通图,所以需要遍历每一个点,若当前点没有染色,则将其作为dfs的起点进行染色
模板:
bool dfs(int x, int c) // x表示点的编号,c表示要染的颜色
{
color[x] = c;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i]; // 获取下一点的编号
if(!color[j])
{
if (!dfs(y, 3 - c)) // 3 - c将1变成2,2变成1,也就是相反颜色
return false;
}
else if(color[j] == c) return false;
}
return true;
}
bool flag = true;
for (int i = 1; i <= n; ++ i )
{
if (!color[i])
{
if (!dfs(i, 1))
{
flag = false;
break;
}
}
}
if (flag == false) // 不是二分图
else // 是二分图
匈牙利算法
二分图的最大匹配
在二分图中求子图,子图中不存在邻接两条边的点,即两点通过一条边匹配
对于二分图的两个顶点集合,假设为n1
和n2
遍历n1
的所有点,对于每个点,遍历邻接该点的所有边
- 若另外一点未匹配,则选择该点,匹配成功
- 若另外一点已经匹配,试着让其匹配的对象匹配其他点
- 若其匹配的对象能够匹配其他点,那么两点匹配成功
- 若其匹配的对象无法匹配其他点,那么两点匹配失败
时间复杂度为O(nm),这是最坏情况,一般情况下是线性复杂度
以上操作中,匹配
是一个相同子问题,所以总问题可以用匹配
这个子问题分解
对于逻辑中的一些细节:
遍历点的所有邻边时,需要注意对方是否已经匹配,这里用match数组
表示对方已经匹配的点,默认值为0(没有0号点)表示还未匹配
当对方已经匹配,此时要看对方的匹配对象是否能匹配其他点。也就是假设对方已经和自己匹配,判断对方的匹配对象在不选择对方的情况下,是否能匹配成功
所以这里需要一个状态表示对方已经和自己匹配的假设,用st数组
表示当前点正在考虑或考虑完成某点。每次遍历某点的邻边时,先设置st数组
,以表示自己正在考虑对方
接着会出现两种情况:
- 对方没有匹配,此时和对方匹配成功
- 对方已经匹配,对方的匹配对象需要在不考虑对方的情况下,试着匹配其他点。不考虑对方的前提通过
st数组
限制,对方的匹配对象每次匹配前通过st数组
判断试着匹配的对象是否被考虑,正在被考虑的点无法被匹配
- 当前点试着匹配对方时,可能匹配成功,可能匹配失败。匹配失败的情况下,
st数组
对应位置表示该点被考虑完成(已经无法匹配),后续不需要再考虑该点了
考虑
和匹配
是两个不同的概念,两者无法等价
已经被匹配的情况下,可以让对方的匹配对象重新匹配。若对方的匹配对象重新匹配失败,此时考虑完成,对方真的无法匹配
然后试着匹配下一条邻边的对象,若对方的匹配对象需要重新匹配,那么他就不应该试着匹配已经考虑完成的点
考虑完成的点一定无法匹配,虽然考虑完成分为匹配成功与匹配失败两种情况,但是匹配成功后,st数组失去了意义(此时要匹配n1
的下一个点),因为该数组要被重置
只有无法匹配的情况下,考虑完成的点(st数组)才有意义,因为它将限制其他点的匹配与重新匹配。因此这时的st数组的含义变成了:该点是否被强绑定(该点的对象无法匹配其他点了,此时两点只能绑定在一起)
匹配下一个n1
中点的对象时,将st数组被重置为false,表示n2
中所有的点未被考虑过
虽然是无向图,但是我们只要存储n1
到n2
的边, n2
到n1
的边没必要存
模板:
int h[N], e[N], ne[N], idx = 1;
bool st[N];
int match[N];
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;
}
最小生成树练习题
858. Prim算法求最小生成树
858. Prim算法求最小生成树 - AcWing题库
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int g[N][N], dis[N];
bool st[N];
int n, m;
int prim()
{
memset(dis, 0x3f, sizeof(dis));
int res = 0;
for (int i = 0; i < n; ++ i )
{
int t = -1;
for (int j = 1; j <= n; ++ j)
if (!st[j] && (t == -1 || dis[j] < dis[t])) t = j;
if (i && dis[t] == INF) return INF;
if (i) res += dis[t];
st[t] = true;
for (int j = 1; j <= n; ++ j )
dis[j] = min(dis[j], g[t][j]);
}
return res;
}
int main()
{
memset(g, 0x3f, sizeof(g));
scanf("%d%d", &n, &m);
int x, y, d;
while (m -- )
{
scanf("%d%d%d", &x, &y, &d);
g[x][y] = g[y][x] = min(g[x][y], d);
}
int t = prim();
if (t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}
859. Kruskal算法求最小生成树
859. Kruskal算法求最小生成树 - AcWing题库
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
const int INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge
{
int x, y, w;
bool operator<(const Edge& e)
{
return w < e.w;
}
}edges[M];
int find(int x)
{
if (x != p[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;
int x, y, w;
int cnt = 0, res = 0;
for (int i = 0; i < m; ++ i )
{
auto t = edges[i];
x = t.x, y = t.y, w = t.w;
x = find(x), y = find(y);
if (x != y)
{
res += w;
cnt ++ ;
p[x] = y;
}
}
if (cnt == n - 1) return res;
return INF;
}
int main()
{
scanf("%d%d", &n, &m);
int x, y, d;
for (int i = 0; i < m; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
edges[i] = { x, y, d };
}
int t = kruskal();
if (t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}
二分图练习题
860. 染色法判定二分图
860. 染色法判定二分图 - AcWing题库
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx = 1;
int color[N];
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
bool dfs(int x, int c)
{
color[x] = c;
for(int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!color[y])
{
if (!dfs(y, 3 - c)) return false;
}
else if (color[y] == c) return false;
}
return true;
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
int x, y;
while (m -- )
{
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
bool flag = true;
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;
}
debug:把int color[N]
写成bool color[N]
,看了半天,乐文章来源:https://www.toymoban.com/news/detail-533905.html
861. 二分图的最大匹配
861. 二分图的最大匹配 - AcWing题库文章来源地址https://www.toymoban.com/news/detail-533905.html
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], idx = 1;
int match[N];
bool st[N];
int n1, n2, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = 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));
int x, y, res = 0;
while (m -- )
{
scanf("%d%d", &x, &y);
add(x, y);
}
for (int i = 1; i <= n1; ++ i )
{
memset(st, false, sizeof(st));
if (find(i)) res ++ ;
}
printf("%d\n", res);
return 0;
}
到了这里,关于第三章 搜索与图论(三)——最小生成树与二分图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!