参考zxdxte老师《数据结构、算法及应用》
原理：
G=是连通的带权无向图。 Prim算法通过增加生成树的顶点得到最小生成树。 在算法的任意时刻，一些顶点被添加到生成树的顶点集合中，但其馀顶点没有被添加到生成树中。 此时，Prim算法通过选择边缘，使所有u (起点)都在生成树中，但v )终点)不在生成树中的边缘的权重为最小，从而找到新的顶点v，将她追加到生成树中
详细步骤：
1 )初始状态，U={u1}，TE={}。 这里，u1是图的顶点集合的某个顶点。
2 )找出所有uU，vV-U边(u，v )中代价最小的边) u，v)，放入集合TE； 同时把v '放入集合u。 在这个过程中不要产生电路。
3 )在u=v的情况下，算法结束； 否则重复2。
代码实现：
#包含
#包含
using namespace std；
类边缘{
公共：
int start；
int end；
输入权重；
edge(intstrt，int ed，int w ) {
开始=开始；
end=ed；
weight=w；
}
edge ()。
开始=-1；
end=-1；
weight=-1；
}
(；
//旁边的桌子
类列表node {
公共：
int listver；
int edgenam；
输入权重；
listnode * next；
listnode (listnode * nextval=空值)。
next=nextval；
}
listnode(const intLV，const int en，constint
w，listnode* nextval=NULL ) {
listver=lv；
edgenam=en；
weight=w；
next=nextval；
}
(；
类头节点{
公共：
listnode *start；
头节点() }
start=new listnode (；
}
语音移除全部
listnode *tmp；
wile (开始！=NULL ) {
tmp=start；
start=start-next；
delete tmp；
}
}
~headnode () }
removeall (；
}
(；
类列表图形{
私有：
头节点* gralist；
公共：
int vertexnum；
int edgenum；
int *zjdcjl； //访问过1，未访问过0
列表图形(intn ) {
vertexnum=n；
edgenum=0；
zjdcjl=new int[vertexnum]；
for(intI=0； I
zjdcjl[i]=0；
gralist=new headnode[vertexnum]；
}
~listgraph ()。
delete[]zjdcjl；
delete[]gralist；
vertexnum=0；
edgenum=0；
}
edgefirstedge(intv ) {
edge tmpedge；
tmpedge.start=v；
listnode * tmp lst=gralist [ v ].start；
if(tmplst-next！=NULL )
{
tmpedge.end=tmplst-listver；
}
返回tmp edge；
}
edgenextedge(edgeoneedge ) {
edge tmpedge；
tmpedge.start=oneedge.start；
listnode * tmp lst=gralist [ oneedge.start ].start；
while(tmplst->next!=NULL&&tmplst->next->listver<=oneedge.end)
tmplst=tmplst->next;
if(tmplst->next!=NULL)
{
tmpedge.end=tmplst->next->listver;
}
return tmpedge;
}
void setedge(int strt,int end,int wt){
listnode* tmplst=gralist[strt].start;
while(tmplst->next!=NULL&&tmplst->next->listver
tmplst=tmplst->next;
//确定该边在边结点插入位置
//边在边结点中不存在
if(tmplst->next==NULL){
tmplst->next=new listnode;
tmplst->next->listver=end;
tmplst->next->edgenam=edgenum;
tmplst->next->weight=wt;
edgenum++;
setedge(end,strt,wt);
return;
}
//边在边结点中已存在
if(tmplst->next->listver==end){
edgenum--;
return;
}
//边在边结点中不存在，但在边表中其后存在其他边
if(tmplst->next->listver>end)
{
listnode* tmp=tmplst->next;
tmplst->next=new listnode;
tmplst->next->listver=end;
tmplst->next->edgenam=edgenum;
tmplst->next->next->weight=wt;
tmplst->next->next=tmp;
edgenum++;
setedge(end,strt,wt);
return;
}
}
void deledge(int start,int end){
listnode* tmplst=gralist[start].start;
while(tmplst->next!=NULL&&tmplst->next->listver
tmplst=tmplst->next;
if(tmplst->next==NULL){
cout<
return;
}
if(tmplst->next->listver==end)
{
listnode * tmp=tmplst->next->next;
delete tmplst->next;
tmplst->next=tmp;
edgenum--;
}
}
void show(int v){
cout<
if(gralist[v].start!=NULL)
{
listnode* tmp=gralist[v].start;
// cout<"<listver<
"<edgenam;
while(tmp->next!=NULL)
{
tmp=tmp->next;
cout<"<listver<
"<edgenam;
}
}
return;
}
void show(){
cout<
cout<
cout<
cout<
for(int i=0;i
{
show(i);
cout<
}
return;
}
void visit(int v){
cout<
}
edge * prim(int s){
int i,j;
edge *mst; //存储最小生成树的边
int *nearest; //nearest[i]表示生成树中点到i点的最小边""权值""
int *neighbor; //neighbor[i]表示生成树中与i点最近的""点编号""，
//-1表示i点已经在生成树集合中
int n=vertexnum;
nearest= new int[n];
neighbor=new int [n];
mst=new edge [n-1];
for(i=0;i
{
neighbor[i]=s;
nearest[i]=100;
}
for(listnode* tmp=gralist[s].start->next;tmp!=
NULL;tmp=tmp->next)
{
nearest[tmp->listver]=tmp->weight;
}
neighbor[s]=-1;//将已加入到生成树的点的最近邻设置成-1
for(i=1;i
//用i标记已经加入到生成树中的点个数
int min=100;
int v=-1;
for(j=0;j
//确定一个顶点在生成树集合一个顶点不在生成树集合且权值最小
//的边所关联的顶点
if(nearest[j]-1){
min=nearest[j];
v=j;
}
}
if(v>=0){
//将V加入到生成树集合中，更新生成树外的各个点最小权值的边信息
edge tempedge(neighbor[v],v,nearest[v]);
mst[i]=tempedge;//将边加入到生成树集合中
neighbor[v]=-1;
for(listnode*
tmp=gralist[v].start->next;tmp!=NULL;tmp=tmp->next){
int u=tmp->listver;
if(neighbor[u]!=-1&&nearest[u]>tmp->weight){
//用于V关联的边更新生成树之外顶点到生成树集合的最小权值边
neighbor[u]=v;
nearest[u]=tmp->weight;
}
}
}
}
delete[]neighbor;
delete[]nearest;
cout<
V"<
for(i=1;i
{
cout<
"<
"<
}
return mst;
}
};
int main(){
listgraph graph=listgraph(6);
graph.setedge(0,1,6);
graph.setedge(0,2,1);
graph.setedge(0,3,5);
graph.setedge(1,2,5);
graph.setedge(1,4,3);
graph.setedge(2,3,5);
graph.setedge(2,4,6);
graph.setedge(2,5,4);
graph.setedge(3,5,2);
graph.setedge(4,5,6);
graph.show();
graph.prim(1);
return 0;
}