Prim算法-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

Prim算法

阅读量：5798 次

发布时间：2019-06-18

本文共 2458 字，大约阅读时间需要 8 分钟。

普利姆算法，是一种常用的求最小生成树的算法。

最小生成树，使得一个连通图内拥有最小的和。对现实生活中有极大的作用。

主要思路

1 选定一个顶点（与结果无关）

2 寻找与这个顶点相连的最小权值的邻居

while(j

3 把这个邻居，加入到最小生成树集合中。

4 在此新加入的顶点基础上，寻找与该集合相连的最小权值的邻居。重复2。

for(j=1;j
     
      arc[k][j] < lowcost[j]){                lowcost[j] = g->arc[k][j];                ver[j] = k;            }        }

5 直到所有顶点都存在于该集合中

算法代码

1 void Prim(Graph *g){ 2     int min,i,j,k; 3     int ver[MAXSIZE]; 4     int lowcost[MAXSIZE]; 5     lowcost[0] = 0; 6     ver[0] = 0; 7     for(i=1;i
     
      arc[0][i]; 9         ver[i] = 0;10     }11     for(i=1;i
      
       arc[k][j] < lowcost[j]){32                 lowcost[j] = g->arc[k][j];33                 ver[j] = k;34             }35 36         }37     }38 }

示例代码

1 #include 
      
        2 #include 
       
         3 #define MAXSIZE 9 4 #define INF 65535 5 typedef struct Graph{ 6     int arc[MAXSIZE][MAXSIZE]; 7 }Graph; 8  9 void initGraph(Graph *g);10 void showGraph(Graph *g);11 void Prim(Graph *g);12 13 int num[MAXSIZE][MAXSIZE]={ 0,  10, INF,INF,INF,11, INF,INF,INF,14                 10, 0,  18, INF,INF,INF,16, INF,12,15                 INF,INF,0,  22, INF,INF,INF,INF,8,16                 INF,INF,22, 0,  20, INF,INF,16, 21,17                 INF,INF,INF,20, 0,  26, INF,7,  INF,18                 11, INF,INF,INF,26, 0,  17, INF,INF,19                 INF,16, INF,INF,INF,17, 0,  19, INF,20                 INF,INF,INF,16, 7,  INF,19, 0,  INF,21                 INF,12, 8,  21, INF,INF,INF,INF,0};22 int main()23 {24     Graph *g = (Graph *)malloc(sizeof(Graph));25     initGraph(g);26     showGraph(g);27     printf("\n\n");28     Prim(g);29 30     return 0;31 }32 33 void initGraph(Graph *g){34    int i,j;35    for(i=0;i<9;i++){36         for(j=0;j<9;j++){37             g->arc[i][j]=num[i][j];38         }39     }40 }41 void showGraph(Graph *g){42     int i,j;43     for(i=0;i<9;i++){44         for(j=0;j<9;j++){45             printf("%d ",g->arc[i][j]);46         }47         printf("\n");48     }49 }50 51 void Prim(Graph *g){52     int min,i,j,k;53     int ver[MAXSIZE];54     int lowcost[MAXSIZE];55     lowcost[0] = 0;56     ver[0] = 0;57     for(i=1;i
        
         arc[0][i];59         ver[i] = 0;60     }61     for(i=1;i
         
          arc[k][j] < lowcost[j]){82                 lowcost[j] = g->arc[k][j];83                 ver[j] = k;84             }85 86         }87     }88 }

View Code

运行结果

转载于:https://my.oschina.net/u/204616/blog/545281

你可能感兴趣的文章

python 开发之selenium

Xcode3.2.5中找不到Mac OS X - Command Line Utility -...

css的div垂直居中的方法，百分比div垂直居中

如何理解EM算法

nginx 域名跳转一例~~~(rewrite、proxy)

我的友情链接

linux用户家目录无损迁移到独立硬盘

shell编程前言（一）

5、centos7.*配置yum的EPEL源及其它源

JSON前后台简单操作

shell中一些常见的文件操作符

CentOS 7 装vim遇到的问题和解决方法

JavaScript基础教程1-20160612

使用第三方类、库需要注意的正则类RegexKitLite的使用

iOS \U7ea2 乱码转换

FCN图像分割

设计模式之-工厂模式、构造函数模式

python matplotlib 中文显示参数设置

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-12-22 12:58:59 当前IP: 18.189.182.15 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我