二分图与最小生成树
发布日期:2022-02-24 01:06:48 浏览次数:9 分类:技术文章

本文共 6937 字,大约阅读时间需要 23 分钟。

二分图与最小生成树

最小生成树

最小生成树对应的问题都是无向图

最小生成树算法 :

  1. Prim算法
    1. 稠密图 : 朴素版Prim算法 O( n^2 ) [^代码短 一般用于稠密图]
    2. 稀疏图 : 堆优化版Prim算法 O( mlog(n) ) [^不常用]
  2. Kruskal算法 O( mlog(m) ) [^一般用于稀疏图]

捋清算法思路 , 弄清楚算法的流程 , 不是死记模版

朴素版Prim算法

集合 s 表示当前已经在连通块中的点

步骤 :

  1. 将所有距离初始化为正无穷 . dist[i] --> INF
  2. 进行 n 次迭代 , for(int i = 0;i < n;i ++ )
    1. 找到 不在集合 s 中的距离最小的点
    2. 用 t 更新其他点到 集合(与Dijkstra算法的区别处) 的距离
    3. 将 t 加入到集合当中 st[t] = true

模版 :

给定一个n个点m条边的无向图 , 图中可能存在重边和自环 , 边权可能为负数.

求最小生成树的树边权重之和 , 如果最小生成树不存在则输出 impossible.

1 <= n <= 500 , 1 <= m <= 10^5

输入样例 :

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

输出样例 :

6

点到集合的距离 : 点到集合中的点的所有边中最短的那条边

最小生成树中, 没有环 , 因此正边和负边都可以

代码如下 :

// 朴素版 Prim算法 :#include 
#include
#include
using namespace std ;const int N = 510 , INF = 0x3f3f3f3f ;int dist[N] ; bool st[N] ; int n , m ; int g[N][N] ; // 稠密图 , 邻接矩阵存储int prim(){
memset(dist,0x3f,sizeof dist) ; // 初始状态 , 所有点到集合的距离均为无穷大 int res = 0 ; // res 记录最小生成树的各边的权值的和 // n 个点 , 迭代 n 次 for(int i = 0;i < n;i ++ ) {
int t = -1 ; // 从集合外的点集中找到距离当前集合距离最短的点 , 第一次时随机选择 for(int j = 1;j <= n;j ++ ) {
if(!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j ; } } if(i && dist[t] == INF) return -1 ; // 如果当前不是第一个点且其到集合的距离为INF,则该图不连通 if(i) res += dist[t] ; // 注意 : 这里可能存在自环的情况 , 所以应该先累加边的权值 , 再进行更新 for(int j = 1;j <= n;j ++ ) dist[j] = min(dist[j] , g[t][j]) ; // 更新集合外的点到集合的距离 st[t] = true ; // 将点 t 加入到集合当中 } 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 == -1) puts("impossible") ; else printf("%d \n",t) ; return 0 ;}

Kruskal算法

步骤 :

  1. 将所有边按权重从小到大排序( sort ) 时间复杂度 : O( mlogm ) e
  2. 枚举每条边 a --> b , 权重为 c .
    1. 如果 a , b 不连通 , 将这条边加入到集合中 ( 并查集的简单应用 )

模版 :

给定一个n个点m条边的无向图 , 图中可能存在重边和自环 , 边权可能为负数.

求最小生成树的树边权重之和 , 如果最小生成树不存在则输出 impossible.

不需存图 , 直接开一个结构体存边即可

输入样例 :

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

输出样例 :

6

代码如下 :

// Kruskal 算法 :#include 
#include
using namespace std ;const int N = 100010 ;int n , m ; int p[N] ;struct Edge{
int a , b , w ; bool operator< (const Edge & W) const // 重载小于号 , 使排序的时候按w的值排序 {
return w < W.w ; }}edges[N];int find(int x){
if(p[x] != x) p[x] = find(p[x]) ; return p[x] ;}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} ; } sort(edges , edges + m) ; for(int i = 1;i <= n;i ++ ) p[i] = i ; // 初始化并查集数组 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) {
p[a] = b ; res += w ; cnt ++ ; } } if( cnt != n - 1 ) puts("impossible") ; else printf("%d \n",res) ; return 0 ;}

二分图

简介 : 二分图,又称二部图,英文名叫 Bipartite graph。

节点由两个集合组成,且两个集合内部没有边的图。

换言之,存在一种方案,将节点划分成满足以上性质的两个集合。

*性质 : 二分图不存在长度为奇数的环 充分必要

因为每一条边都是从一个集合走到另一个集合,只有走偶数次才可能回到同一个集合。

染色法

时间复杂度 : O ( n + m ) 线性 . 类似于dfs

如果在染色过程中出现矛盾 --> 存在奇数环 , 不是二分图

反之 , 则是二分图

模版 : 染色法判定二分图 :

给定一个n个点m条边的无向图 ,图中可能存在重边或自环,判断这个图是否是二分图

输入样例 :

4 4

1 3

1 4

2 3

2 4

输出样例 :

Yes

代码如下 :

// 二分图的染色法 : #include 
#include
#include
using namespace std ; const int N = 100010 , M = N << 1 ; int h[N] , e[M] , ne[M] , idx ; int color[N] ; int n , m ; 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 点染色 for(int i = h[u] ; i != -1;i = ne[i]) {
int j = e[i] ; if (!color[j]) {
if(!dfs(j,3 - c)) // 因为 j 是u 的相邻点 , 所以给其染色时要与u不一样 , 3-u即可 {
return false ; } } else if (color[j] == c) return false ; // 如果 j 的颜色与 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 ; for(int i = 1;i <= n;i ++ ) {
if(!color[i]) {
if(!dfs(i,1)) {
flag = false ; break ; } } } if(!flag) puts("No") ; else puts("Yes") ; return 0 ; }

匈牙利算法

时间复杂度 : O ( mn ) , 实际运行时间一般远小于 O( mn )

匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。

交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。

增广路有一个重要特点:非匹配边比匹配边多一条。因此,研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边,所以这样做不会破坏匹配的性质。

我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(这是增广路定理)。匈牙利算法正是这么做的。

匈牙利树一般由 BFS 构造(类似于 BFS 树)。从一个未匹配点出发运行 BFS(唯一的限制是,必须走交替路),直到不能再扩展为止。

匈牙利树要求所有叶子节点均为匹配点.

匈牙利算法 : 求解一个图中的最大匹配

匈牙利算法的要点如下

  1. 从左边第 1 个顶点开始,挑选未匹配点进行搜索,寻找增广路。
    1. 如果经过一个未匹配点,说明寻找成功。更新路径信息,匹配边数 +1,停止搜索。
    2. 如果一直没有找到增广路,则不再从这个点开始搜索。事实上,此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去,而不影响结果。
  2. 由于找到增广路之后需要沿着路径更新匹配,所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈,而 BFS 版本使用 prev 数组。

性能比较

两个版本的时间复杂度均为O(V⋅E)O(V⋅E)。DFS 的优点是思路清晰、代码量少,但是性能不如 BFS。我测试了两种算法的性能。对于稀疏图,BFS 版本明显快于 DFS 版本;而对于稠密图两者则不相上下。在完全随机数据 9000 个顶点 4,0000 条边时前者领先后者大约 97.6%,9000 个顶点 100,0000 条边时前者领先后者 8.6%, 而达到 500,0000 条边时 BFS 仅领先 0.85%。

补充定义和定理:

最大匹配数:最大匹配的匹配边的数目

最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择

最大独立数:选取最多的点,使任意所选两点均不相连

最小路径覆盖数:对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为 0(即单个点)。

定理1:最大匹配数 = 最小点覆盖数(这是 Konig 定理)

定理2:最大匹配数 = 最大独立数

定理3:最小路径覆盖数 = 顶点数 - 最大匹配数

​ 选自 : https://www.renfei.org/blog/bipartite-matching.html

模版 :

给定一个二分图 , 其中左半部包含 n1 个点 ( 编号1~n1 ) , 右半部分包含 n2 个点 (编号 1 ~ n2) , 二分图共包含 m 条边. 求出二分图的最大匹配数.

输入样例 :

2 2 4

1 1

1 2

2 1

2 2

输出样例 :

2

代码如下 :

// Huagarian 匈牙利算法 :// hungarian(匈牙利算法) :#include 
#include
#include
using 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) ; } 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 ;}

转载地址:https://blog.csdn.net/weixin_45877540/article/details/109082730 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:图 . 树 . bfs . dfs .
下一篇:质.约数

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月09日 11时46分47秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

c语言 实现sizeof功能,C语言简单实现sizeof功能代码 2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值 2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21
java文档生成_Java文档自动生成 2019-04-21
java 共享目录_java 操作windows 共享目录方法介绍 2019-04-21
java 监控 宕机_JAVA监测tomcat是否宕机,控制重启 2019-04-21
catch that cow java_POJ3278——Catch That Cow 2019-04-21
java integer 不变模式_Java代码的变与不变 2019-04-21
java guava 使用_Java8-Guava实战示例 2019-04-21
python barrier option pricing_《Python金融数据分析》书内代码实战与讲解(二)金融衍生物定价... 2019-04-21