Kruskal与Prim算法实现最小生成树

5星 · 超过95%的资源需积分: 9 184 浏览量更新于2024-07-22 收藏 292KB DOC 举报

"这篇资源是关于ACM算法的集合，主要介绍了如何解决图论问题中的最小生成树问题，包括Kruskal算法和Prim算法。" 在ACM算法竞赛中，数据结构和图论算法是非常重要的部分，其中最小生成树问题是经典问题之一，用于寻找连接所有顶点的边权重之和最小的子集。这里提到了两种常见的解决方法：Kruskal算法和Prim算法。 1. Kruskal算法： Kruskal算法的基本思想是从所有边中选择权重最小的边，并检查这条边是否与已经选择的边形成环。如果不会形成环，就将它添加到结果集中。这个过程一直持续到找到一个连接所有顶点的树。在提供的代码中，首先定义了一个`edg`结构体来存储边的信息（u、v表示两个端点，w表示权重），然后定义了一个比较边权重的`<`操作符用于排序。`uni`函数是判断并查集中的两个元素是否属于同一集合，如果不在同一集合且合并后不会形成环，则返回true。在主函数中，先初始化并查集，然后读入边的信息，对边进行排序，最后按照Kruskal算法的步骤选择边并更新结果。 2. Prim算法： Prim算法则是从一个顶点开始，逐步添加边来扩展树，每次添加的边都是当前未被选中且连接已选节点和未选节点中权重最小的。在给出的代码片段中，Prim算法并没有完整呈现，但可以看到开始的框架，如初始化数组`set`，以及用于存储边的矩阵`g`。完整的Prim算法还需要包含一个循环，每次迭代中找到与当前树相连且权重最小的边，将其加入树中，直到所有顶点都被包含。这两种算法各有优缺点：Kruskal算法需要处理边的排序，适用于边较多的情况；而Prim算法则适合顶点较多的图，因为其每次操作都在顶点之间进行。在实际应用中，根据问题的具体情况，选择合适的算法可以更高效地求解最小生成树。在ACM竞赛中，熟练掌握这些基础算法并能灵活运用，对于解决问题至关重要。同时，了解并优化算法的时间复杂度也是提高解题效率的关键。

ACM 算法资料集锦 2009 年 12 月 10 日星期四

g[u].push_back(v);

}

scc(n,g,set);

int pi=1,ptosc[M];

struct Scc{

int p,n;

}sc[M];

memset(sc,0,sizeof(sc));

for(i=1;i<=n;i++){

int p=findp(set,i);

if(sc[p].p==0) {sc[p].p=pi; ptosc[pi++]=p;}

sc[p].n++;

}

int n2=pi-1,od[M];

memset(od,0,sizeof(od));

for(i=1;i<=n;i++){

for(j=0;j<g[i].size();j++){

u=findp(set,i); v=findp(set,g[i][j]);

if(sc[u].p!=sc[v].p) od[sc[u].p]++;

}

int sum=0,s1=0;

for(i=1;i<=n2;i++) if(od[i]==0) {s1++; sum+=sc[ptosc[i]].n;}

if(s1!=1) sum=0;

cout << sum << endl;

}

最大匹配

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

#define M 1001

int n,m,match[M],ans[M];

bool visit[M],g[M][M];

//O(n^3)

bool dfs(int k,bool map[M][M]){

int t;

for(int i = 1; i <= m; i++){

if(map[k][i] && !visit[i]){

visit[i] = true;

t = match[i];

match[i] = k;

if(t == 0 || dfs(t,map))

return true;

match[i] = t;

}

return false;

}

int main(){

int i,sum=0,t,j,u,v;

cin >> t;

while(t--){

sum=0;

memset(match,0,sizeof(match));

memset(g,0,sizeof(g));

scanf("%d%d",&n,&m);

for(i=1;i<=m;i++){

scanf("%d%d",&u,&v);

g[u][v]=true;

}

m=n;

for(i=1;i<=n; i++){

memset(visit,0,sizeof(visit));

if(dfs(i,g)) sum++;

}

cout << n-sum << endl;

}

return 0;

}

还有两个最大匹配模板

#include <iostream>

#include <string>

#include <math.h>

#include <vector>

using namespace std;

#define M 3001

bool g[M][M];

int mk[M] ,cx[M],pred[M],open[M],cy[M],nx,ny;

//边少适用 O(n^3)

int MaxMatchBFS()

{

int i , u , v , t , d , e , cur , tail , res(0) ;

memset(mk , 0xff , sizeof(mk)) ;

memset(cx , 0xff , sizeof(cx)) ;

memset(cy , 0xff , sizeof(cy)) ;

for (i = 0 ; i < nx ; i++){

pred[i] = -1 ;

for (open[cur = tail = 0] = i ; cur <= tail && cx[i] == -1 ; cur+

+){

ACM 算法资料集锦 2009 年 12 月 10 日星期四

for (u = open[cur] , v = 0 ; v < ny && cx[i] == -1 ; v ++) if (g[u][v]

&& mk[v] != i)

{

mk[v] = i ; open[++tail] = cy[v] ; if (open[tail] >= 0)

{ pred[open[tail]] = u ; continue ; }

for (d = u , e = v ; d != -1 ; t = cx[d] , cx[d] = e , cy[e] = d , e = t ,

d = pred[d]) ;

}

if (cx[i] != -1) res++ ;

}

return res ;

}

int path(int u){

for (int v = 0 ; v < ny ; v++)

if (g[u][v] && !mk[v]){

mk[v] = 1 ;

if (cy[v] == -1 || path(cy[v])) {

cx[u] = v ;

cy[v] = u ;

return 1 ;

}

} return 0 ;

}

//少适用 O(n^3)

int MaxMatchDFS()

{

int res(0) ;

memset(cx , 0xff , sizeof(cx)) ;

memset(cy , 0xff , sizeof(cy)) ;

for (int i = 0 ; i < nx ; i++)

if (cx[i] == -1){

memset(mk , 0 , sizeof(mk));

res += path(i) ;

}

return res ;

}

最大权匹配,KM 算法

//此 KM 算法，坐标从 1 开始，记住

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

#define M 110

int n; // X 的大小

int lx[M], ly[M]; // 标号

bool sx[M], sy[M]; // 是否被搜索过

int match[M]; // Y(i) 与 X(match [i]) 匹配

// 从 X(u) 寻找增广道路，找到则返回 true

bool path(int u,int weight[M][M]) {

sx [u] = true;

for (int v = 0; v < n; v ++)

if (!sy [v] && lx[u] + ly [v] == weight [u] [v]) {

sy [v] = true;

if (match [v] == -1 || path(match [v],weight)) {

match [v] = u;

return true;

}

return false;

}

// 参数 Msum 为 true ，返回最大权匹配，否则最小权匹配

int km(bool Msum,int weight[M][M]) {

int i, j;

if (!Msum) {

for (i = 0; i < n; i ++)

for (j = 0; j < n; j ++)

weight [i] [j] = -weight [i] [j];

}

// 初始化标号

for (i = 0; i < n; i ++) {

lx [i] = -0x1FFFFFFF;

ly [i] = 0;

for (j = 0; j < n; j ++)

if (lx [i] < weight [i] [j])

lx [i] = weight [i] [j];

}

memset(match, -1, sizeof (match));

for (int u = 0; u < n; u ++)

while (1) {

memset(sx, 0, sizeof (sx));

memset(sy, 0, sizeof (sy));

if (path(u,weight))

break;

// 修改标号

int dx = 0x7FFFFFFF;

for (i = 0; i < n; i ++)

if (sx [i])

for (j = 0; j < n; j ++)

if(!sy [j])

剩余25页未读，继续阅读

奔跑的badboy

粉丝: 0
资源: 2

Kruskal与Prim算法实现最小生成树

ACM算法集锦.7z

ACM算法模板集锦.zip

ACM算法自学推荐书目

acm常用java算法,java算法之「字符串反转」noip算法 ACM算法

acm经典c语言算法代码

没学过acm可以搞算法吗

acm常用java算法,

请通过acm分析如何解决主人公的问题

acm竞赛常用算法与数据结构

acm六边形旋转连线通关算法

最新资源