Prime算法——学习笔记
Prime算法是图论中的经典算法,用于在图中寻找最小生成树。Prime算法的原理在于:
(0)首先假设有点队列V和边队列E,两个队列初始都为空
(1)任取一点加入点队列V
(2)在满足一端点在点队列V中,一端点(新节点)不在队列中的所有边中寻找最短边
(3)把新节点加入点队列V中,把新边加入边队列E
(4)重新执行(2)直到所有点都加入点队列
以上图(图片搜索自百度图片)为例
(1)首先任选节点,选择A节点,发现最短边AD,加入队列 V=[A,D];E=[AD]
(2)以V为基础继续搜索,找到DF,加入队列V=[A,D,F];E=[AD,DF]
(3)找到AB,加入队列V=[A,D,F,B];E=[AD,DF,AB]
……
(5)找到EG,加入队列V=[A,D,F,B,E,C,G];E=[AD,DF,AB,BE,EC,EG]
上代码:
//边
struct Edge{
int start;
int end;
int length;
};
//需要传入图邻接矩阵graph,点的个数length
Edge* Fun(int **graph,int length){
//length个点,(length-1)条边
int* V=(int*)calloc(length,sizeof(int));
Edge* E=(Edge*)malloc((length-1)*sizeof(Edge));
//先设起始点,置1说明入队列
V[0]=1;
for(int i=0;i<length-1;i++){
//寻找满足要求的最短边
for (int j=0,min=INT_MAX; j<length; j++) {
//判断当前点是否在点队列
if(V[j]>0){
for(int k=0;k<length;k++){
if(V[k]==0&&graph[j][k]<min&&graph[j][k]>0){
min=graph[j][k];
E[i].start=j;
E[i].end=k;
E[i].length=min;
}
}
}
}
//把新点加入队列
V[E[i].end]=1;
}
free(V);
return E;
}