汽车空调电磁离合器Prim算法
1.概览
普⾥姆算法（Prim算法），图论中的⼀种算法，可在加权连通图⾥搜索最⼩⽣成树。意即由此算法搜索到的边⼦集所构成的树中，不但包括了连通图⾥的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最⼩。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普⾥姆（英语：Robert C. Prim）独⽴发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普⾥姆算法⼜被称为DJP算法、亚尔尼克算法或普⾥姆－亚尔尼克算法。 2.算法简单描述
1).输⼊：⼀个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：V new = {x}，其中x为集合V中的任⼀节点（起始点），E new = {}，为空；弹性钢
3).重复下列操作，直到V new = V：
a.在集合E中选取权值最⼩的边<u, v>，其中u为集合V new中的元素，⽽v不在V new集合当中，并且v∈V（如果存在有多条满⾜前述
条件即具有相同权值的边，则可任意选取其中之⼀）；
b.将v加⼊集合V new中，将<u, v>边加⼊集合E new中；
4).输出：使⽤集合V new和E new来描述所得到的最⼩⽣成树。
#define MAX 100000
#define VNUM 10+1 //这⾥没有ID为0的点,so id号范围1~10
int edge[VNUM][VNUM]={/*输⼊的邻接矩阵*/};
int lowcost[VNUM]={0}; //记录Vnew中每个点到V中邻接点的最短边
int addvnew[VNUM]; //标记某点是否加⼊Vnew
int adjecent[VNUM]={0}; //记录V中与Vnew最邻近的点
void prim(int start)
{
int sumweight=0;
int i,j,k=0;
过氧化氢浓度测定for(i=1;i<VNUM;i++) //顶点是从1开始
{
lowcost[i]=edge[start][i];
addvnew[i]=-1; //将所有点⾄于Vnew之外,V之内，这⾥只要对应的为-1，就表⽰在Vnew之外 }
addvnew[start]=0; //将起始点start加⼊Vnew
adjecent[start]=start;
for(i=1;i<VNUM-1;i++)
摆度{
int min=MAX;
int v=-1;
for(j=1;j<VNUM;j++)
{
if(addvnew[j]!=-1&&lowcost[j]<min) //在Vnew之外寻最短路径 {
min=lowcost[j];
v=j;
}
}
if(v!=-1)
{
printf("%d %d %d\n",adjecent[v],v,lowcost[v]);
addvnew[v]=0; //将v加Vnew中
sumweight+=lowcost[v]; //计算路径长度之和
for(j=1;j<VNUM;j++)
{李涛漂移
if(addvnew[j]==-1&&edge[v][j]<lowcost[j])
{
lowcost[j]=edge[v][j]; //此时v点加⼊Vnew 需要更新lowcost
adjecent[j]=v;
}
}
}
}
printf("the minmum weight is %d",sumweight);
}
>十二水磷酸氢二钠
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议