--------------------------------------------------------------------------------------------------------------------------------
代码：（C语言实现）
#include<stdio.h> #include<stdlib.h> #include<limits.h> #define ERROR 0 #define OK 1 #define INFINITY INT_MAX //最大值 #define MAX_VERTEX_NUM 21 //最大顶点个数 #define MAX 20 typedef enum{ DG,DN,UDG,UDN } GraphKind; //{有向图，有向网，无向图，无向网} //--------图的数组（邻接矩阵）存储表示------// typedef struct ArcCell{ int adj; // int 可用 VRType代替 ，VRType是顶点关系类型。对无权图，用1或者0 // 表示相邻否； 对带权图，则为权值类型 // InforType *info; //该弧相关信息指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ char vexs[MAX_VERTEX_NUM]; //顶点向量 书中用 VertexType 代替 char AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph; //----------------------------------------// typedef struct{ char adjvex; int lowcost; }closedges[MAX_VERTEX_NUM]; //求最小生成树中的辅助数组 typedef struct EdgeData { char start; //起始点 char end; //终点 int weight; //权重 }EGraph; //邻接矩阵顶点定位 int LocateVex(MGraph G,char v){ int m; for(m=1;m<=G.vexnum;m++) if(G.vexs[m]==v) return m; return ERROR; return OK; } //创建无向网邻接矩阵 int CreatGraph(MGraph &G){ int i,j,k,w; char x,y; printf("请输入邻接矩阵： 顶点的个数 、弧的个数："); scanf("%d %d",&G.vexnum,&G.arcnum); //构造顶点向量 if(G.vexnum>20){ //顶点个数过多 printf("你输入的顶点个数超过最大值"); return ERROR; } printf("请输入 %d 个顶点的值",G.vexnum); for(i=1;i<=G.vexnum;i++){ fflush(stdin); scanf("%c",&G.vexs[i]); //构造顶点向量的值 } for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=INT_MAX; //初始化 printf("请输入无向网的两个相邻的顶点 (x,y) 以及相应的权值 w ：\n");; for(k=1;k<=G.arcnum;k++){ fflush(stdin); scanf("%c %c %d",&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcs[i][j].adj=w; G.arcs[j][i].adj=G.arcs[i][j].adj; } return OK; } //输出邻接表 int OutGraph(MGraph G1){ int i,j; printf("无向网的邻接矩阵： \n"); for(i=1;i<=G1.vexnum;i++){ //将邻接矩阵输出 for(j=1;j<=G1.vexnum;j++){ if(G1.arcs[i][j].adj==INT_MAX) printf("#"); else printf("%d",G1.arcs[i][j].adj); } printf("\n"); } return OK; } int Minimun(MGraph G,closedges m){ int i,j,min=INFINITY; for(i=1;i<=G.vexnum;i++){ if(m[i].lowcost){ if(m[i].lowcost<min){ min=m[i].lowcost; j=i; } } } return j; } //对权重进行排序 int sort_edge(EGraph G1[],MGraph G){ int i,j; int dex=1; for(i=1;i<=G.arcnum;i++){ for(j=i;j<=G.arcnum;j++){ if(G.arcs[i][j].adj!=INT_MAX){ G1[dex].start=G.vexs[i]; G1[dex].end=G.vexs[j]; G1[dex].weight=G.arcs[i][j].adj; // printf("%c %c %d \n",G1[dex].start,G1[dex].end,G1[dex].weight); dex++; } } } for(i=1;i<=G.vexnum;i++){ for(j=i+1;j<=G.vexnum;j++){ if(G1[i].weight > G1[j].weight){ EGraph tmp=G1[i]; G1[i]=G1[j]; G1[j]=tmp; } } } for(i=1;i<=G.arcnum;i++){ printf("%c %c %d \n",G1[i].start,G1[i].end,G1[i].weight); } return OK; } static int get_position(MGraph G,char ch){ int i; for(i=1;i<=G.vexnum;i++) if(G.vexs[i]==ch) return i; return -1; } //得到字符在数组中的位置 int get_end(int vends[],int i){ while(vends[i]!=0) i=vends[i]; return i; } //使用克鲁斯卡尔算法 int kruskal(MGraph G){ int i; int p1,p2,m,n; int index=0; EGraph G1[MAX]; EGraph rets[MAX]; int vends[MAX]={0}; sort_edge(G1,G); //进行排序 for(i=1;i<=G.arcnum;i++){ p1=get_position(G,G1[i].start); p2=get_position(G,G1[i].end); m=get_end(vends,p1); n=get_end(vends,p2); printf("m= %d,n= %d \n",m,n); if(m!=n){ vends[m]=n; rets[index]=G1[i]; index++; } } int length=0; for(i=0;i<index;i++){ printf("%d ",rets[i].weight); length=length+rets[i].weight; } printf("Kruskal = %d \n",length); for(i=0;i<index;i++) printf("%c-%c ",rets[i].start,rets[i].end); printf("\n"); return OK; } //用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T ，输出T的各条边 //记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义 int CreatMinTree(MGraph G){ char u; int i,j,k; closedges closedge; printf("请输入第一个顶点："); fflush(stdin); scanf("%c",&u); printf("无向网的最小生成树：\n"); k=LocateVex(G,u); for(j=1;j<=G.vexnum;j++){ //辅助数组初始化 if(j!=k){ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j].adj; } } closedge[k].lowcost=0; for(i=2;i<=G.vexnum;i++){ k=Minimun(G,closedge); printf("%c-%c ",closedge[k].adjvex,G.vexs[k]); closedge[k].lowcost=0; for(j=1;j<=G.vexnum;j++) if(G.arcs[k][j].adj<closedge[j].lowcost){ //新顶点并入 U 后重新选择最小边 closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j].adj; } } return OK; } void main(){ MGraph G; CreatGraph(G); OutGraph(G); CreatMinTree(G); printf("\n"); kruskal(G); }