prim.cpp.txt

PRIM算法 对任意给定的网和起点

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN 0
#define MAX_V_N 20
typedef enum {DG,DN,UDG,UDN} GraphKind; //DG表示有向图,  DN表示有向网,  UDG表示无向图,  UDN表示无向网
typedef struct ArcNode{
int adj;
char * info;//该弧相关信息的指针
}ArcNode,
AdjMatrix[MAX_V_N][MAX_V_N];//邻接矩阵
typedef struct {
int vexs[MAX_V_N];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
//-------
int LocateVex(int vexs[],int v){ //确定节点v在节点向量中的位置
for(int i=0;i<MAX_V_N;i++)
if(vexs[i]==v)
return i;
printf("不存在这个节点!");
exit(0);
}
bool  CreateMarph(MGraph &G){ //bool函数返回ture or false
int IncInfo,v1,v2,weight,i,j,k;
printf("请输入%s的顶点数和弧数，以及各弧是否含有其他信息(0表示不含其它信息)\n","无向网");
scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
for(i=0;i<G.vexnum;i++){ //初始化节点向量

G.vexs[i]=i+1;
}
for(i=0;i<G.vexnum;i++){ //初始化邻接矩阵
for(j=0;j<G.vexnum;j++){
G.arcs[i][j].adj=MIN; G.arcs[i][j].info=NULL;
}
}
for(k=0;k<G.arcnum;k++){ //输入一条边及依附的定点及权值
printf("请输入第%d弧的%s:",k+1,"两个节点及权值");
scanf("%d%d%d",&v1,&v2,&weight);
i=LocateVex(G.vexs,v1); j=LocateVex(G.vexs,v2); //找到两个顶点在邻接矩阵中的位置
G.arcs[i][j].adj=weight;
if(IncInfo!=0)
scanf("%s",G.arcs[i][j].info); //若弧含有相关信息，则输入信息
G.arcs[j][i].adj=G.arcs[i][j].adj; //置<v1，v2>的对称弧<v2，v1>
G.arcs[j][i].info=G.arcs[i][j].info;
}
return true;
}
//辅助数组，记录从顶点集U到V-U的代价最小的边的辅助数组
struct closed{
int adjvex;
int lowcost;
};
closed closedge[MAX_V_N];
//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输入T的各条边
void MiniSpanTree_PRIM(MGraph G,int u){
int k=u;int i,j;
for( i=0;i<G.vexnum;i++) //初始化数组
if(i!=k){
closedge[i].adjvex=u+1;
if(!G.arcs[k][i].adj)
closedge[i].lowcost=-1;
else
closedge[i].lowcost=G.arcs[k][i].adj;
}
closedge[k].lowcost=0;
for(i=0;i<G.vexnum-1;i++){ //选自其余G.vexnum-1各顶点
for(j=0;j<G.vexnum;j++){
if(closedge[j].lowcost>0){ //求出T的下一个结点：第k结点
k=j; break;
}
}
for(j=0;j<G.vexnum;j++){
if(closedge[j].lowcost>0)
if(closedge[j].lowcost<closedge[k].lowcost)
k=j;
}
printf("%d-%d->%d,",closedge[k].adjvex,closedge[k].lowcost,G.vexs[k]);
//输出生成边
closedge[k].lowcost=0; //第k个顶点并入U集
for(j=0;j<G.vexnum;j++)
if(G.arcs[k][j].adj){ //新顶点并入U后重新选择最小边
if(closedge[j].lowcost==-1){
closedge[j].lowcost=G.arcs[k][j].adj; closedge[j].adjvex=G.vexs[k];
}
else
if(G.arcs[k][j].adj<closedge[j].lowcost){
closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
//---------
int main()
{
int i,j;
MGraph G;
CreateMarph(G);
for( i=0;i<G.vexnum;i++){
for( j=0;j<G.vexnum;j++){
printf("%d ",G.arcs[i][j].adj);
}
printf("\n");
}
printf("一个最小生成树为：\n");
MiniSpanTree_PRIM(G,0);
printf("\n");
system("PAUSE");
return 0;
}