博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Prim算法的C语言程序
阅读量:5843 次
发布时间:2019-06-18

本文共 1401 字,大约阅读时间需要 4 分钟。

Prim算法是有关图的最小生成树的算法。1957年由美国计算机科学家罗伯特·普里姆(Robert C. Prim)独立发现

程序来源:。

百度百科:。

维基百科:。

需要说明的是,该程序使用了三重循环,其计算速度相当的慢,可以说是不可用的。

C语言程序(去除了原文中非标准的C语言代码):

#include 
int a,b,u,v,n,i,j,ne=1;int visited[10]={0},min,mincost=0, cost[10][10];int main(){ printf("\nEnter the number of nodes:"); scanf("%d",&n); printf("\nEnter the adjacency matrix:\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&cost[i][j]); if(cost[i][j] == 0) cost[i][j] = 999; } visited[1]=1; printf("\n"); while(ne < n) { for(i=1,min=999; i<=n; i++) for(j=1; j<=n; j++) if(cost[i][j] < min) if(visited[i] != 0) { min = cost[i][j]; a = u = i; b = v = j; } if(visited[u]==0 || visited[v]==0) { printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min); mincost+=min; visited[b]=1; } cost[a][b] = cost[b][a] = 999; } printf("\n Minimun cost=%d\n",mincost);}
运行结果:

Enter the number of nodes:6Enter the adjacency matrix:0 3 1 6 0 03 0 5 0 3 01 5 0 5 6 46 0 5 0 0 20 3 6 0 0 60 0 4 2 6 0 Edge 1:(1 3) cost:1 Edge 2:(1 2) cost:3 Edge 3:(2 5) cost:3 Edge 4:(3 6) cost:4 Edge 5:(6 4) cost:2 Minimun cost=13

转载于:https://www.cnblogs.com/tigerisland/p/7564184.html

你可能感兴趣的文章
Java类加载过程及static详解
查看>>
background-color和background-image相关细节
查看>>
如何学好C#
查看>>
梅沙教育APP简单分析-版本:iOS v1.2.21-Nathaneko-佳钦
查看>>
Word中如何设置图片与段落的间距为半行
查看>>
Firefox about
查看>>
Angular - - angular.element
查看>>
美图秀秀首页界面按钮设计(二)
查看>>
nginx安装及负载均衡配置
查看>>
JQuery this和$(this)的区别及获取$(this)子元素对象的方法
查看>>
tomcat不能多次startup.sh,异常时直接,分析logs目录下的日志。
查看>>
关于分区索引与全局索引性能比较的示例
查看>>
ASP.NET MVC学习之(5):Html.ActionLink
查看>>
yii_wiki_145_yii-cjuidialog-for-create-new-model (通过CJuiDialog来创建新的Model)
查看>>
431.chapter2.configure database mail
查看>>
同一页面中引入多个JS库产生的冲突解决方案(转)
查看>>
C语言之指针与数组总结
查看>>
沟通:用故事产生共鸣
查看>>
1080*1920 下看网站很爽
查看>>
topcoder srm 305 div1
查看>>