导航:首页 > 源码编译 > 普里姆算法适合构造稠密图
普里姆算法适合构造稠密图
发布时间：2025-09-01 11:42:38❶ 普里姆算法的普里姆算法的实现
为了便于在两个顶点集U和V-U之间选择权最小的边，建立了两个辅助数组closest和lowcost，它们记录从U到V-U具有最小权值的边，对于某个j∈V-U，closest[j]存储该边依附的在U中的顶点编号，lowcost[j]存储该边的权值。
为了方便，假设图G采用邻接矩阵g存储，对应的Prim(g,v)算法如下：
void Prim(MatGraph g,int v) //输出求得的最小生树的所有边
{ int lowcost[MAXVEX]; //建立数组lowcost
int closest[MAXVEX]; //建立数组closest
int min,i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //构造n-1条边
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k为最近顶点的编号
}
printf( 边(%d,%d),权值为%d
,closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.n;j++) //修正数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆算法中有两重for循环，所以时间复杂度为O(n2)，其中n为图的顶点个数。由于与e无关，所以普里姆算法特别适合于稠密图求最小生成树。
与普里姆算法适合构造稠密图相关的资料
- 预编译获得元数据
- 安卓编译平台搭建
- vs2017自动编译
- p2p网站源码免费
- h5网站源码怎么传服务器
- 背包问题近似算法
- 许昌提供短视频app源码
- 八减七手指算法
- 9是3的几倍乘法算法
- 只做强势股指标公式源码
- 360加固了什么反编译
- 普里姆算法适合构造稠密图
- 编译原理的目标代码是什么
- mac编译慢cpu没跑满
- 对数函数变底运算法则
- 找别人写程序包括源码吗
- 模拟退火算法matlab代码
- 算法工程师年龄大了以后怎么办
- ssm看源码哪本书好
- basic语言算法
- 你家离学校源码用英语回答
- js二分搜索算法
- pandas在哪里编译
- 分支定界法算法
- 电脑安全编译器
- 累加C语言算法
- proteus51编译工具
- 图像ai算法工程师创业
- 傅氏算法和积分算法
- 小米手机发布源码
- vs中编译在哪
- 单片机编译picc
- 什么是系统级编译
- 微信做照片小程序源码
- 三根阴线选股指标源码
- PDF编译base64位文件
- 华为方舟编译器和miui
- 编译原理vn集合
- 信源编译码作用
- 编译脚本失败
- 编译无效对象是什么意思
- 编译程序软件哪个好