最小生成树kruskal算法-数据结构课程设计|数据结构课程设计
/*Name:最小生成树kruskal算法Author:wujilinDescription:用邻接矩阵做图Date: 21-07-06 23:07Copyright:wujilin*/
#include
#include#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请输入有边的2个顶点");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;}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=965291
