最小生成树算法源程序
发布网友
共2个回答
热心网友
#include <stdio.h>
#include <stdlib.h>typedef struct{
int vexnum;//点数量
int arcnum;//边数量
int **arcs;//边指针
char *vexs;//点名称
}iGraph;
typedef struct close{
int adjvex;//
int endvex;//
int lowcost;//最小权值
}*closedge,closedges;void CreateUDN(iGraph &G);//创建无向图
int LocateVex(iGraph G,char v);//节点的顶点向量中的下标
void PrintUDN(iGraph G);//输出存储结构示意图
void MiniSpanTree_PRIM(iGraph G,closedge &minedge);//求最小生成树的算法
void PrintMinEdge(iGraph G,closedge minedge);//输出最小生成树的边
int main()
{iGraph G;<br>closedge minedge;</p><p> CreateUDN(G);<br> printf("\n");<br> MiniSpanTree_PRIM(G,minedge);<br> PrintMinEdge(G,minedge);<br> printf("\n");<br> return 0;<br>}void CreateUDN(iGraph &G)
{int i,j,k,l,cost;<br> char name1,name2;</p><p> printf("请输入顶点数和边数，且边数大于或等于顶点数，用空格符隔开：\n");<br> scanf("%d %d",&G.vexnum,&G.arcnum);<br> getchar();<br> G.vexs=(char *)malloc(G.vexnum*sizeof(char));//开辟空间<br> for(i=0;i<G.arcnum;i++)<br> G.arcs=(int **)malloc(G.arcnum*sizeof(int *));<br> for(i=0;i<G.arcnum;i++)<br> G.arcs[i]=(int *)malloc(G.arcnum*sizeof(int));<br> printf("请输入各顶点名字，回车确认：\n");<br> for(i=0;i<G.vexnum;i++)<br> {scanf("%c",&G.vexs[i]);<br> getchar();}
printf("请输入图中各边。按回车结束一条边的输入，输入结束后按回车执行，输入格式为：“端点1-端点2-权值”：\n"); for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=100000; //使边的权值初始化为最大
for(i=0;i<G.arcnum;i++)
{
scanf("%c-%c-%d",&name1,&name2,&cost);
getchar();
for(j=0;j<G.vexnum;j++)//在表中查找点
{ if(name1==G.vexs[j])
k=j;
if(name2==G.vexs[j])
l=j;
}
if(k==l)//两个点如果相同，报错
{i--;<br> printf("输入错误的数据,请重新输入\n");<br> continue;<br> } G.arcs[k][l]=cost;//无向边赋权值
G.arcs[l][k]=cost;
}//使输入的边赋值 for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
if(i==j)
G.arcs[i][j]=0;//如果端点相同，则不存在边
}int LocateVex(iGraph G,char v)//节点的顶点向量中的下标
{int i,m;<br> for(i=0;i<G.vexnum;i++)<br> if(v==G.vexs[i])<br> m=i;<br> return m;<br>}void PrintUDN(iGraph G)//打印模块
{int i,j;<br> printf("对应的矩阵为\n");<br> printf(" ");<br> for(i=0;i<G.vexnum;i++)<br> printf("\t%c ",G.vexs[i]);<br> printf("\n");<br> for(i=0;i<G.vexnum;i++)<br> {<br> for(j=0;j<G.vexnum+1;j++)<br> { <br> if(j==0)<br> printf("%c\t",G.vexs[i]);<br> else<br> if(G.arcs[i][j-1]==100000)//如果没有被赋值，即ij两点不连通<br> printf("NO\t");<br> else<br> printf("%d\t",G.arcs[i][j-1]);<br> }
printf("\n");
}
}void MiniSpanTree_PRIM(iGraph G,closedge &minedge)//最小生成树
{ int i,j,k,z;
int temp;
int currentmin;
k=0;
minedge=(closedge)malloc((G.vexnum+1)*sizeof(closedges));
for(j=1;j<G.vexnum;j++)
{
minedge[j-1].adjvex=k;
minedge[j-1].endvex=j;
minedge[j-1].lowcost=G.arcs[k][j];
}
for(i=0;i<G.vexnum-1;i++)
{ currentmin=minedge[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum-1;j++)
{
if(minedge[j].lowcost<currentmin)
{currentmin=minedge[j].lowcost;<br> k=j;<br> }
}
//第K个元素和第I个元素交换
temp=minedge[i].adjvex;
minedge[i].adjvex=minedge[k].adjvex;
minedge[k].adjvex=temp;
temp=minedge[i].endvex;
minedge[i].endvex=minedge[k].endvex;
minedge[k].endvex=temp;
temp=minedge[i].lowcost;
minedge[i].lowcost=minedge[k].lowcost;
minedge[k].lowcost=temp; for(j=i+1;j<G.vexnum-1;j++)
{
z=minedge[i].endvex;//Z为新找到的顶点
k=minedge[j].endvex;
if(k!=z)
{
if(G.arcs[z][k]<minedge[j].lowcost)
{
minedge[j].adjvex=z;
minedge[j].lowcost=G.arcs[z][k];//和以前的节点比较，如果边的权值小，则，即选取已有的结点中权值最小的边
}
}
}
}
}
void PrintMinEdge(iGraph G,closedge minedge)
{int i,sum;<br>sum=0;<br> printf("最小生成树对应的边为\n");<br> for(i=0;i<G.vexnum-1;i++)<br> {<br> printf("%c-%c:权值为：%d\n",G.vexs[minedge[i].adjvex],G.vexs[minedge[i].endvex],minedge[i].lowcost);<br> sum=sum+minedge[i].lowcost;<br> }
printf("最小生成树的权值为：%d",sum);
}
热心网友
呵呵 这两天我正在做这方面的东西呢 刚好有这是我从网上看的别人的，我觉得很好，思路比较清晰 而且数据结构设计的也很好 很容易看懂 //prim算法#include<iostream>using namespace std; #define MAXVEX 10#define MAX 65000typedef 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; } } }}
