用prim算法和Kruskal算法求最小生成树,不要原代码要过程.

以逝2022-10-04 11:39:541条回答

已提交，审核后显示！提交回复

at305091777 共回答了13个问题 | 采纳率76.9%: V: {1,2,3,4,5,6,7}
E: {a:(1,2):50, b:(1,3):60,
c:(2,4):65, d:(2,5):40,
e:(3,4):52, f:(3,7):45,
g:(4,5):50, h:(4,6):30, i:(4,7):42,
j:(5,6):70}kruskal0: V={{1},{2},{3},{4},{5},{6},{7}}, E={},
pick 1st from {h,d,i,f,a,g,e,b,c,j}
1: V={{1},{2},{3},{4,6},{5},{7}}, E={h},
pick 1st from {d,i,f,a,g,e,b,c,j}
2: V={{1},{2,5},{3},{4,6},{7}}, E={h,d},
pick 1st from {i,f,a,g,e,b,c,j}
3: V={{1},{2,5},{3},{4,6,7}}, E={h,d,i},
pick 1st from {f,a,g,e,b,c,j}
4: V={{1},{2,5},{3,4,6,7}}, E={h,d,i,f},
pick 1st from {a,g,b,c,j}
5: V={{1,2,5},{3,4,6,7}}, E={h,d,i,f,a},
pick 1st from {g,b,c,j}
6: V={{1,2,5,3,4,6,7}}, E={h,d,i,f,a,g}, pick 1st from {}
#: final V={1,2,5,3,4,6,7}, E={h,d,i,f,a,g}primVstart = 1
0: V={1}, E={}, pick 1st from {a,b}
1: V={1,2}, E={a}, pick 1st from {d,b,c}
2: V={1,2,5}, E={a,d}, pick 1st from {g,b,c,j}
3: V={1,2,5,4}, E={a,d,g}, pick 1st from {h,i,e,b}
4: V={1,2,5,4,6}, E={a,d,g,h}, pick 1st from {i,e,b}
5: V={1,2,5,4,6,7}, E={a,d,g,h,i}, pick 1st from {e,b}
6: V={1,2,5,4,6,7,3}, E={a,d,g,h,i,e}.; 1年前

求带权图的最小生成树一、实验目的熟练理解求最小生成的Prim算法；锻炼程序设计能力.二、实验内容编程实现求无向带权图的最 求带权图的最小生成树 一、实验目的 熟练理解求最小生成的Prim算法； 锻炼程序设计能力. 二、实验内容 编程实现求无向带权图的最小生成树. 三、实验原理、方法和手段 设图G =（V,E）,其生成树的顶点集合为U. ①、把v0放入U. ②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树. ③、把②找到的边的v加入U集合.如果U集合已有n个元素,则结束,否则继续执行②. 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求. 五、实验条件 每人一台计算机独立完成实验,如下条件： （1）硬件：微机； （2）软件：VC++6.0、VC++.Net. 六、实验步骤 （1）编写生成一个邻接矩阵表示的无向带权图的函数. （2）编写Prim函数； （3）在主函数中调用上述函数,并将结果中所有的边输出.输出边的格式为：i,j,w.其中i和j为该边关联的点的下标,w为该边权值. 七、实验报告 实验报告主要包括实验预习、实验说明、程序代码、实验结果及分析等内容. 别说什么1年前1: 逝去的记忆闹共回答了12个问题 | 采纳率91.7%

某是秦XX老师,请认真上机完成!

1年前查看全部

用prim算法从下面图中的顶点1开始逐步构造最小代价生成树 ZYH200208031年前0: 共回答了个问题 | 采纳率

查看全部

数据结构（prim算法）如图示,以V1为起始点,上述算法在确定了V1,V32个节点之后,寻找最短路径.ee数组（最小距离 数据结构（prim算法） 如图示,以V1为起始点,上述算法在确定了V1,V32个节点之后,寻找最短路径. ee数组（最小距离数组）中的值为0 6 0 5 无穷无穷 for(j = 0;j < G.vexnum;j++)循环中将V3邻接到个点的距离与ee数组比较,在与V2点比较时将出发点改称V3,可是 V1到V4的距离 < V3到V4的距离,接下去连接的边应该是V1到V4的边啊. 不理解 补充 (I)类型定义 typedef char VexType; /*顶点数据类型*/ typedef int EdgeType;/*边数据类型*/ typedef struct { VexType vexs[VexNum]; EdgeTypearcs[VexNum][VexNum]; int vexnum,arcnum; /* 顶点数和边数 */ }Mgraph; /* 图的邻接矩阵表示结构定义 */ typedef struct {int adjvex;/*集合U中的顶点(始点)*/ int value;/*集合u中顶点到非U中的某个顶点的最小距离值*/ }InterEdge; ducky_happy1年前1: 下雨的雨人共回答了15个问题 | 采纳率80%

开始时将v1加入U后,更新ee中的值应该是0 6 1 2 无穷无穷；
将v3加入U后,更新ee中的值应该是0 5 0 2 6 4；
怎么会出现你说的0 6 0 5 无穷无穷的情况呢?
for(j = 0;j < G.vexnum;j++)中不是有条件判断么,要在k到j的距离小于ee[j]的value值时才会更新ee[j]啊.

1年前查看全部

如图所示为一个无向带权图,请分别按照Prim算法和Kruskal算法求最小生成树 一朵蔷薇花1年前1: 波波的MM 共回答了18个问题 | 采纳率88.9%

按照prim是：（从起点到终点的边）
46,45,51,63,12,32
按照kruskal是：
46,15,45,63,12,32

1年前查看全部

prim算法和kruskal 算法哪个好 testonly4u1年前1: cbl-wy 共回答了16个问题 | 采纳率93.8%

Kruskal算法适用于边稀疏的情形,而Prim算法适用于边稠密的情形

1年前查看全部

根据Prim算法,求图示的最小代价生成树.设①为起点,要求画出构造过程. windxier1年前1: 兜里只有9毛3 共回答了14个问题 | 采纳率85.7%

　　#include 　　#include 　　using namespace std;　　#define MAX_VERTEX_NUM 10 //最大顶点个数　　#define INFINITY 1000 //定义最大值为1000　　typedef char VerType;//定点向量　　typedef int V...

1年前查看全部

如果在一个无向图中遇到两点到同一点的的权值一样,用prim算法在生成最小树的时候,怎么办 如果在一个无向图中遇到两点到同一点的的权值一样,用prim算法在生成最小树的时候,怎么办 z 孤桐迎风1年前1: 轻飘仙子共回答了15个问题 | 采纳率93.3%

只要加入权值最小的点就好了,如果两点同时最小,就先加两点中的任意一点,或两点都加

1年前查看全部

13.用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树是否相同? 一夫多妻1年前1: pplroy 共回答了14个问题 | 采纳率92.9%

如果原来的图里面任何两条边长都不相同,那么最小生成树是唯一的,此时不管用什么方法算出来的都是一样的
但是如果图里有相等的边,那么最小生成树可能会不唯一,这样就无法保证不同的方法得到同一棵树（即使是同一个算法,只要图的编号方式改变也可能得到不同的最小生成树）

1年前查看全部

根据Prim算法求出图的最小生成树(给出生成过程). 根据Prim算法求出图的最小生成树(给出生成过程). 已知图G的邻接矩阵A= lsun0261年前1: 狂饮倭寇血共回答了13个问题 | 采纳率92.3%

Floyd算法的Matlab程序如下：
clear;clc;
n=5; a=zeros(n);
a(1,2)=1;a(1,3)=12;a(1,4)=6;a(1,5)=10;
a(2,3)=8;a(2,4)=9;
a(3,5)=2;
a(4,5)=4;
a=a+a';M=max(max(a))*n^2; %M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
ifa(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
a,path
Matlab输出结果：
a =
0 1 9 6 10
1 0 8 7 10
9 8 0 6 2
6 7 6 0 4
10 10 2 4 0
path =
0 0 2 0 0
0 0 0 1 3
2 0 0 5 0
0 1 5 0 0
0 3 0 0 0

1年前查看全部

设某带权无向图如下图,画出用Prim算法,从顶点A开始生成最小生成树的每一步结果. rexysy141年前1: 悠悠睡共回答了18个问题 | 采纳率83.3%

和你文字描述好了,你自己画出来
第一步连AE
第二步连EG
GC
GF
AD
BD

1年前查看全部

数据结构,选什么,下面（　）算法适合构造一个稠密图G的最小生成树.A． Prim算法 B．Kruskal算法 C．Flo 数据结构,选什么, 下面（　）算法适合构造一个稠密图G的最小生成树. A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法 mjm_zhy1年前1: cctv2_win 共回答了18个问题 | 采纳率94.4%

B．Kruskal算法

1年前查看全部

prim算法构造出的最小生成树唯一吗?prim算法和kruskal算法构造出的最小生成树一样吗? xiyufeilong1年前1: covadis 共回答了15个问题 | 采纳率93.3%

不唯一,两种算法构造出的最小生成不一定相同.

1年前查看全部

无权无向图,只给出节点个数,怎么用Prim算法求最小生成树 歪歪gg1年前1: carlyle 共回答了17个问题 | 采纳率76.5%

Prim算法的主要运行时间花在过程②的选边中.看起来复杂度是O(VE)=O(V^3)不是么,效率也太低了吧……

为了比较快速地选边,我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离.在某一状态下,lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值,closest[i]表示在S中且与i相连的点中与i之间距离最小的点.显然,lowcost[i]=w(i,closest[i]).需要注意的是两个数组记录的都是边而不是路径.若i没有边直接连向S,则lowcost[i]=∞.另外,若i已在S中,则lowcost[i]=0.

设出发点为x.初始时对于任意k∈V,closest[k]=x,lowcost[k]=w（k,x）【w（i,j）表示i、j间的距离.初始化时,若两点间没有边则w（i,j）赋为一个足够大的整数（如maxint）,并且所有点到自身的距离赋为0,即w（i,i）=0】

每一次找出lowcost中不为0的最小值lowcost[i],然后把i加入S（即lowcost[i]:=0）,然后对于图中所有点k,若w(k,i)

1年前查看全部

用prim算法和Kruskal算法求最小生成树,不要原代码要过程.

共1条回复

相关推荐

大家在问