Ⅰ 急！数据结构最小生成树prim算法c语言实现
Kruskal算法：
void
Kruskal(Edge
E[],int
n,int
e)
{
int
i,j,m1,m2,sn1,sn2,k;
int
vset[MAXE];
for
(i=0;i<n;i++)
vset[i]=i;
//初始化辅助数组
k=1;
//k表示当前构造最小生成树的第几条边,初值为1
j=0;
//E中边的下标,初值为0
while
(k<n)
//生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v;
//取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if
(sn1!=sn2)
//两顶点属于不同的集合,该边是最小生成树的一条边
{
printf("
(%d,%d):%d/n",m1,m2,E[j].w);
k++;
//生成边数增1
for
(i=0;i<n;i++)
//两个集合统一编号
if
(vset[i]==sn2)
//集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++;
//扫描下一条边
}
}
Prim算法：
void
prim(MGraph
g,int
v)
{
int
lowcost[MAXV],min,n=g.vexnum;
int
closest[MAXV],i,j,k;
for
(i=0;i<n;i++)
//给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for
(i=1;i<n;i++)
//找出n-1个顶点
{
min=INF;
for
(j=0;j<n;j++)
//在(V-U)中找出离U最近的顶点k
if
(lowcost[j]!=0
&&
lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf("
边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0;
//标记k已经加入U
for
(j=0;j<n;j++)
//修改数组lowcost和closest
if
(g.edges[k][j]!=0
&&
g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
Ⅱ 利用Prim（普里姆）算法 构造最小生成树 程序
算法同样是解决最小生成树的问题。
其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。
与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。
复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}
Ⅲ 用prim算法的思想，用C语言编写出最小生成树的方法的代码
PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}
Ⅳ c++求最小生成树prim算法,我捣鼓2天了,真心不会改了,求指导感激不尽啊
你的代码太乱，给你这个，添加了注释，容易看懂：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
usingnamespacestd;
#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];//节点数组
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图的当前节点数和弧数
}MGraph;
typedefstructPnode//用于普利姆算法
{
charadjvex;//节点
doublelowcost;//权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
charch1;//节点1
charch2;//节点2
doublevalue;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevalue&dgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue)//构造无向加权图的邻接矩阵
{
inti,j,k;
cout<<"请输入图中节点个数和边/弧的条数：";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入节点：";
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)//初始化数组
{
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
}
cout<<"请输入一条边依附的定点及边的权值："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1);
j=LocateVex(G,dgevalue[k].ch2);
G.arcs[i][j].adj=dgevalue[k].value;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置
{
inta;
for(inti=0;i<G.vexnum;i++)
{
if(G.vexs[i]==ch)
a=i;
}
returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成树
{
inti,j,k;
Closedgeclosedge;
k=LocateVex(G,u);
//将该顶点到其他所有的顶点权值赋值给closedge
for(j=0;j<G.vexnum;j++)
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
//找到权值最小的顶点，记录到k
k=Minimum(G,closedge);
cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
//清零，方便寻找下一个顶点
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
{
//依次比较上个顶点和当前顶点与剩余顶点的权值，将小的赋值给closedge
if(G.arcs[k][j].adj<closedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
inti,j;
doublek=1000;
for(i=0;i<G.vexnum;i++)
{
if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidmain()
{
inti,j;
MGraphG;
charu;
Dgevaluedgevalue;
CreateUDG(G,dgevalue);
cout<<"图的邻接矩阵为："<<endl;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
cout<<G.arcs[i][j].adj<<"";
cout<<endl;
}
cout<<"=============普利姆算法=============== ";
cout<<"请输入起始点：";
cin>>u;
cout<<"构成最小代价生成树的边集为： ";
MiniSpanTree_PRIM(G,u);
}
Ⅳ 用prim算法求最小生成树:c语言
把main函数改成：
main(){
GraphMatrix graph = {
"abcd",
{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},
};
Edge mst[Max];
int i,j;
prim(graph,mst);
for(j=0;j<Max;j++)
{
printf("%c\t",mst[j].stop_vex);
printf("%c\t",mst[j].start_vex);
printf("%d\n",mst[j].weight);
}
}
还有GraphMatrix结构体里的vexs数组最好定义为vexs[VN+1]给字符串末尾的‘\0'留地方。
Ⅵ 求数据结构(C语言)prim算法求最小生成树
PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){ //求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)； //根据新红点v调整候选轻边集
}
}
Ⅶ 对任意的网和起点,用PRIM算法的基本思想求解出所有的最小生成树(C语言编写)
prim基本思想就是贪心，每次加最短的边
既然要求所有的
那就判断如果有两条或更多条都是最小，那就分支出多种情况。
Ⅷ 关于Prim算法求最小生成树的问题
PrimMST(G，T，r){ //求图G的以r为根的MST，结果放在T=(U，TE)中 InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠) for(k=0；k<n-1；k++){ //求T的n-1条树边 (u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)； T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U ModifyCandidateSet(…)； //根据新红点v调整候选轻边集 } }
Ⅸ 怎样用prim算法求全部最小生成树
//prim算法
#include<iostream>
using namespace std;
#define MAXVEX 10
#define MAX 65000
typedef char VexType;
typedef float AdjType;
struct GraphMatrix
{
VexType vexs[MAXVEX]; //顶点信息
AdjType arcs[MAXVEX][MAXVEX]; //边信息
int n; //图的顶点个数
};
struct Edge
{
int start_vex; //边的起点
int stop_vex; //边的终点
AdjType weight; //边的权
};
void edgeCopy(Edge *to,Edge *from)
{
to->start_vex=from->start_vex;
to->stop_vex=from->stop_vex;
to->weight=from->weight;
}
void prim(GraphMatrix *pgraph,Edge *mst)
{
int i,j;
int vx,vy;
int min;
AdjType weight,minweight;
Edge edge;
for(i=0;i<pgraph->n-1;++i)
{
mst[i].start_vex=0;
mst[i].stop_vex=i+1;
mst[i].weight=pgraph->arcs[0][i+1];
}
for(i=0;i<pgraph->n-1;++i)
{
minweight=MAX;
min=i;
for(j=i;j<pgraph->n-1;++j)
if(mst[j].weight<minweight)
{
minweight=mst[j].weight;
min=j;
}
edgeCopy(&edge,&mst[min]);
edgeCopy(&mst[min],&mst[i]);
edgeCopy(&mst[i],&edge);
vx=mst[i].stop_vex;
for(j=i+1;j<pgraph->n-1;++j)
{
vy=mst[j].stop_vex;
weight=pgraph->arcs[vx][vy];
if(weight<mst[j].weight)
{
mst[j].weight=weight;
mst[j].start_vex=vx;
}
}
}
}