怎样用prim算法求全部最小生成树

发布网友 发布时间：2022-04-23 12:49

我来回答

共2个回答

热心网友 时间：2023-10-18 08:52

//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;
}
}
}
}

热心网友 时间：2023-10-18 08:53

那样意思？