精华内容
下载资源
问答
  • 2021-09-11 14:53:35

    Prim算法和Krusakl算法都是从连通图中寻找最小生成树的算法

    1. Prim算法是直接查找,多次寻找邻边的权重最小值;Kruskal算法采用贪心策略,是需要先对权重排序后查找的。
    2. Kruskal算法在效率上比Prim算法快,因为Krusal算法只要对所有边排序一次就能找到最小生成树;而Prim算法需要对邻边进行多次排序才能找到。
    3. Prim算法:选择一个顶点作为树的根节点,然后找到以这个点为邻边的最小权重的点,然后将其加入最小生成树中,再重复查找这棵最小生成树的权重最小的边的点,加入其中。(如果加入要产生回路,就跳过这条边)。当所有结点加入最小生成树中,就找到了这个连通图的最小生成树。
    4. Kruskal算法:利用贪心策略,再找最小生成树结点之前,需要对边的权重从小到大排序,将排序好的权重边依次加入到最小生成树中(如果加入时产生回路就跳过这条边,加入下一条边),当加入的边数为n-1时,就找到了这个连通图的最小生成树。
    5. Prim算法适合边稠密图,时间复杂度O(n²)
    6. Kruskal算法与边有关,适合于稀疏图O(eloge)
    更多相关内容
  • 重点掌握:最小生成树(Prim算法和Kruskal算法)、单源最短路径(Dijkstra算法)。 编程实现最小生成树(Prim算法和Kruskal算法)、单源最短路径(Dijkstra算法)代码。
  • 【贪心】Prim和Kruskal算法区别 Kruskal算法和Prim算法的优劣 Kruskal算法,相较于Prim算法是基于点的操作,Kruskal算法是基于边的操作,思想也比Prim简单,更容易理解 Prim算法是采用从点方面考虑来构建MST...

    【贪心】Prim和Kruskal算法的区别

    Kruskal算法和Prim算法的优劣

    Kruskal算法,相较于Prim算法是基于点的操作,Kruskal算法是基于边的操作,思想也比Prim简单,更容易理解

    Prim算法是采用从点方面考虑来构建MST的一种算法,Prim 算法在稠密图中比Kruskal优。

    示例

    Prim算法

    1. 从源点出发,把源点所有的边加入一个集合(称为待选边集合E{} 图1
    2. E{}中选出最短边,连接并移除,并将该点的所有的边加入E{}       图2
    3. 不断重复此步骤,如果遇到边已连接,则跳过此边并从E{}移除。

    步骤图

     

     

     

    1.

    2.

    3.

    4.

    5.

    6.

    7.

    Kruskal算法

    与Prim算法不同的是,

    1. 先将所有的边排序
    2. 连接并移除当前最短边,不断重复
    3. 如果步骤2遇到边的连接会形成环形,则跳过此边并移除。 如图5

    步骤图

     

     

     

    1.

    2.

    3.

    4.

    5.

    6.

    7.

    展开全文
  • Prim算法与Kruskal算法都是用来求连通网的最小生成树问题的方法。首先让我们来创设一个情景: 某营业厅接到一个单子,要求给一所学校新建校区安装宽带 该学校教学楼、宿舍分别用(A, B, C, D, E, F, G)来代表 ...

    Prim算法与Kruskal算法都是用来求连通网的最小生成树问题的方法。首先让我们来创设一个情景:

    • 某营业厅接到一个单子,要求给一所学校新建校区安装宽带
    • 该学校教学楼、宿舍分别用(A, B, C, D, E, F, G)来代表
    • 问:如何修路保证各个站点都能连通,并且线路最短
      在这里插入图片描述

    Prim算法

    1).输入:一个加权连通图,其中顶点集合为V,边集合为E;
    2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;
    3).重复下列操作,直到Vnew = V:
    	a.在集合E中选取权值最小的边<u, v>,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
    	b.将v加入集合Vnew中,将<u, v>边加入集合Enew中;
    4).输出:使用集合Vnew和Enew来描述所得到的最小生成树。
    

    以上是来自百度百科对Prim的描述,那他到底是怎么执行的呢,我们看看流程图

    • 首先我们确定一根节点,然后从此节点出发,利用贪心算法寻找权值最小的边。逐步扩大所含顶点的数目,直到遍及连通图的所有顶点。

    • 这里我们选取A点为起始点,那么Prim的流程就如下图所示在这里插入图片描述

    • 最后黄色所连成的树就是Prim算法的最小生成树

    Kruskal算法

    百度百科中对Kruskal是这样描述的:

    克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树

    • 其基本思想是:假设连通网G=(V,E),令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),概述图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点分别在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止
    • 流程如下在这里插入图片描述

    Prim算法与Kruskal算法比较

    Prim算法的核心步骤是增加点,针对点考察边,与网中的边数无关,因此适合求解稠密图最小生成树。Kruskal算法是针对一条边的扫描和排序,借助“堆”存放。

    算法名普利姆算法克鲁斯卡尔算法
    基本思想顶点为对象为对象
    时间复杂度O(n²)O(eloge)
    适应范围稠密图稀疏图

    Prim算法实现

    pass

    Kruskal算法实现

    pass

    展开全文
  • 图论算法:最小生成树——Prim算法和Kruskal算法C 实现
  • PrimKruskal算法的最小生成树matlab实现
  • 文章目录最小生成树实现约定原理Prim算法过的洛谷板子题P3366 约定 只考虑连通图。 边的权重可以为负数或者是0。 原理 用一条边连接树中的任意的两个顶点都会产生一个新的环。 从树中删去一条边会得到两个独立的树。...

    最小生成树实现

    约定

    只考虑连通图。

    边的权重可以为负数或者是0。

    原理

    用一条边连接树中的任意的两个顶点都会产生一个新的环。

    从树中删去一条边会得到两个独立的树。

    切分:图的一种切分是将图中所有的顶点分为两个非空且不重叠的两个集合。

    横切:便是一条连接两个属于不同集合的顶点的边。

    切分定理:在一幅加权图中,给定任意的切分,它的横切边中的最小权重者必然属于图中的最小生成树。

    在假设所有的边的权重均不相同的情况下,每一幅连通图都只有一颗唯一的最小生成树。

    切分定理表明对于每一种的切分,权重最小的横切边必然属于最小生成树。

    贪心:切分定理是解决最小生成树的基础。

    Prim算法

    在这里只需要存边,不管结点的事。或许换句话说,就是现在边才是“上司”,谁还管小职员呢
    主要是通过三步筛选得到一个关于选择的最小生成树的边集add_e。

    #include <bits/stdc++.h>
    using namespace std;
    
    struct Edge {
    	int u;
    	int v;   //与该边相连的两个结点
    	double w;//该边的权值
    	
    	bool operator<(const Edge&a)const{
    		return w>a.w;
    	}
    };
    
    int node, edge;
    int vis[100000] = {0}; //结点数组,查看是否走过
    //三步筛选
    vector<Edge>all_e;//存全部的边
    priority_queue<Edge>vis_e;//这个是最小生成树的"candidates"
    queue<Edge>add_e;//对于已经加入最小生成树中的边是不动的
    
    void Visit() {
    	cout << "共有多少结点?";
    	cin >> node;
    	cout << endl << "共有多少边?";
    	cin >> edge;
    
    	for (int i = 0; i < edge; i++) {
    		Edge a;
    		//输入格式为:起点-终点-权值
    		cin >> a.u >> a.v >> a.w;
    		all_e.push_back(a);
    	}
    }
    
    void add(int start) { //把与该结点有关的边全部加入优先队列
    	vis[start] = 1;
    	for (int i = 0; i < all_e.size(); i++) {
    		if (all_e[i].u == start || all_e[i].v == start)vis_e.push(all_e[i]);
    	}
    }
    
    void Prim(int start) { //起始节点
    	add(start);
    	while (!vis_e.empty()) {
    		Edge a = vis_e.top();
    		vis_e.pop();
    		if (vis[a.u] && vis[a.v])continue;//说明会构成环
    		else add_e.push(a);//不然就加入最小生成树
    		if (!vis[a.u]) add(a.u);//把另外一个结点相连的所有边加入候选人
    		if (!vis[a.v]) add(a.v);
    	}
    }
    
    void Show() { //已经得到了最小生成树的所有边,输出
    	while (!add_e.empty()) {
    		Edge a = add_e.front();
    		add_e.pop();
    		cout << a.u << " " << a.v << " " << a.w << endl;
    	}
    }
    
    int main() {
    	int s;
    	Visit();//获得所有存在的边
    	cout << "选定开始的起点:";
    	cin >> s;
    	Prim(s);
    	Show();
    	return 0;
    }
    

    过的洛谷板子题P3366

    上述的并不能直接套到这个题里面,然后还T了8 9 10三个点。
    需要进行一些优化。
    显然,需要进行一个大修的操作。【已经修改完毕】
    结论:基本上是和原来的代码完全不同了。使用了链式前向星+堆优化。(是一个类似Dijkstra算法算最短路径的操作)

    #include <bits/stdc++.h>
    using namespace std;
    const int INF = 2147483647; //2^31-1
    const int MAXN = 6000006;
    
    struct Edge {
    	int to;//终点
    	int w;//权值
    	int next;//实际上是上一点
    };
    
    struct Node {
    	int node;//编号
    	int cost;
    
    	bool operator<(const Node &a)const {
    		return cost > a.cost;
    	}
    };
    
    int node, edge, cnt = 1;
    int vis[100000] = {0}; //结点数组
    Edge edgeTo[MAXN];//与父节点
    int head[MAXN];
    int dis[MAXN];//得到父节点到其他点的最短路径
    
    void init() {
    	for (int i = 0; i < node; i++)head[i] = -1;
    }
    
    void add(int from, int to, int w) {
    	edgeTo[cnt].to = to;
    	edgeTo[cnt].w = w;
    	edgeTo[cnt].next = head[from]; //起始:next=-1;类似头插法,指针操作
    	head[from] = cnt++; //起点的第一条边指向cnt
    }
    
    void Visit() {
    	int u, v, w;
    	init();
    	cin >> node >> edge;
    
    	for (int i = 0; i < edge; i++) {
    		//输入格式为:起点-终点-权值
    		cin >> u >> v >> w;
    		add(u, v, w);
    		add(v, u, w);
    	}
    }
    
    int Prim(int start) { //起始节点
    	for (int i = 1; i <= node; i++)dis[i] = INF;//初始化
    	dis[start] = 0;
    	int cnt_node = 0, sum = 0;
    
    	priority_queue<Node>q;
    	q.push(Node{start, 0});
    	while (!q.empty()) {
    		int u = q.top().node;
    		q.pop();
    		if (!vis[u]) {
    			vis[u] = 1;
    			cnt_node++;
    			sum += dis[u];
    			dis[u] = 0; //并入集合内部,因此dis=0
    			for (int i = head[u]; i; i = edgeTo[i].next) {
    				int &t = edgeTo[i].to;
    				if (!vis[t] && dis[t] > dis[u] + edgeTo[i].w) {
    					dis[t] = dis[u] + edgeTo[i].w;
    					q.push(Node{t, dis[t]});
    				}
    			}
    		}
    	}
    	if (cnt_node < node)sum = -1;
    	return sum;
    }
    
    int main() {
    	int s, sum = 0;
    	Visit();//获得所有存在的边
    	int n = Prim(1);
    	if (n == -1)cout << "orz";
    	else cout << n;
    	return 0;
    }
    

    Kruskal算法

    需要使用一个并查集的操作。
    并查集的数据结构如下:

    #include <iostream>
    using namespace std;
    const int maxn = 1e5;
    int father[maxn];
    
    void Init() {
    	for (int i = 1; i < maxn; i++) father[i] = i
    }
    
    void Union(const int &u, const int &v) { //联合
    	father[Find(u)] = Find(v); //v的最老祖宗的爹是u的最老祖宗的爹
    }
    
    int Find(const int &u) { //查找u的祖宗是谁
    	if (u == father[u])return u;
    	return father[u] = Find(father[u]); //扁平化
    }
    
    int main() {
    	Init();
    	return 0;
    }
    

    【Kruskal】

    #include <iostream>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    struct Edge {
    	int u;//起点
    	int v;//终点
    	int w;//权值
    
    	bool operator<(const Edge &a)const {
    		return w > a.w;
    	}
    };
    
    int node, edge; //总结点数以及边数
    priority_queue<Edge> all_e;//存放所有的边
    queue<Edge> vis_e;//加入最小生成树的所有的边
    const int maxn = 1e5;
    int father[maxn];
    
    void Init() {
    	for (int i = 1; i < maxn; i++) father[i] = i;
    }
    
    int Find(const int &u) { //查找u的祖宗是谁
    	if (u == father[u])return u;
    	return father[u] = Find(father[u]); //扁平化
    }
    
    void Union(const int &u, const int &v) { //联合
    	father[Find(u)] = Find(v); //v的最老祖宗的爹是u的最老祖宗的爹
    }
    
    void Visit() {
    	cout << "【请输入结点数以及边数】:" << endl;
    	cin >> node >> edge;
    	cout << "【请按照 起点-终点-权值 的格式输入边】:" << endl;
    	for (int i = 0; i < edge; i++) {
    		Edge a;
    		cin >> a.u >> a.v >> a.w;
    		all_e.push(a);
    	}
    }
    
    int Kruskal() {
    	int n_edge = 0, sum = 0;
    	while (!all_e.empty()) {
    		Edge a = all_e.top();
    		all_e.pop();
    		if (Find(a.u) != Find(a.v)) { //就加入这条边
    			Union(a.u, a.v);
    			vis_e.push(a);
    			sum += a.w;
    			n_edge++;
    		}
    	}
    	if (n_edge < node - 1)sum = -1;
    	return sum;
    }
    
    void Show() {
    	while (!vis_e.empty()) {
    		Edge a = vis_e.front();
    		vis_e.pop();
    		cout << a.u << " " << a.v << " " << a.w << endl;
    	}
    }
    
    int main() {
    	Init();
    	Visit();
    	cout << "===========" << endl;
    	int n=Kruskal();
    	if(n==-1)cout<<"此图不连通"<<endl;
    	else {
    		cout<<n<<endl;
    		Show();
    	}
    	return 0;
    }
    

    这个稍作修改就可以ACP3366了。。。

    展开全文
  • 之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法。 一、权重图最小生成树 权重图:图的边带权重 最小生成树:在连通图的所有生成树中,所有边的权重...
  • 宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构——优先级队列,用于动态排序。由于这两个算法很容易理解,在此不再赘述。接下来给出我的源代码。 ...
  • prim算法和kruskal算法

    2021-03-13 22:18:08
    prim算法和kruskal算法 1.问题 对于如何生成最小生成树,目前有Prim算法和Kruskal算法Prim算法是从结点出发,寻找距离原结点最短的结点,直至将所有结点都找到为止;Kruskal算法是从边出发,先找最短的边,在不...
  • Kruskal算法&Prim算法的区别

    千次阅读 2021-11-17 10:52:06
    Prim算法区别: 贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。 贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优...
  • prim是根据访问过的结点来更新当前可以加入的最小边 kruskal是把所有边排序,然后一条条边加入,需要防止形成环 本程序使用接邻矩阵保存图,测试用例如下图: #pragma once #include #include #include using namespace ...
  • MST Prim Kruskal 算法的 Java 实现,用于查找图的最小生成树
  • 最小生成树——Prim和Kruskal算法

    千次阅读 2022-03-13 17:47:52
    Kruskal算法总结 简介 求最小生成树的目的: 最常见的便是,在多个途经点中计划出一条最快捷的路线。 求最小生成树的两种算法: 普利姆算法 Prim 克鲁斯卡尔算法 Kruskal 二者主要区别在于: Prim通过遍历图的...
  • 边的权重值之最小 结论:只要图是连通的,则存在最小生成树,同理,只要有最小生成树,图就连通。 核心算法思路:贪心 贪心算法的约束条件: 只能用图里有的边 只能正好用电V-1条边 不能有回路 ...
  • 详细的c语言实现最小生成树的prim算法和kruskal算法,非常有用的
  • prim算法和Kruskal算法

    2021-12-26 18:46:31
    代码实现二、Kruskal算法1.基本介绍2.应用场景3.代码实现 一、prim算法 1.基本介绍 普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极...
  • Prim算法和Kruskal算法的Matlab实现
  • Prim和Kruskal算法构造最小生成树 1.问题 (1)举一个实例,画出采用Prim算法构造最小生成树的过程,并按实验报告模板编写算法。 (2)举一个实例,画出采用Kruskal算法构造最小生成树的过程,并按实验报告模板...
  • c++最小生成树两种方法: Prim算法 Kruskal算法 Prim算法: 算法思想: 假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作: 在所有u∈U,v∈V-U的边...
  • 最小生成树——Prim算法和Kruskal算法 一、prim算法解析 以上图为例。 prim算法从任意顶点开始,每次都找到一个距离顶点集中距离最近的一个点,将其加入到顶点集,并把两点间的边加入到树中。直到访问完所有点,...
  • 最小生成树—prim和kruskal算法 一般Kruskal用的比prim多,因为prim可以解决的,kruskal一定可以解决,反过来就不一定了。 prim算法 prim 算法采用的是一种贪心的策略。 每次将离连通部分的最近的点点对应的边加入...
  • prim 和kruskal 算法分析课程设计.doc
  • Prim算法和Kruskal算法都是基于最小生成树的MST性质的贪心策略。只是两者处理的对象不一样,一个是从点出发,一个是从边出发。 Prim算法 设源点为v1,初始时U={v1},假设补集V-U={v2,v3,v4,v5,v6}。 第一次...
  • prim算法和kruskal算法详解

    千次阅读 2019-10-22 11:49:09
    prim算法和kruskal算法详解。下面笔者将与大家共同探讨一下这两个经典的算法他们的C++代码实现。 首先我们先看引自百度百科的prim算法的定义:普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索...
  • 最小生成树 定义 生成树:连通图包含全部顶点的一个极小连通子图 最小生成树:对于带权无向连通图 G=(V, E),G的所有生成...Prim 算法适用于稠密图,Kruskal算法适用于稀疏图 Prim 算法 初始化:向空的结果树 T=(VT,ET
  • 最小生成树经典算法Matlab实现
  • 本次要说的是Prim算法(普里姆算法) kruskal算法(克鲁斯卡尔算法),两者都是求最小生成树 最小生成树什么? (1)定义 最小生成树: 一个有n个结点的连通图的生成树是原图的最小连通图,且包含原图的所有n个...
  • 一般求最小生成树有Prim和Kruskal算法 一.prim算法 此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。 1. 图的所有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,740
精华内容 6,696
关键字:

prim和kruskal算法区别

友情链接: nslist.rar