用prim和kruskal算法求最小生成树问题

这篇具有很好参考价值的文章主要介绍了用prim和kruskal算法求最小生成树问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最短网络

题目http://ybt.ssoier.cn:8088/problem_show.php?pid=1350

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N][N];
bool st[N];
int dist[N];
int n,res=0;
void prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;//初始化第一个点到自己的距离为0
    for(int i=1;i<=n;i++)//找剩下的n个点与第一起点的距离,就像dijkstra一样
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//找不在连通块且距离最小的点
                 t=j;
        st[t]=true;//标记这个点在连通块内
        res+=dist[t];
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);//用该点更新其他点的最短距离
    }
}
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
         cin>>w[i][j];
   prim();
   cout<<res<<endl;
	return 0;
}

2.局域网

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid=1391

相当于一个图中求最小生成树的问题

prim解决

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N][N];
bool st[N];
int dist[N];
int n,res=0,m;
void prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;//初始化第一个点到自己的距离为0
    for(int i=1;i<=n;i++)//找剩下的n个点与第一起点的距离,就像dijkstra一样
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//找不在连通块且距离最小的点
                 t=j;
        st[t]=true;//标记这个点在连通块内
        res+=dist[t];
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);//用该点更新其他点的最短距离
    }
}
int main()
{
    int ans=0;
   cin>>n>>m;
   memset(w,0x3f,sizeof w);
   while(m--)
   {
      int a,b,c;
      cin>>a>>b>>c;
      w[a][b]=w[b][a]=min(w[a][b],c);
      ans+=w[a][b];//记录所有网线的答案
   }
   prim();
   cout<<ans-res<<endl;//输出总的减最小生成数的
	return 0;
}

kruskal解法

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=N*N;
int n,m;
struct Edge
{
    int a,b,w;
    bool operator < (const Edge&t)const//重载小于号,待会排序就按照w排序
    {
        return w<t.w;
    }
}e[M];//结构体存数
int p[N];
int find(int x)//并查集
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
   int ans=0;
   cin>>n>>m;
   for(int i=1;i<=n;i++) p[i]=i;//并查集初始化
   for(int i=0;i<m;i++)
   {
       int a,b,w;
       cin>>a>>b>>w;
       e[i]={a,b,w};
   }
   sort(e,e+m);//先排序
   for(int i=0;i<m;i++)
   {
       int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
       if(a!=b) p[a]=b;//假如不在一个集合,则加上该条边
       else ans+=w;//反之该条边就是多余不要的加上答案里
   }
   cout<<ans<<endl;//输出总的减最小生成数的
	return 0;
}

3.繁忙的都市

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid=1392

#include<bits/stdc++.h>
using namespace std;
const int N=310,M=N*N;
struct edge
{
	int a,b,c;
	bool operator < (const edge &t)const
	{
		return c<t.c;
	}
}e[M];
int n,m;
int p[N];
int res,maxx;
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[i]={a,b,c};
	}
	sort(e,e+m);
	for(int i=0;i<m;i++)
	{
		int a=find(e[i].a),b=find(e[i].b),c=e[i].c;
		if(a!=b)
		{
			p[a]=b;
			res++;
			maxx=c;
		}
	}
	cout<<res<<" "<<maxx;
}

4.联络员

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid=1393

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=N*N;
struct Edge
{
	int a,b,w;
	bool operator< (const Edge& t)
	{
		return w<t.w;
	}
}e[M];
int p[N];
int n,m;
int res;
int cnt;
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=0;i<m;i++)
	{
		int k,a,b,c;
		cin>>k>>a>>b>>c;
		if(k&1)
		{
			res+=c;
			p[find(a)]=find(b);
		}
		else 
		e[cnt++]={a,b,c};
	}
	sort(e,e+m);
	for(int i=0;i<m;i++)
	{
		int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
		if(a!=b)
		{
			p[a]=b;
			res+=w;
		}
	}
	cout<<res<<endl;
}

5.连接格点

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)http://ybt.ssoier.cn:8088/problem_show.php?pid=1394

就是给你已经连接了的点,让你加上某些边使他连通,也就是最小生成树,但是不能用prim,可能给出的边有环,只能用kruskal文章来源地址https://www.toymoban.com/news/detail-493349.html

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N,K=2*M;
struct Edge
{
	int a,b,w;	
}e[K];
int p[M];
int id[N][N];
int n,m,cnt;

int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
void edge()
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},dw[4]={1,2,1,2};
    for(int s=0;s<2;s++)//s表示余数,0表示打横走,1表示纵着走
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
             for(int u=0;u<4;u++)
                if(u%2==s)//走的途径
               {
                    int x=i+dx[u],y=j+dy[u],w=dw[u];
                    if(x<=0||x>n||y<=0||y>m) continue;//假如越界
                    int a=id[i][j],b=id[x][y];//获取当前位置
                    if(a<b) e[cnt++]={a,b,w};//为了避免重复假如
               }
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n*m;i++)p[i]=i;
	for(int i=1,t=1;i<=n;i++)
	for(int j=1;j<=m;j++,t++)//映射坐标为点
	id[i][j]=t;
	int x1,x2,y1,y2;
	while(cin>>x1>>y1>>x2>>y2)
	{
		int a=id[x1][y1],b=id[x2][y2];
		p[find(a)]=find(b);//假如是连通块了,则加到同个连通块
	}
	edge();
	int res=0;
	for(int i=0;i<cnt;i++)
	{
		int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
		if(a!=b)
		{
			p[a]=b;
			res+=w;
		}
	}
	cout<<res;
 } 

到了这里,关于用prim和kruskal算法求最小生成树问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(50)
  • 最小生成树Kruskal、Prim算法C++

    连通图: 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1和顶点v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。 生成树: 一个连通图的最小连通子图称作为图的生成树。有 n个顶点 的连通图的生成树有 n个顶点和 n-1 条边。 最小生成树: 最小生活

    2024年02月10日
    浏览(41)
  • 【最小生成树】一文学懂prim、kruskal算法

    博主简介: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: 算法 ;该专栏专注于蓝桥杯和ACM等算法竞赛🔥 近期目标: 写好专栏的每一篇文章 首先,我们要了解什么是最小生

    2023年04月25日
    浏览(32)
  • C语言实现最小生成树算法:Prim和Kruskal

    以下是使用C语言实现Prim算法生成最小生成树的代码: 注释如下: #include stdio.h 和 `#include #define V 5 定义了图中顶点的个数为5。 int minDistance(int dist[], int visited[]) 函数用于找到顶点集合中未访问的顶点中距离最小的顶点。输入参数 dist 用于存储顶点到最小生成树的距离,输入

    2024年02月03日
    浏览(42)
  • 【算法基础:搜索与图论】3.5 求最小生成树算法(Prim&Kruskal)

    最小生成树 有关树的定义 生成子图 :生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。 生成树 :一个连通 无向图 的 生成子图 ,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。 我们

    2024年02月16日
    浏览(40)
  • 求最小生成树Prim(普里姆)和Kruskal(克鲁斯卡尔)算法

     想求最小生成树,我们首先得弄懂以下几个概念   连通图 :图中任意两个顶点都是连通的 极小连通子图 :既要保持图连通又要使得边数最少的子图 生成树 : 包含图中全部顶点的一个极小连通子图 连通图用通俗的话来讲就是,某一个顶点,可以 直接或者间接 (通过其他顶点

    2024年02月05日
    浏览(46)
  • 【数据结构与算法】最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

      🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 一、最小生成树的概念 二、最小生成树的求解方法 三、练习题 四、最小生成树在实际应用中的例子 最近非科班的同学学到了最小生成树并询问我,于是想趁

    2024年02月07日
    浏览(42)
  • 使用邻接矩阵实现最小生成树Prim算法 题目编号:1135

    用邻接矩阵存储无向图,实现最小生成树Prim算法,图中边的权值为整型,顶点个数少于10个。 部分代码提示: #include using namespace std; const int MaxSize = 10; const int INF = 32767; class MGraph { public: MGraph(char a[], int n, int e); private: char vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }

    2024年02月06日
    浏览(40)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(52)
  • 【刷题】图论——最小生成树:Prim、Kruskal【模板】

    假设有n个点m条边。 Prim适用于邻接矩阵存的稠密图,时间复杂度是 O ( n 2 ) O(n^2) O ( n 2 ) ,可用堆优化成 O ( n l o g n ) O(nlogn) O ( n l o g n ) 。 Kruskal适用于稀疏图,n个点m条边,时间复杂度是 m l o g ( m ) mlog(m) m l o g ( m ) 。 Prim:遍历n次,每次选择 连通块和外面的点 到连通块距离

    2024年04月13日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包