#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> using namespace std; #define max_name 5 #define max_vertex_num 20 //权的上限值 typedef char vertex[max_name];//顶点名字串 typedef int adjmatrix[max_vertex_num][max_vertex_num];//邻接矩阵 typedef struct //定义图 { vertex vexs[max_vertex_num]; adjmatrix arcs; int vexnum,arcnum ; }Graph;
typedef struct { vertex adjvex;//当前点 int lowcost;//代价 }minside[max_vertex_num];
int locatevex(Graph g,vertex u)//定位 { int i ; for (i=0;i<g.vexnum ;++i) if(strcmp(u,g.vexs[i])==0) return i; return -1; }
void creategraph(Graph &g) { int i,j,k,w; vertex va,vb; printf("请无向图g的顶点数和边数(以空格为分隔)n"); //scanf("%d %d",&g.vexnum,&g.arcnum ); cin>>g.vexnum>>g.arcnum; printf("请输入%d个顶点的值(<%d个字符):n",g.vexnum,max_name); for(i=0;i<g.vexnum ;++i)//构造顶点集 //scanf("%s",g.vexs[i]); cin>>g.vexs[i]; for(i=0;i<g.vexnum;++i) for(j=0;j<g.vexnum;++j)//初始化邻接矩阵 g.arcs[i][j]=100; printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔):n",g.arcnum); for(k=0;k<g.arcnum;++k) { //scanf("%s%s%d%*c",va,vb,&w); cin>>va>>vb>>w; i=locatevex(g,va); j=locatevex(g,vb); g.arcs[i][j]=g.arcs[j][i]=w; } }//对称
int minimum(minside sz,Graph g) { int i=0,min; while(!sz[i].lowcost) i++; min=sz[i].lowcost;//将最小权值记在min中 k=i;//把与边关联的生成树外的定点序号记在k中 for(j=i+1;j<g.vexnum;j++) if(sz[j].lowcost>0&&min>sz[j].lowcost ) { min=sz[j].lowcost ; k=j; } return k; }
void minispantree_prim(Graph g,vertex u) { int i,k; minside closedge ; k=locatevex(g,u); for(j=0;j<g.vexnum ;++j) { strcpy(closedge[j].adjvex,u); closedge[j].lowcost = g.arcs[k][j]; } closedge[k].lowcost =0;//将顶点vk加入生成树中 printf("最小代价生成树的各条边为:n"); for(i=1;i<g.vexnum ;++i) { k=minimum(closedge,g); //printf("(%d-%d)n",closedge[k].adjvex,g.vexs[k]);//输出最小边及权值 cout<<closedge[k].adjvex<<"-"<<g.vexs[k]<<endl; closedge[k].lowcost = 0; for(j=0;j<g.vexnum ;++j) if(g.arcs[k][j]>0&&g.arcs[k][j]<closedge[j].lowcost ) { strcpy(closedge[j].adjvex,g.vexs[k]); closedge[j].lowcost=g.arcs[k][j]; } } }//修改权值域
int main() { Graph g ; creategraph(g); minispantree_prim(g,g.vexs[0]);
return 0 ; } (编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|