最小生成树,普利姆(Prim)算法及C/C++代码实现 | 您所在的位置:网站首页 › 二叉树查找算法及代码 › 最小生成树,普利姆(Prim)算法及C/C++代码实现 |
1. 最小生成树(又名:最小权重生成树) 概念:将给出的所有点连接起来(即从一个点可到任意一个点),且连接路径之和最小的图叫最小生成树。最小生成树属于一种树形结构(树形结构是一种特殊的图),或者说是直链型结构,因为当n个点相连,且路径和最短,那么将它们相连的路一定是n-1条。 可以利用参考一个问题理解最小生成树,有n个村庄,每个村庄之间距离不同,要求村庄之间修路,每一个村庄必须与任意一个村庄联通,如何修路最省钱(修的最短) 2. 普利姆算法介绍利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极小连通子图 具体过程如下: (1)设G=(V,E)是连通网,T=(U,D)是最小生成树,V,U是顶点集合,E,D是边的集合 (2)若从顶点u开始构造最小生成树,则从集合V中取出顶点u放入集合U中,标记顶点v的visited[u]=1 (3)若集合U中顶点ui与集合V-U中的顶点vj之间存在边,则寻找这些边中权值最小的边,但不能构成回路,将顶点vj加入集合U中,将边(ui,vj)加入集合D中,标记visited[vj]=1 (4)重复步骤②,直到U与V相等,即所有顶点都被标记为访问过,此时D中有n-1条边 3. 代码实现 不同的题目有不同的细节实现方式,因此本代码仅供参考 #include #include #define n 20 #define MaxNum 10000 /*定义一个最大整数*/ /*定义邻接矩阵类型*/ typedef int adjmatrix[n + 1][n + 1]; typedef struct { int fromvex, tovex; //生成树的起点和终点 int weight; //边的权重 } Edge; typedef Edge *EdgeNode; //定义生成树的别名 int arcnum; /*边的个数*/ /*建立图的邻接矩阵*/ void CreatMatrix(adjmatrix GA) { int i, j, k, e; printf("=============================\n"); printf("图中有%d个顶点\n", n); for(i=1; i |
CopyRight 2018-2019 实验室设备网 版权所有 |