C语言实现最小生成树算法：Prim和Kruskal-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言实现最小生成树算法：Prim和Kruskal。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

以下是使用C语言实现Prim算法生成最小生成树的代码：

#include <stdio.h>
#include <limits.h>

#define V 5 // 图中顶点的个数

// 找到顶点集合中未访问的顶点中距离最小的顶点
int minDistance(int dist[], int visited[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++) {
        if (!visited[v] && dist[v] < min) {
            min = dist[v];
            min_index = v;
        }
    }

    return min_index;
}

// 打印生成的最小生成树
void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

// 使用Prim算法生成最小生成树
void primMST(int graph[V][V]) {
    int parent[V]; // 用于存储最小生成树中的父节点
    int dist[V]; // 用于存储顶点到最小生成树的距离
    int visited[V]; // 用于存储顶点是否已被访问

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }

    dist[0] = 0; // 选定第一个顶点作为根节点
    parent[0] = -1; // 根节点没有父节点

    for (int count = 0; count < V-1; count++) { // 需要选择V-1个边
        int u = minDistance(dist, visited); // 找到距离最小的顶点
        visited[u] = 1; // 标记已访问

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v] && graph[u][v] < dist[v]) {
                // 如果顶点未访问过且与u相邻的边的权重小于dist[v]
                parent[v] = u; // 将u作为v的父节点
                dist[v] = graph[u][v]; // 更新dist[v]
            }
        }
    }

    printMST(parent, graph); // 打印生成的最小生成树
}

int main() {
    int graph[V][V] = {{0, 2, 0, 6, 0},
                       {2, 0, 3, 8, 5},
                       {0, 3, 0, 0, 7},
                       {6, 8, 0, 0, 9},
                       {0, 5, 7, 9, 0}};
    // 以邻接矩阵的形式表示图

    primMST(graph); // 生成最小生成树

    return 0;
}

注释如下：

#include <stdio.h> 和 `#include
#define V 5 定义了图中顶点的个数为5。
int minDistance(int dist[], int visited[]) 函数用于找到顶点集合中未访问的顶点中距离最小的顶点。输入参数 dist 用于存储顶点到最小生成树的距离，输入参数 visited 用于存储顶点是否已被访问。
int min = INT_MAX, min_index; 定义 min 和 min_index 用于存储距离最小的顶点。
for (int v = 0; v < V; v++) 循环遍历所有顶点。
if (!visited[v] && dist[v] < min) 如果顶点未访问过且距离小于 min。
min = dist[v]; min_index = v; 更新距离最小的顶点。
return min_index; 返回距离最小的顶点。
void printMST(int parent[], int graph[V][V]) 函数用于打印生成的最小生成树。输入参数 parent 用于存储最小生成树中的父节点，输入参数 graph 用于表示图。
printf(“Edge \tWeight\n”); 打印表头。
for (int i = 1; i < V; i++) 循环遍历所有顶点，从第二个顶点开始。
printf(“%d - %d \t%d \n”, parent[i], i, graph[i][parent[i]]); 打印边的信息。
void primMST(int graph[V][V]) 函数用于使用Prim算法生成最小生成树。输入参数 graph 用于表示图。
int parent[V], dist[V], visited[V]; 定义 parent，dist 和 visited 数组用于存储最小生成树中的父节点、顶点到最小生成树的距离和顶点是否已被访问。
for (int i = 0; i < V; i++) 初始化 dist 和 visited 数组。
dist[0] = 0; parent[0] = -1; 选定第一个顶点作为根节点，根节点没有父节点。
for (int count = 0; count < V-1; count++) 需要选择V-1个边。
int u = minDistance(dist, visited); visited[u] = 1; 找到距离最小的顶点，并标记已访问。
for (int v = 0; v < V; v++) 循环遍历所有顶点。
if (graph[u][v] && !visited[v] && graph[u][v] < dist[v]) 如果顶点未访问过且与u相邻的边的权重小于dist[v]。
parent[v] = u; dist[v] = graph[u][v]; 更新最小生成树中的父节点和顶点到最小生成树的距离。
printMST(parent, graph); 打印最小生成树。
int main() 主函数。
int graph[V][V] = {{0, 2, 0, 6, 0}, 定义图。
primMST(graph); 使用Prim算法生成最小生成树。

以上是Prim算法的C语言代码和相关讲解和注释，希望能对你有所帮助。

以下是Kruskal算法的C语言代码和注释：文章来源地址https://www.toymoban.com/news/detail-769501.html

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_EDGE_NUM 100   // 最大边数

// 边的结构体，包含起点、终点和边权重值
typedef struct {
  int u, v;   // 边的起点和终点
  int weight; // 边的权重值
} Edge;

// 图的结构体，包含顶点数、边数和边的集合
typedef struct {
  int vexnum, edgenum; // 图的顶点数和边数
  Edge edges[MAX_EDGE_NUM]; // 图的边的集合
} Graph;

// 并查集的结构体
typedef struct {
  int *parent; // 并查集的父节点数组
  int size;    // 并查集的大小
} UnionFind;

// 初始化并查集
void initUnionFind(UnionFind *uf, int size) {
  uf->size = size;
  uf->parent = (int *)malloc(sizeof(int) * size);

  // 将每个节点的父节点初始化为自身
  for (int i = 0; i < size; i++) {
    uf->parent[i] = i;
  }
}

// 查找节点的祖先节点
int find(UnionFind *uf, int x) {
  if (uf->parent[x] == x) {
    return x;
  } else {
    // 路径压缩
    uf->parent[x] = find(uf, uf->parent[x]);
    return uf->parent[x];
  }
}

// 合并两个集合
void unionSet(UnionFind *uf, int x, int y) {
  int x_root = find(uf, x);
  int y_root = find(uf, y);

  if (x_root != y_root) {
    uf->parent[x_root] = y_root;
  }
}

// 比较两个边的权重值，用于排序
int cmp(const void *a, const void *b) {
  Edge *e1 = (Edge *)a;
  Edge *e2 = (Edge *)b;
  return e1->weight - e2->weight;
}

// Kruskal算法生成最小生成树
void kruskal(Graph *graph) {
  UnionFind uf;
  initUnionFind(&uf, graph->vexnum); // 初始化并查集

  int count = 0;
  Edge result[MAX_EDGE_NUM]; // 保存最小生成树的边集合

  // 对边进行排序
  qsort(graph->edges, graph->edgenum, sizeof(Edge), cmp);

  // 依次选择每一条边，如果两个端点不在同一个集合中，则将它们合并，并将边加入最小生成树的边集合中
  for (int i = 0; i < graph->edgenum; i++) {
	Edge e = graph->edges[i];
	if (find(&uf, e.u) != find(&uf, e.v)) {
  unionSet(&uf, e.u, e.v);
  result[count++] = e;
}

// 如果已经找到了n-1条边，就可以停止了
if (count == graph->vexnum - 1) {
  break;
}
}

// 输出最小生成树的边集合
printf("The minimum spanning tree:\n");
for (int i = 0; i < count; i++) {
printf("(%d, %d): %d\n", result[i].u, result[i].v, result[i].weight);
}
}

int main() {
Graph graph;
printf("Please input the number of vertices and edges:\n");
scanf("%d%d", &graph.vexnum, &graph.edgenum);

// 读入每一条边的起点、终点和权重值
printf("Please input each edge's start vertex, end vertex and weight:\n");
for (int i = 0; i < graph.edgenum; i++) {
scanf("%d%d%d", &graph.edges[i].u, &graph.edges[i].v, &graph.edges[i].weight);
}

kruskal(&graph); // 生成最小生成树

return 0;
}