#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef struct { int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; typedef struct { int begin; int end; int weight; }Edge; /* 对边集数组Edge结构的定义 */ /* 构件图 */ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges=15; G->numVertexes=9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < G->numVertexes; j++) { if (i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } G->arc[0][1]=10; G->arc[0][5]=11; G->arc[1][2]=18; G->arc[1][8]=12; G->arc[1][6]=16; G->arc[2][8]=8; G->arc[2][3]=22; G->arc[3][8]=21; G->arc[3][6]=24; G->arc[3][7]=16; G->arc[3][4]=20; G->arc[4][7]=7; G->arc[4][5]=26; G->arc[5][6]=17; G->arc[6][7]=19; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /* 交换权值 以及头和尾 */ void Swapn(Edge *edges,int i, int j) { int temp; temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } /* 对权值进行排序 */ void sort(Edge edges[],MGraph *G) { int i, j; for ( i = 0; i < G->numEdges; i++) { for ( j = i + 1; j < G->numEdges; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); for (i = 0; i < G->numEdges; i++) { printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight); } } /* 查找连线顶点的尾部下标 */ int Find(int *parent, int f) { while ( parent[f] > 0) { f = parent[f]; } return f; } /* 生成最小生成树 */ void MiniSpanTree_Kruskal(MGraph G) { int i, j, n, m; int k = 0; int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */ Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */ /* 用来构建边集数组并排序********************* */ for ( i = 0; i < G.numVertexes-1; i++) { for (j = i + 1; j < G.numVertexes; j++) { if (G.arc[i][j]<INFINITY) { edges[k].begin = i; edges[k].end = j; edges[k].weight = G.arc[i][j]; k++; } } } sort(edges, &G); /* ******************************************* */ for (i = 0; i < G.numVertexes; i++) parent[i] = 0; /* 初始化数组值为0 */ printf("打印最小生成树:\n"); for (i = 0; i < G.numEdges; i++) /* 循环每一条边 */ { n = Find(parent,edges[i].begin); m = Find(parent,edges[i].end); if (n != m) /* 假如n与m不等,说明此边没有与现有的生成树形成环路 */ { parent[n] = m; /* 将此边的结尾顶点放入下标为起点的parent中。 */ /* 表示此顶点已经在生成树集合中 */ printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight); } } } int main(void) { MGraph G; CreateMGraph(&G); MiniSpanTree_Kruskal(G); return 0; }