个人中心
gpt4 book ai didi

Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Prim(普里姆)算法求最小生成树的思想及C语言实例讲解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

Prim 算法思想： 从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1，再连接与 T1 最近顶点 v2 构成树 T2， 如此重复直到所有顶点均在所构成树中为止。 最小生成树（MST）：权值最小的生成树。 生成树和最小生成树的应用：要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 构造网的最小生成树必须解决下面两个问题： 1、尽可能选取权值小的边，但不能构成回路； 2、选取n－1条恰当的边以连通n个顶点； MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。 prim算法假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。  Prim算法的核心:始终保持TE中的边集构成一棵生成树。 注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。 举个简单的例子来说明具体的实现方法:

Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

G:图，用邻接矩阵表示 vcount:表示图的顶点个数 max_vertexes:图最大节点数 infinity:为无穷大 数组存储从0开始 由于最小生成树包含每个顶点，那么顶点的选中与否就可以直接用一个数组来标记used[max_vertexes];（我们这里直接使用程序代码中的变量定义，这样也易于理解）；当选中一个数组的时候那么就标记，现在就有一个问题，怎么来选择最小权值边，注意这里最小权值边是有限制的，边的一个顶点一定在已选顶点中，另一个顶点当然就是在未选顶点集合中了。我最初的一个想法就是穷搜了，就是在一个集合中选择一个顶点，来查找到另一个集合中的最小值，这样虽然很易于理解，但是很明显效率不是很高，在严蔚敏的《数据结构》上提供了一种比较好的方法来解决：设置两个辅助数组lowcost[max_vertexes]和closeset[max_vertexes]，lowcost[max_vertexes]数组记录从U到V－U具有最小代价的边。对于每个顶点v∈V－U,closedge[v], closeset[max_vertexes]记录了该边依附的在U中的顶点.

Prim 算法步骤： T0 存放生成树的边，初值为空 输入加权图的带权邻接矩阵 C = (Cij)n×n (两点间无边相连则其大小为无穷) 为每个顶点 v 添加一属性 L(v) ：表 v 到 T0 的最小直接距离 （1) T0←∅, V1={v0}, C(T0)=0 （2) 对任意v ∈ V，L(v)←C(v, v0) （3) If V==V1 then stop else goto next. （4) 在 V-V1 中找点 u 使 L(u) =min{ L(v) | v ∈ (V − V1 )},记 V1 中与 u 相邻点为 w. （5) T0←T0∪{(u, w)}, C(T0) ←C(T0)+C(u, w), V1←V1∪{u} （6) 对任意v ∈ (V − V1 ) if C(v, u)<L(v) then L(v) = C(v, u) else L(v)不变。 （7) Go to 3. 。

C++实现示例 prim.txt中的内容

?
1
2
3
4
5
6
7
8
9
10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
5 6 6
4 6 2

  程序代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<stdo.h>
#include<string.h>
#include <stdlib.h>
 
#define infinity 1000000 //  定义两个不直接相邻一步到达顶点的距离
#define max_vertexes 6 //  定义图形中顶点的个数
 
typedef int Graph[max_vertexes][max_vertexes]; // 边上的权值
 
void prim(Graph G, int vcount, int father[])
{ 
   int i,j,k;
   int lowcost[max_vertexes]; //最小代价边上的权值
   int closeset[max_vertexes],used[max_vertexes]; //依附在U中的顶点；标记是否已被选中
   int min;
   int result=0; //记录最短距离权值的和
 
 
   for (i=0;i<vcoun;k++)  //初始化所有数组，把最短距离初始化为其他顶点到1结点的距离
   {
       lowcost[i]=G[0][i];
       closeset[i]=0;  
    used[i]=0; 
    father[i]=-1;  
   } 
   used[0]=1;
 
 
  
   for (i=1;i<=vcount-1;i++)  
   {  
    j=0;
     min = infinity;
      
    for (k=1;k<count;k++) //for循环得到离结点最近的顶点j
    if ((!used[k])&&(lowcost[k]
    {
     min = lowcost[k];
     j=k;
    }
    father[j]=closeset[j];
    printf ( "%d %d\n" ,j+1,father[j]+1); //输出当前找到的结点，该顶点依附的上一个结点
    result=result+G[j][closeset[j]];
    used[j]=1;; //把第j个顶点并入了U中 
    for (k=1;k
        
    if (!used[k]&&(G[j][k]保留到k的最短路径
 
     {
       lowcost[k]=G[j][k];  
       closeset[k]=j;
     }  
   }
   printf ( "%d" ,result);
}
        
int main()
{
   FILE *fr;
   int i,j,weight;
   Graph G;
   int fatheer[max_vertexes];
   for (i=0; i<max_vertexes;i++)
   for (j=0; j<max_vertexer;i++)
   G[i][j] = infinity;
   fr = fopen ( "prim.txt" , "r" );
   if (!fr)
   {
    printf ( "fopen failed\n" );
    exit (1);
   }
   while ( fscanf (fr, "%d%d%d" , &i, &j, &weight) != EOF)
   {
    G[i-1][j-1] = weight;
    G[j-1][i-1] = weight;
   }
 
   prim(G,max_vertexes,fatheer);
   return 0;
 
}

测试的结果如下:

最后此篇关于Prim(普里姆)算法求最小生成树的思想及C语言实例讲解的文章就讲到这里了,如果你想了解更多关于Prim(普里姆)算法求最小生成树的思想及C语言实例讲解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： Python读写/追加excel文件Demo分享
文章推荐： C语言获取Shell返回结果的实现方法
文章推荐： windows下安装Python的XlsxWriter模块方法
文章推荐： Python中的字符串类型基本知识学习教程
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com