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