最小生成树

教学克鲁斯卡尔算法，这里临时补一下关于最小生成树的知识

引入：什么是最小生成树？

生成树

两个关键词：连通，无回路 —极小连通子图
边和顶点关系：n-1 n，路径唯一
边推点条件不充要（只是必要，但不充分）
深度，广度优先

T(G) 已经经过的
B(G) 未经过的
最小生成树
连通权值最小（最小代价生成树）
建立数学模型
应用：建立通信网建立城村道路（费用可以作为权值）
MST性质：
what is？
在生成树的构造过程中，图中n个顶点分属两个集合：

已落在生成树上的顶点集：U
尚未落在生成树上的顶点集：V-U接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
图片展示：
算法
克鲁斯卡尔（Kruskal）
普利姆
这里我主要讲的是前者

步骤：

首先将所有点添加到U中（即生成树点集上）
找边的权值最小的选择即可，但是直接选是比较麻烦的，可以创建一个数组去存储所有的边（随便使用一个排序，冒泡选择插入都是可以的）
过程中需要排查，如果出现环就对这条边舍去
依次类推，直至所有点都在一个连通分量上即可（这里可以用一个案例去演示）

演示案例：

使用iodraw所画

最后的结果：

但是最小生成树可以不唯一

适合： 稀疏图（选择边的方式）
时间复杂度：O(e loge) e是边数
比较：
普利姆算法就更适用于稠密图（选择点的方式）
时间复杂度：O(n^2) n为顶点数

算法实现

#include <stdio.h>
#include <stdlib.h>
#define N 9   // 图中边的数量
#define P 6   // 图中顶点的数量
//构建表示边的结构体
struct edge {
    //一条边有 2 个顶点
    int initial;
    int end;
    //边的权值
    int weight;
};

//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序
int cmp(const void* a, const void* b) {
    return  ((struct edge*)a)->weight - ((struct edge*)b)->weight;
}
//克鲁斯卡尔算法寻找最小生成树，edges 存储用户输入的图的各个边，minTree 用于记录组成最小生成树的各个边
void kruskal_MinTree(struct edge edges[], struct edge minTree[]) {
    int i, initial, end, elem, k;
    //每个顶点配置一个标记值
    int assists[P];
    int num = 0;
    //初始状态下，每个顶点的标记都不相同
    for (i = 0; i < P; i++) {
        assists[i] = i;
    }
    //根据权值，对所有边进行升序排序
    qsort(edges, N, sizeof(edges[0]), cmp);
    //遍历所有的边
    for (i = 0; i < N; i++) {
        //找到当前边的两个顶点在 assists 数组中的位置下标
        initial = edges[i].initial - 1;
        end = edges[i].end - 1;
        //如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
        if (assists[initial] != assists[end]) {
            //记录该边，作为最小生成树的组成部分
            minTree[num] = edges[i];
            //计数+1
            num++;
            elem = assists[end];
            //将新加入生成树的顶点标记全部改为一样的
            for (k = 0; k < P; k++) {
                if (assists[k] == elem) {
                    assists[k] = assists[initial];
                }
            }
            //如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
            if (num == P - 1) {
                break;
            }
        }
    }
}

void display(struct edge minTree[]) {
    int cost = 0, i;
    printf("最小生成树为:\n");
    for (i = 0; i < P - 1; i++) {
        printf("%d-%d  权值：%d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
        cost += minTree[i].weight;
    }
    printf("总权值为：%d", cost);
}

int main() {
    int i;
    struct edge edges[N], minTree[P - 1];
    for (i = 0; i < N; i++) {
        scanf("%d %d %d", &edges[i].initial, &edges[i].end, &edges[i].weight);
    }
    kruskal_MinTree(edges, minTree);
    display(minTree);
    return 0;
}

最小生成树

引入：什么是最小生成树？

生成树

最小生成树

MST性质：

算法

演示案例：

算法实现