最小生成树（MST）介绍及C/C++代码

文章目录

• 前言
• 一、最小生成树是什么？
• 二、最小生成树的算法
• • 1、Prim算法
  • 2、Kruskal算法
• 总结

---

前言

  最小生成树也是在路由算法设计中常用到的一种树，其可保证全局的权重和最小。如果权重和路径大小成正比，那其也可保证全局的路径和最小，因此是定量数据传输方式钟爱的路由树。接下来，让我们一起学习一下吧~

---

一、最小生成树是什么？

  最小生成树，全称是Minimum Spanning Tree，简称为MST，其具体定义如下：
  在一给定的无向图$G=(V,E)$ 中，$(u,v)$ 代表连接顶点$u$与顶点$v$的边，而$w(u,v)$代表此边的权重。若存在$T$为$E$的子集且为无循环图，使得联通所有结点的的$w(T)$最小，则此$T$为$G$的最小生成树。即：$$w(t)=\sum _{(u,v)\in t}w(u,v)$$
  因此，最小生成树其实是最小权重生成树的简称。
  以上内容参考自百度百科，网址如下：

/item/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91/5223845?fr=aladdin

二、最小生成树的算法

1、Prim算法

（1）输入：一个加权连通图$G=(V,E)$ ，其中顶点集合为$V$，边集合为$E$；
（2）初始化：$V_{new}=x$，其中$x$为集合$V$中的任一节点（起始点），$E_{new}$为空；
（3）重复下列操作，直到$V_{new}=V$：
a.在集合$E$中选取权值最小的边$<u,v>$，其中$u$为集合$V_{new}$中的元素，而$v$不在$V_{new}$集合当中，并且$v\in V$（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将$v$加入集合$V_{new}$中，将$<u,v>$边加入集合$E_{new}$中；
（4）输出：使用集合$V_{new}$和$E_{new}$来描述所得到的最小生成树。
以上算法讲解同样参考百度百科，其C/C++代码实现如下：

#include <>
#define MAXINT (0X7FFF7FFF)
#define VER_LEN (101)
typedef struct {
    int cost;
    int flag;
    int pre;
} vertex;

int Graph[VER_LEN][VER_LEN];
vertex Vertex[VER_LEN];

// 初始化图的数据，初始化为两点之间互不连接
void init_graph(int length) {
    int i, j;
    for(i = 1; i <= length; i++)
      for(j = 1; j <= length; j++)
        Graph[i][j] = MAXINT;
}

void prim(int start, int length) {
    int i,j;
    int min_cost, min_v;

    // 根据初始顶点start，初始为各顶点的相关信息
    // cost表示权重，flag表示是否已经加入最小生成树，pre表示其parent节点
    for(i = 1; i <= length; i++) {
        Vertex[i].cost = Graph[start][i];
        Vertex[i].flag = 0;
        Vertex[i].pre = start;
    }

    // 将初始顶点加入到最小生成树中
    Vertex[start].cost = 0;
    Vertex[start].flag = 1;

    for(i = 2; i <= length; i++) {
        min_cost = MAXINT;
        // 找出cost最小的边
        for(j = 1; j <= length; j++) {
            if(Vertex[j].flag == 0 && Vertex[j].cost < min_cost) {
                min_cost = Vertex[j].cost;
                min_v = j;
            }
        }

        // 将上面找出来的cost最小的边的顶点加入到最小生成树中
        Vertex[min_v].flag = 1;

        // 根据上面新加入到最小生成树的顶点调整各顶点的cost值
        for(j = 1; j <= length; j++) {
            if(Vertex[j].flag == 0 && Vertex[j].cost > Graph[min_v][j]) {
                Vertex[j].cost = Graph[min_v][j];
                Vertex[j].pre = min_v;
            }
        }
    }
}

int main() {
    int i;
    int ver_num, edge_num;
    int edge_u, edge_v, cost;

    printf("输入顶点数和边数：\n");
    scanf("%d %d", &ver_num, &edge_num);
    init_graph(ver_num);
    
    printf("输入图的信息：\n");
    for(i = 1; i <= edge_num; i++) {
        scanf("%d %d %d", &edge_u, &edge_v, &cost);
        Graph[edge_u][edge_v] = cost;
        Graph[edge_v][edge_u] = cost;
    }

    prim(1, ver_num);
    printf("prim算法输出最小生成树：\n");
    for(i = 2; i <= ver_num; i++)
        printf("%d to %d, the cost is %d\n", Vertex[i].pre, i, Vertex[i].cost);
    return 0;
}

2、Kruskal算法

  假设 $W_n=(V,E)$是一个含有$n$个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：
  先构造一个只含$n$个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有$n$棵树的一个森林。之后，从网的边集$E$中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有$n-1$条边为止。
  以上算法讲解同样参考百度百科，其C/C++代码实现如下：

#include <>
#define VER_LEN (101)
#define EDGE_LEN (10001)
typedef struct {
    int u,v,cost;
}edge;

edge Edge[EDGE_LEN];
int Parent[VER_LEN];
int Size[VER_LEN];
int Flag[VER_LEN];

// 排序，按照边的权重，从小到大排序
void sort(int edge_num){
    int i,j;
    int temp_u, temp_v, temp_cost;

    for(i = 1; i < edge_num; i++) {
        for(j = 1; j <= edge_num - i; j++) {
            if(Edge[j].cost > Edge[j+1].cost) {
                temp_u = Edge[j].u;
                temp_v = Edge[j].v;
                temp_cost = Edge[j].cost;
                Edge[j].u = Edge[j+1].u;
                Edge[j].v = Edge[j+1].v;
                Edge[j].cost = Edge[j+1].cost;
                Edge[j+1].u = temp_u;
                Edge[j+1].v = temp_v;
                Edge[j+1].cost = temp_cost;
            }
        }
    }
}

void init(int ver_num) {
    int i;
    for(i=1; i<=ver_num; i++) {
        Parent[i]=i;// 将parent初始化为自身
        Size[i]=1;/*将size初始化为1，用于按秩压缩（
		如果不需要进行按秩压缩，不需要这个数组信息）*/
    }
}

int find(int vertex) {
    if(vertex != Parent[vertex]) {
        Parent[vertex]=find(Parent[vertex]);//路径压缩
    }
    return Parent[vertex];
}

int union_set(int i) {
    int parent_u = find(Edge[i].u);
    int parent_v = find(Edge[i].v);
    
    // 节点u和v已经在同一颗树上了
    if(parent_u == parent_v)     return 0;
    
    // 按秩压缩，将秩小一些的树加入到秩大一些的树
    if(Size[parent_u] > Size[parent_v]) {
        Parent[parent_v] = parent_u;
        Size[parent_u] += Size[parent_v];
    } else {
        Parent[parent_u] = parent_v;
        Size[parent_v] += Size[parent_u];
    }
    return 1;
}

void Kruskal(int ver_num, int edge_num) {
    int i,counter;

    // 排序，按照边的权重，从小到大排序
    sort(edge_num);

    // 进行初始化
    init(ver_num);

    counter = 0;
    // 按照边的权重，从小到大遍历所有的边
    // 直到编译完所有边，或者生成了最小生成树为止
    for(i = 1; i <= edge_num && counter < ver_num-1; i++) {
        // 当新加入的边会形成环时，需要舍弃
        if(union_set(i) == 0)    continue;
        
        // 将新加入的边的编号保存在Flag数组中，以便输入
        counter++;
        Flag[counter] = i;
    }
}

int main() {
    int i,ver_num, edge_num;
    printf("输入顶点数和边数：\n");
    scanf("%d %d", &ver_num, &edge_num);
    printf("输入图的信息：\n");
    for(i = 1; i <= edge_num; i++)
        scanf("%d %d %d", &Edge[i].u, &Edge[i].v, &Edge[i].cost);
        
    Kruskal(ver_num, edge_num);
    printf("Kruskal算法输出最小生成树：\n");
    for(i = 1; i < ver_num; i++)
        printf("%d to %d\n", Edge[Flag[i]].u, Edge[Flag[i]].v);
    return 0;
}

---

总结

  以上两个代码参考自网站：

/tags/

  同时，下面这个网址也有对这两种算法的具体讲解和C/C++代码，大家可自行查看：

/u013075699/article/details/80408067

  常用的也有这两种算法的matlab代码，在此给出几个建议的网址：

prim算法在matlab中的代码（好评不少）：
/download/z1149591130/4650761?utm_medium=distribute.pc_aggpage_search_result.none-task-download-2_{aggregatepage}first_rank_ecpm_v1~rank_v31_ecpm-3-4650761.pc_agg_new_rank&utm_term=matlab+prim%E7%AE%97%E6%B3%95&spm=1000.2123.3001.4430

matlab实现kruskal ：
/view/

基于并查集+Kruskal算法的matlab程序及最小生成树绘图：
https:///article/

  此次就分享这些内容，希望大家能够有所收获~