普里姆算法
从连通图N=(U,E)中招最小生成树T=(U,TE).
1.算法思想
<1>若从顶点v0出发构造,U={v0},TE={};
<2>先找权值最小的边(u,v),其中u∈U且v∈V-U,并且子图不构成环,则
U=U∪{v},TE=TE∪{(u,v)};
<3>重复(2),直到U=V为止.则TE中必有n-1条边,T=(U,TE)就是最小生成树
2.
设用邻接 矩阵 ((二维数组))表示图,两个顶点之间不存在边的权值为机内允许的最大值。
为便于算法实现,设置一个一 维数组
closedge[n],用来保存,V-U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是
struct
{
int adjvex;/*边所依附于U中的顶点*/
int lowcost;/*该边的权值*/
}closedge[MAX_EDGE];
在Prime算法中,图采用邻接矩阵存储,所构造的最小生成树用一维数组存储其n-1条边,
每条边的存储结构描述:
typedef struct MSTEdge
{
int vex1,vex2;/*边所依附的图的两个顶点*/
WeightType weight;/*边的权值*/
}MSTEdge;
算法实现
#define INFINITY MAX_VAL
MSTEdge *Prim_MST(AdjGraph *G,int u)
{
MSTEdge TE[];
int j,k,v,min;
for(j=0;j<G->vexnum;j++)
{
closedge[j].adjvex=u;
closedge[j].lowcost=G->adj[j][u];
}/*初始化数组closedge[n]*/
closedge[u].lowcost=0;
TE=(MSTEdge*)malloc((G->vexnum-1)*sizeof(MSTEdge));
for(j=0;j<G->vexnum;j++)
{
min=INFINITY;
for(v=0;v<G->vexnum;v++)
if(closedge[v].lowcost!=0&&closedge[v].lowcost<min)
{min=closedge[v].lowcost;k=v;}
TE[j].vex1=closedge[k].adjvex;
TE[j].vex2=k;
TE[j].weight=closedge[k].lowcost;
closedge[k].lowcost=0;/*将顶点k并入U*/
for(v=0;v<G->vexnum;v++)
if(G->adj[v][k]<closedge[v].lowcost)
{
closedge[v].lowcost=G->adj[v][k];
closedge[v].adjvex=k;
}/*修改数组closedge[n]的各个元素的值*
/
}
return (TE);
}/*求最小生成树的Prim算法*/
克鲁斯卡尔(Kruskal)算法
1 算法思想
设G=(V, E)是具有n个顶点的连通网,T=(U, TE)是其最小生成树。初值:U=V,,TE={} 。
对G中的边按权值大小从小到大依次选取。
<1>选取权值最小的边(vi,vj),若边(vi,vj)加入到TE后形成回路,则舍弃该边(vi,vj) ;
否则,将该边并入到TE中,,即TE=TE∪{(vi,vj)} 。
<2>重<1>,直到TETE中包含有n-1条边为止。
2 算法实现说明
Kruskal 算法实现的关键是:当一条边加入到TE的集合后,如何判断是否构成回路??
简单的解决方法是:定义一个一维数组Vset[n] ,存放图T中每个顶点所在的连通分量的编号。
◆初值:Vset[i]=i,表示每个顶点各自组成一个,连通分量,连通分量的编号简单地使用顶点在图中的位置((编号))。
◆当往T中增加一条边(vi,vj) 时,先检查Vset[i]和Vset[j]值:
☆若Vset[i]=Vset[j]:表明 :vi和vj处在同一个连通分量中,,加入此边会形成回路
☆ 若Vset[i]≠Vset[j],则 加入此边不会形成
回路 ,将此边加入到生成树的边集中。
◆ 加入一条新边后,将两个不同的连通分量合并
将一个 连通分量的编号换成另 一个 连通分量的编
号。
算法实现
MSTEdge *Kruskal(ELGraph *G)
{
MSTEdge TE[];
int j,k,s1,s2,Vset[];
WeightType w;
Vset=(int*)malloc(G->vexnum*sizeof(int));
for(j=0;j<G->vexnum;j++)
Vset[j]=j;/*初始化数组Vset[n]*/
sort(G->edgelist);/*对表按权值从小到大排序*/
j=0;k=0;
while(k<G->vexnum-1&&j<G->edgenum)
{
s1=Vset[G->edgelist[j].vex1];
s2=Vset[G->edgelist[j].vex2];
/*若边的两个顶点的连通分量编号不同,边加入到TE中*/
if(s1!=s2)
{
TE[k].vex1=G->edgelist[j].vex1;
TE[k].vex2=G->edgelist[j].vex2;
TE[k].weight=G->edgelist[j].weight;
k++;
for(v=0;v<G->vexnum;v++)
if(Vset[v]==s2)Vset[v]=s1;
}
j++;
}
free(Vset);
return (TE);
}
分享到:
相关推荐
.
1.最小生成树: 15 2.最大流量: 17 3.决策论 20 4.灵敏度分析 22 5.线性规划 23 6.动态规划 24 7.牛吃草问题(追及问题): 24 其他公式: 26 1.沟通渠道计算公式: 26 2.香农用概率来定量描述...
算法包含:最小生成树,一元多项式,复数四则运算,哈夫曼树,内部排序,二叉树的深度和叶子节点个数
数学建模matlab常用算法代码整理的集合,包含神经网络图像分类代码,图论算法软件,小波神经网络预测代码,元胞自动机代码,Dijkstra算法找最短路径代码,Floyd算法求最小距离代码,GRNN的...最小生成树MATLAB程序。
408科目中几个基础知识点的归纳总结: OSI参考模型、最小生成树算法、最短路径算法、排序方式、计算机网络中熟知端口号
+ [最小生成树](#最小生成树) + [二分图](#二分图) + [Voronoi图](#voronoi图) + [偶图](#偶图) * [树](#树) + [树](#树-1) + [路径问题](#路径问题) + [最近公共祖先](#最近公共祖先) + [划分问题](#划分...
2.5.5 最小生成树 2.5.6 应用问题 2.6 数学问题的解题窍门 2.6.1 辗转相除法 2.6.2 有关素数的基础算法 2.6.3 模运算 2.6.4 快速幂运算 2.7 一起来挑战GCJ的题目(1) 2.7.1 Minimum Scalar Product 2.7.2 Crazy ...
datastructure-learning-example java 数据结构练习示例 ... (图的最小生成树) (图的最短路径和拓扑排序) (排序算法汇总) 冒泡排序 选择排序 直接插入排序 二分法排序 希尔排序 快速排序 堆排序 归并排序 基数排序
图论:最短路径、最小生成树 动态规划:背包问题、最长子序列 数据结构,主要有如下几种: 数组与链表:单 / 双向链表 栈与队列 哈希表 堆:最大堆 / 最小堆 树与图:最近公共祖先、并查集 字符串:前缀树(字典树...
【图论】最小生成树 kurskal算法、prim算法.md 【图论】最短路径 深宽度优先搜索算法、Dijkstra算法、Floyd算法.md 【排序算法】十大经典排序算法.md 【数据结构】二叉排序树.md 【数据结构】二叉树.md 【数据结构】...
实例139 求最小公倍数 182 实例140 判断素数的算法 183 实例141 按要求生成指定位数的编号 184 实例142 身份证号从15位升到18位的算法 186 实例143 歌德巴赫猜想的算法实现 187 实例144 八皇后问题的算法实现 188 ...
372 9.3.2 子空间聚类 374 9.3.3 DENCLUE:基于密度聚类的一种基于核的方案 377 9.4 基于图的聚类 379 9.4.1 稀疏化 379 9.4.2 最小生成树聚类 380 9.4.3 OPOSSUM:使用METIS的稀疏相似度最优划分 381 9.4.4 ...