zuixiaoshengchengshu.zip_site:www.pudn.com

/* Name:最小生成树kruskal算法 Author:wujilin Description:用邻接矩阵做图 Date: 21-07-06 23:07 Copyright:wujilin */ #include<stdio.h> #include<stdlib.h> #define M 20 #define MAX 20 typedef struct { int begin; int end; int weight; }edge; typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph; void CreatGraph(MGraph *);//函数申明 void sort(edge* ,MGraph *); void MiniSpanTree(MGraph *); int Find(int *, int ); void Swapn(edge *, int, int); void CreatGraph(MGraph *G)//构件图 { int i, j,n, m; printf("请输入边数和顶点数:"); scanf("%d %d",&G->arcnum,&G->vexnum); for (i = 1; i <= G->vexnum; i++)//初始化图 { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; } } for ( i = 1; i <= G->arcnum; i++)//输入边和权值 { printf("\n请输入第%d边的2个顶点",i); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求 请重新输入:"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("\n请输入%d与%d之间的权值:", n, m); scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } void sort(edge edges[],MGraph *G)//对权值进行排序 { int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); for (i = 1; i < G->arcnum; i++) { printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight); } } 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 MiniSpanTree(MGraph *G)//生成最小生成树 { int i, j, n, m; int k = 1; int parent[M]; edge edges[M]; for ( i = 1; i < G->vexnum; i++) { for (j = i + 1; j <= G->vexnum; j++) { if (G->arc[i][j].adj == 1) { edges[k].begin = i; edges[k].end = j; edges[k].weight = G->arc[i][j].weight; k++; } } } sort(edges, G); for (i = 1; i <= G->arcnum; i++) { parent[i] = 0; } printf("最小生成树为:\n"); for (i = 1; i <= G->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; 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; } int main(void)//主函数 { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf("memory allcation failed,goodbye"); exit(1); } CreatGraph(G); MiniSpanTree(G); system("pause"); return 0; }