最小生产树.c

Kruscal算法实现产生最小生成树

#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int begin;
    int end;
    int weight;
}edge;
typedef struct{
    int adj;
    int weight;
}AdjMatrix;
typedef struct{
    AdjMatrix arc[20][20];
    int vexnum, arcnum;
}MGraph;
void Change(edge *,int , int);
int MFset(int *, int );
void input(MGraph *G)
{
 int i, j,n, m;
 printf("Please input the number of edges:");
 scanf("%d",&G->arcnum);
 getchar();
 printf("Please input the number of vertexs:");
 scanf("%d",&G->vexnum);
 getchar();
    for (i = 1; i <= G->vexnum; i++)
        for ( j = 1; j <= G->vexnum; j++)
            G->arc[i][j].adj= 0;
    for ( i = 1; i <= G->arcnum; i++)
    {
        printf("\nPlease input the start vertexs of edge:");
        scanf("%d",&n);
        getchar();
        while(n < 0 || n > G->vexnum)
        {
            printf("Error!\n");
            printf("Please input the start vertexs of edge again:");
            scanf("%d",&n);
            getchar();
        }
        printf("Please input the end vertexs of edge:");
        scanf("%d",&m);
        getchar();
        while(m < 0 || m > G->vexnum||m==n)
        {
            printf("Error!\n");
            printf("Please input the end vertexs of edge again:");
            scanf("%d",&m);
            getchar();
        }
        if(n<m)
        {
            G->arc[n][m].adj=1;
            //getchar();
            printf("\nPlease input the weight of the edge %d-%d :", n, m);
            scanf("%d",&G->arc[n][m].weight);
        }
        else
        {
            G->arc[m][n].adj=1;
            getchar();
            printf("\nPlease input the weight of the edge %d-%d :", n, m);
            scanf("%d",&G->arc[m][n].weight);
        }
    }
}
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)
                Change(edges, i, j);
}
void Change(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 KRUSCAL(MGraph *G)
{
    int i, j, n, m;
    int k = 1;
    int parent[20];
    edge edges[20];
    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("The MiniSpanTree is:\n");
    for (i = 1; i <= G->arcnum; i++)
    {
        n = MFset(parent, edges[i].begin);
        m = MFset(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 MFset(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 error!");
        exit(0);
    }
    input(G);
    KRUSCAL(G);
    free(G);
    return 0;
}