最小生成树kruskal算法

0 4 5 7 0 0 0 0 4 0 0 8 16 0 0 0 15 0 0 1 0 14 0 0 7 8 1 0 13 3 2 0 0 16 0 13 0 0 12 0 0 0 14 3 0 0 11 9 0 0 0 2 12 11 0 10 0 0 0 0 0 9 10 0 /*

Name:最小生成树kruskal算法 Author:wujilin

Description:用邻接矩阵做图 Date: 21-07-06 23:07 Copyright: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\

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\

while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) {

printf(\"输入的数字不符合要求 请重新输入:\");

scanf(\"%d%d\ }

G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar();

printf(\"\\n请输入%d与%d之间的权值:\n, m);

scanf(\"%d\ }

printf(\"邻接矩阵为:\\n\");

for ( i = 1; i <= G->vexnum; i++) {

for ( j = 1; j <= G->vexnum; j++) {

printf(\"%d \ }

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; }

请输入边数和顶点数:14 8 请输入有边的2个顶点1 2 请输入1与2之间的权值:4 请输入有边的2个顶点1 3 请输入1与3之间的权值:5 请输入有边的2个顶点1 4 请输入1与4之间的权值:7 请输入有边的2个顶点2 4 请输入2与4之间的权值:8 请输入有边的2个顶点2 5 请输入2与5之间的权值:16 请输入有边的2个顶点3 4 请输入3与4之间的权值:1 请输入有边的2个顶点3 6 请输入3与6之间的权值:14 请输入有边的2个顶点4 5 请输入4与5之间的权值:13 请输入有边的2个顶点4 6

请输入4与6之间的权值:3 请输入有边的2个顶点4 7 请输入4与7之间的权值:2 请输入有边的2个顶点5 7 请输入5与7之间的权值:12 请输入有边的2个顶点6 7 请输入6与7之间的权值:11 请输入有边的2个顶点6 8 请输入6与8之间的权值:9 请输入有边的2个顶点7 8 请输入7与8之间的权值:10 邻接矩阵为: 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 权排序之后的为: << 3, 4 >> 1 << 4, 7 >> 2 << 4, 6 >> 3 << 1, 2 >> 4 << 1, 3 >> 5 << 1, 4 >> 7 << 2, 4 >> 8 << 6, 8 >> 9 << 7, 8 >> 10 << 6, 7 >> 11 << 5, 7 >> 12 << 4, 5 >> 13 << 3, 6 >> 14 最小生成树为: << 3, 4 >> 1 << 4, 7 >> 2 << 4, 6 >> 3 << 1, 2 >> 4 << 1, 3 >> 5 << 6, 8 >> 9 << 5, 7 >> 12 请按任意键继续. . .