kruskal3.cpp

最小生成树 最小生成树 最小生成树 Kruskal

#include <stdio.h>
#include <string.h>
 

#define maxnodenum 100
#define maxedgenum 100
typedef struct{
        int u, v, weight;
}edge;
edge edges[maxedgenum + 1];
int nodes[maxnodenum + 1];
static int compare(const void *x, const void *y);
int main(int argc, char **argv)
{
        int i, j, m, n, nodenum, edgenum, boolean, safe;
        int presult = 0, flag = 1, find = 0;

        printf("Input nodes and edges:\n");
        scanf("%d %d", &nodenum, &edgenum);
        getchar();

        printf("Input all edges:\n");
        for(i = 0; i < edgenum; i++){
                scanf("%d %d %d", &edges[i].u, &edges[i].v, \
                        &edges[i].weight);
                getchar();
        }
        qsort((void *)&edges[0], edgenum, sizeof(edge), compare);//sort all edge's weight in ascending


        for(i = 0; i < edgenum + 1; i++){
                if(presult == nodenum - 1){//found mst

                        find = 1;
                        break;
                }
                m = edges[i].u;
                n = edges[i].v;
                safe = 0;
                if(nodes[m] == 0 && nodes[n] == 0){
                        nodes[m] = nodes[n] = flag++;
                        safe = 1;//a safe edge

                }
                else if(safe == 0 && (nodes[m] == 0 || nodes[n] == 0)){
                        (nodes[m] == 0) ? (nodes[m] = nodes[n]) :(nodes[n] = nodes[m]);
                        safe = 1;//a safe edge

                }
                else if(safe == 0 && nodes[m] != nodes[n]){
                        for(j = 0; j < nodenum + 1; j++){
                                if(nodes[j] == nodes[m] || nodes[j] == nodes[n]){
                                        nodes[j] = flag;
                                }
                        }
                        flag++;
                        safe = 1;//a safe edge

                }

                if(safe == 1){//reserve a safe edge

                        edges[presult].u = m;
                        edges[presult].v = n;
                        edges[presult].weight = edges[i].weight; 
                        presult++;
                }
        }

        if(find == 1){//print the founded mst

                printf("Print the result:\n");
                for(i = 0; i < presult; i++){
                        printf("%d %d %d\n", edges[i].u, edges[i].v, edges[i].weight);
                }
        }
        return 0;
}

static int compare(const void *x, const void *y)
{
        return ( ((edge *)x)->weight - ((edge *)y)->weight );
}



/*Input nodes and edges:#此前在首页部分显示#
6 10
Input all edges:
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 5 6
3 6 4
4 6 2
4 3 5
5 6 6
Print the result:
1 3 1
4 6 2
2 5 3
3 6 4
2 3 5
*/