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

2024-11-27 18:16:59

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)跟边的数目有关，适合稀疏图。
举个简单的例子来说明具体的实现方法：

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中的内容:

程序代码：

#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;

}

测试的结果如下：

C语言数据结构树的双亲表示法实例详解

1.树的双亲表示法: 树的双亲表示法 2./* bo6-4.c 树的双亲表存储(存储结构由c6-4.h定义)的基本操作(14个) */ Status InitTree(PTree *T) { /* 操作结果: 构造空树T */ (*T).n=0; return OK; } void DestroyTree() { /* 由于PTree是定长类型,无法销毁 */ } typedef struct { int num; TElemType name; }QElemType; /* 定义队列元素类型
C语言实现树的动态查找实例代码

C语言实现树的动态查找实例代码本例演示一种树数据结构存储记录集合时的动态查找方法.首先程序通过construct()函数,利用已经存在的结构体数组数据建立一个二叉树,建立树的过程中,要保证每个节点的值都大于它的左子树上节点的值而小于它右子树所有节点的值,该函数返回建立树的根指针:然后通过函数Search(root,name)查找,如果找到相应的数据,将其打印出来,如果没有找到,则用户可以选择是否将该数据插入到树中. 具体代码如下: #include <stdio.h> #include &l
C语言二叉查找树性质详解及实例代码

二叉查找树性质 1.二叉树每个树的节点最多有两个子节点的树叫做二叉树. 2.二叉查找树一颗二叉查找树是按照二叉树的结构来组织的,并且满足一下性质: 一个节点所有左子树上的节点不大于盖节点,所有右子树的节点不小于该节点. 对查找树的操作查询,插入,删除等操作的时间复杂度和树的高度成正比, 因此,构建高效的查找树尤为重要. 查找树的遍历先序遍历查找树的遍历可以很简单的采用递归的方法来实现. struct list { struct list *left;//左子树 struct list *
C语言实现二叉树的搜索及相关算法示例

本文实例讲述了C语言实现二叉树的搜索及相关算法.分享给大家供大家参考,具体如下: 二叉树(二叉查找树)是这样一类的树,父节点的左边孩子的key都小于它,右边孩子的key都大于它. 二叉树在查找和存储中通常能保持logn的查找.插入.删除,以及前驱.后继,最大值,最小值复杂度,并且不占用额外的空间. 这里演示二叉树的搜索及相关算法: #include<stack> #include<queue> using namespace std; class tree_node{ public
C语言中计算二叉树的宽度的两种方式

C语言中计算二叉树的宽度的两种方式二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo
C语言实现线索二叉树的定义与遍历示例

本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN
使用C语言实现最小生成树求解的简单方法

最小生成树Prim算法朴素版有几点需要说明一下. 1.2个for循环都是从2开始的,因为一般我们默认开始就把第一个节点加入生成树,因此之后不需要再次寻找它. 2.lowcost[i]记录的是以节点i为终点的最小边权值.初始化时因为默认把第一个节点加入生成树,因此lowcost[i] = graph[1][i],即最小边权值就是各节点到1号节点的边权值. 3.mst[i]记录的是lowcost[i]对应的起点,这样有起点,有终点,即可唯一确定一条边了.初始化时mst[i] = 1,即每条边都是从
Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

Prim 算法思想: 从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1,再连接与 T1 最近顶点 v2 构成树 T2, 如此重复直到所有顶点均在所构成树中为止. 最小生成树(MST):权值最小的生成树. 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路.可以把边上的权值解释为线路的造价.则最小生成树表示使其造价最小的生成树. 构造网的最小生成树必须解决下面两个问题: 1.尽可能选取权值小的边,但不能构成回路: 2.选取n-1条恰当的边以连通n个顶点: MST性质:假设G＝(V
JS/HTML5游戏常用算法之路径搜索算法随机迷宫算法详解【普里姆算法】

本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法随机迷宫算法.分享给大家供大家参考,具体如下: 路径搜索算法在游戏中非常常见,特别是在 RPG.SLG 中经常用到.在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的.通俗地说,就是在一张地图中,如何让主角自动行走到指定的地点,如图6-21所示,假设主角在A处,然后玩家在地图中点击B处,要求主角能够从A点自动找寻一条到 B 点的路径,然后自动移动到 B处,要求就这么简单.
JS使用Prim算法和Kruskal算法实现最小生成树

之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法. 一.权重图和最小生成树权重图:图的边带权重最小生成树:在连通图的所有生成树中,所有边的权重和最小的生成树本文使用的图如下: 它的最小生成树如下: 二.邻接矩阵邻接矩阵:用来表示图的矩阵就是邻接矩阵,其中下标表示顶点,矩阵中的值表示边的权重(或者有无边,方向等). 本文在构建邻接矩阵时,默认Number.MAX_SAFE_INTEGER表示两个节点之间没有边,Number.MIN_
Java求最小生成树的两种算法详解

目录 1 最小生成树的概述 2 普里姆算法(Prim) 2.1 原理 2.2 案例分析 3 克鲁斯卡尔算法(Kruskal) 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 6 总结介绍了图的最小生成树的概念,然后介绍了求最小生成树的两种算法:Prim算法和Kruskal算法的原理,最后提供了基于邻接矩阵和邻接链表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最小生成树的
java图论普利姆及克鲁斯卡算法解决最小生成树问题详解

目录什么是最小生成树? 普利姆算法算法介绍应用 --> 修路问题图解分析克鲁斯卡尔算法算法介绍应用场景 -- 公交站问题算法图解算法分析如何判断是否构成回路什么是最小生成树? 最小生成树(Minimum Cost Spanning Tree),简称MST. 最小生成树要求图是连通图.连通图指图中任意两个顶点都有路径相通,通常指无向图.理论上如果图是有向.多重边的,也能求最小生成树,只是不太常见. 普利姆算法算法介绍应用 --> 修路问题图解分析
C++使用Kruskal和Prim算法实现最小生成树

很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易.最近学习了并查集算法,得知并查集可以用于实现上述两个算法后,我自己动手实现了最小生成树算法. 宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构--优先级队列,用于动态排序.由于这两个算法很容易理解,在此不再赘述.接下来给出我的源代码. 输入第一行包含两个整数n和m,n表示图中结点个数,m表示图中边的条数:接下来m行,每一行
NetworkX之Prim算法(实例讲解)

引言 Prim算法与Dijkstra的最短路径算法类似,它采用贪心策略.算法开始先把图中权值最小的边添加到树T中,然后不断把权值最小的边E(E的一个端点在T中,另一个在G-T中).当没有符合条件的E时算法结束,此时T就是G的一个最小生成树. NetworkX是一款Python的软件包,用于创造.操作复杂网络,以及学习复杂网络的结构.动力学及其功能. 本文借助networkx.Graph类实现Prim算法. 正文 Prim算法的代码 Prim def prim(G, s): dist = {} #
浅谈算法之最小生成树Kruskal的Python实现

目录一.前言二.树是什么三.从图到树四.解决生成问题五.从生成树到最小生成树六.实际问题与代码实现七.结尾一.前言我们先不讲算法的原理,也不讲一些七七八八的概念,因为对于初学者来说,看到这些术语和概念往往会很头疼.头疼也是正常的,因为无端突然出现这么多信息,都不知道它们是怎么来的,也不知道这些信息有什么用,自然就会觉得头疼.这也是很多人学习算法热情很高,但是最后又被劝退的原因. 我们先不讲什么叫生成树,怎么生成树,有向图.无向图这些,先简单点,从最基本的内容开始,完整地将这个算
C#图表算法之最小生成树

目录 1.原理 1.切分定理 2.贪心算法 2.加权无向图的数据类型 3.最小生成树 API 4.Prim 算法数据结构维护横切边的集合实现性能 5. Prim 算法的即时实现 6.Kruskal 算法实现加权图是一种为每条边关联一个权值或是成本的图模型.这种图能够自然地表示许多应用.在一幅航空图中,边表示航线,权值则可以表示距离或是费用.在这些情形中,最令人感兴趣的自然是将成本最小化.这里用加权无向图模型来解决最小生成树:给定一幅加权无向图,找到它的一棵最小生成树. 图的生成树是它
C++用Dijkstra(迪杰斯特拉)算法求最短路径

算法介绍迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低. 算法思想按路径长度递增次序产生算法: 把顶点集合V分成两组: (1)S:已求出的顶点的集合(初始时只含有源点V0) (2)V-S=T:尚未确定的顶点集合将T中顶点按递增

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

相关推荐

随机推荐