kruskal算法c语言

实现

以下是kruskal算法的C语言实现示例：

#include <stdio.h>
#include <stdlib.h>

#define MAX_EDGES 1000
#define MAX_VERTEXS 100

struct Edge {
  int u, v, w;
};

// 按权重从小到大排序边
void sort_edges(struct Edge *e, int num_edges) {
  int i, j;
  for(i = 0; i < num_edges - 1; i++) {
    for(j = i + 1; j < num_edges; j++) {
      if(e[i].w > e[j].w) {
        struct Edge tmp = e[i];
        e[i] = e[j];
        e[j] = tmp;
      }
    }
  }
}

// 查找节点所在的连通分量
int find(int *parent, int i) {
  while(parent[i] != i)
    i = parent[i];
  return i;
}

// 合并两个连通分量
void merge(int *parent, int u, int v) {
  parent[find(parent, u)] = find(parent, v);
}

void kruskal(struct Edge *e, int num_vertexs, int num_edges) {
  int i, j;
  // 由于最多只需连接n-1条边，所以最多只要n-1个连通分量
  int parent[MAX_VERTEXS];
  for(i = 0; i < num_vertexs; i++)
    parent[i] = i;

  sort_edges(e, num_edges);

  printf("Kruskal最小生成树的边：\n");
  for(i = 0, j = 0; i < num_edges && j < num_vertexs - 1; i++) {
    int u = e[i].u, v = e[i].v, w = e[i].w;
    if(find(parent, u) != find(parent, v)) {
      printf("%d-%d weight:%d\n", u, v, w);
      merge(parent, u, v);
      j++;
    }
  }
}

int main() {
  int i, num_edges, num_vertexs;
  struct Edge edges[MAX_EDGES];
  
  printf("输入顶点数：");
  scanf("%d", &num_vertexs);
  
  printf("输入边数：");
  scanf("%d", &num_edges);

  printf("输入每条边的起点、终点、权重：\n");
  for(i = 0; i < num_edges; i++) {
    scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
  }

  kruskal(edges, num_vertexs, num_edges);

  return 0;
}

需要注意的是，上述实现中的权重w必须为非负整数，否则可能导致算法无法正确工作。