图——图的应用01最小生成树（Prim算法与Kruskal算法详解）

这篇文章就来讲一下图的最后的应用章节中的最小生成树，包括Prim算法与Kruskal算法两大部分，在实际问题当中应用很广。在对于前面的内容熟悉的情况下再学习本章比较好哦，图的基本概念，存储结构以及图的遍历。大家可以通过下面的链接再次学习：

图的定义和基本术语

图的类型定义和存储结构

图的遍历（DFS和BFS）

一，最小生成树

生成树：包含图G所有顶点的极小连通子图。

一个图可以有许多棵不同的生成树

所有生成树具有以下共同特点：

生成树的顶点个数与图的顶点个数相同;生成树是图的极小连通子图，去掉一条边则非连通；有n个顶点的连通图的生成树有n-1条边;再加一条边必然形成回路；任意两个顶点间的路径是唯一的。

例：

画出下图的生成树

因为图的遍历方式有两种，所以生成树也有两种方式DFS和BFS。

下面是一个最小生成树的典型用途：

欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n–1条线路，使总费用最少？

数学模型：

顶点———表示城市，有n个；

边————表示线路，有n–1条；

边的权值—表示线路的经济代价；

连通网——表示n个城市间通信网。

显然此连通网是一个生成树。

如何求最小生成树？

首先明确：

使用不同的遍历图的方法，可以得到不同的生成树

从不同的顶点出发，也可能得到不同的生成树。

按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。

目标：

在网的多个生成树中，寻找一个各边权值之和最小的生成树。

构造最小生成树的准则：

必须只使用该网中的边来构造最小生成树；

必须使用且仅使用n-1条边来联结网络中的n个顶点；

不能使用产生回路的边。

构造最小生成树(Minimum Cost Spanning Tree):构造最小生成树的算法很多，其中多数算法都利用了MST的性质。

利用MST性质，我们就得到了构造最小生成树的步骤：

在学习具体构造最小生成树的算法之前，我们需要先了解一下贪心算法。

贪心算法：

而求小生成树的两种算法都属于贪心算法

Prim（普里姆）算法：归并顶点，与边数无关，适于稠密网。

Kruskal（克鲁斯卡尔）算法：归并边，适于稀疏网。

普里姆算法

我们通过一个例子来理解：

下面是prim算法的代码实现：

其中`limits.h` 头文件在C语言中用于定义一些与系统相关的常量，包括整数类型的最大值和最小值。在代码中，`limits.h` 头文件被用来定义 `INT_MAX`，这是一个常量，表示 `int` 类型的最大值，`INT_MAX` 被用来初始化 `key` 数组，表示所有顶点初始时都未被访问。具体来说，`key` 数组用于存储每个顶点到生成树的最小距离，初始时所有顶点的距离都被设置为 `INT_MAX`，表示它们都未被访问。

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

#define V 5

// 函数：找到未加入最小生成树的顶点中，距离最小的顶点
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    // 遍历所有顶点，找到未加入最小生成树的顶点中，距离最小的顶点
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[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 key[V];
    bool mstSet[V];

    // 初始化所有顶点的距离为无穷大，所有顶点未加入最小生成树
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    // 起始顶点的距离为0，父节点为-1
    key[0] = 0;
    parent[0] = -1;

    // 遍历所有顶点，构建最小生成树
    for (int count = 0; count < V - 1; count++) {
        // 找到未加入最小生成树的顶点中，距离最小的顶点
        int u = minKey(key, mstSet);
        // 将该顶点加入最小生成树
        mstSet[u] = true;
        // 更新与该顶点相邻的顶点的距离和父节点
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][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;
}

输出结果：

克鲁斯卡尔算法

下面用一个例子来理解克鲁斯卡尔算法的过程：

下面是c语言中克鲁斯卡尔算法的代码实现：

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

#define MAX_VERTICES 100

// 定义边结构体
typedef struct {
    int u, v, weight;
} Edge;

// 定义并查集结构体
typedef struct {
    int parent[MAX_VERTICES];
    int rank[MAX_VERTICES];
} DisjointSet;

// 初始化并查集
void makeSet(DisjointSet *ds, int n) {
    for (int i = 0; i < n; i++) {
        ds->parent[i] = i;
        ds->rank[i] = 0;
    }
}

// 查找并查集的根节点
int find(DisjointSet *ds, int x) {
    if (ds->parent[x] != x) {
        ds->parent[x] = find(ds, ds->parent[x]);
    }
    return ds->parent[x];
}

// 合并两个集合
void unionSet(DisjointSet *ds, int x, int y) {
    int rootX = find(ds, x);
    int rootY = find(ds, y);

    if (rootX != rootY) {
        if (ds->rank[rootX] < ds->rank[rootY]) {
            ds->parent[rootX] = rootY;
        } else if (ds->rank[rootX] > ds->rank[rootY]) {
            ds->parent[rootY] = rootX;
        } else {
            ds->parent[rootY] = rootX;
            ds->rank[rootX]++;
        }
    }
}

// 比较函数，用于排序边
int compare(const void *a, const void *b) {
    Edge *edgeA = (Edge *)a;
    Edge *edgeB = (Edge *)b;
    return edgeA->weight - edgeB->weight;
}

// 克鲁斯卡尔算法
void kruskal(Edge edges[], int n, int m) {
    qsort(edges, m, sizeof(Edge), compare);

    DisjointSet ds;
    makeSet(&ds, n);

    int mstWeight = 0;
    printf("Edges in the minimum spanning tree:");
    for (int i = 0; i < m && mstWeight < n - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].weight;

        if (find(&ds, u) != find(&ds, v)) {
            printf("%d -- %d == %d", u, v, w);
            unionSet(&ds, u, v);
            mstWeight++;
        }
    }
}

int main() {
    int n = 4; // 图中顶点的数量
    int m = 5; // 图中边的数量
    Edge edges[] = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};

    kruskal(edges, n, m);
    return 0;
}

输出结果：