C++：图的最小生成树

一、简介

连通图的生成树是包含图中全部顶点的一个极小连通子图。极小的含义是包含全部顶点的连通子图中，边数最小的子图。一颗具有n个顶点的生成树，有且仅有n-1条边。显然，生成树可能不唯一。

无向连通网的生成树上各边的权值之和称为该生成树的代价，在图的所有生成树中，代价最小的生成树称为最小生成树。

最小生成树的概念可以应用到许多实际问题中，例如，在n个城市之间建造通信网络，至少需要假设n-1条通信线路，每两个城市之间架设通信线路的造假是不一样的，如何设计才能使得总造价最小？如果用图的顶点表示城市，用边上的权值表示建造城市之间的通信线路所需的费用，则最小生成树给出了建造通信网络的最优方案。

本文将介绍两种求最小生成树的算法——Prim算法和Kruskal算法。

二、Prim算法

Prim算法是用来求解无向图的最小生成树的一种贪心算法。

它的基本思想是：从一个任意节点出发，逐步选择边来连接未被访问的节点，使得当前生成树的边的权值之和最小，直到所有节点都被连接为止。

Prim算法适用于求稠密网的最小生成树，其步骤大致如下：

选择一个起始点：选择一个任意的节点作为最小生成树的初始点，可以取第一个节点（0）。
扩展树的边：从已选节点开始，选择最小的边，并将其加入生成树。
更新权值：在加入新节点后，更新现有生成树到其他未加入节点的最小边的权值。
重复以上步骤，直到所有节点都被加入生成树。

#include <iostream>
using namespace std;
#include <vector>           //使用vector要用//图的邻接矩阵（0表示无边，非0值表示边的权重/距离）
vector<vector<int>> edge={{ 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 }};
//图的顶点个数
int vertex_num=5;//功能：找出带最小权值的边的未访问顶点
//参数：1.权值数组；2.顶点访问状态数组
int Get_min_dist(const vector<int>& dist, const vector<bool>& visited)
{int min = INT_MAX, min_index(-1);for (int i = 0; i < vertex_num; i++)   //遍历所有顶点{if (!visited[i] && dist[i] < min)  //若该顶点未被访问且权值较小{min = dist[i];  //更新最小值min_index = i;  //更新最小值对应的下标}}return min_index;       //返回最小值对应的下标
}//功能：求最小生成树
//参数：图的邻接矩阵
void primMST(vector<vector<int>> edge)
{vector<int> dist(vertex_num, INT_MAX);//存储每个节点到最小生成树的直接距离的最小值，初始值为INT_MAX,表示还未连接到树中vector<int> parent(vertex_num, -1);//存储每个节点的父节点，每个节点及其父节点构成最小生成树的一条边，初始值为-1vector<bool> visited(vertex_num, false);//用来标记一个节点是否已经包含在最小生成树中dist[0] = 0;//从节点0开始构建最小生成树//构建最小生成树for (int i = 0; i < vertex_num - 1; i++)     //执行n-1次循环，之后便可确定n-1条边{int u = Get_min_dist(dist, visited);//获得离已有生成树最近的节点的下标uvisited[u] = true;//标记该节点为已访问（加入到生成树中）for (int j = 0; j < vertex_num; j++)     //遍历每个节点，n次循环{if (edge[u][j] && !visited[j] && edge[u][j] < dist[j])//若该节点和u之间有边、未被访问、距离较小{dist[j] = edge[u][j];  //更新最小距离parent[j] = u;         //更新最小距离对应的父节点}}}//输出结果int sum(0);cout << "edge\tweight\n";for (int i = 1; i < vertex_num; i++){cout << i << "-" << parent[i] << "\t" << dist[i] << endl;sum += dist[i];          //将最小生成树的边累加起来}cout << "sum_dist:" << sum;  //总的最小距离，一般需要的是这个。
}int main()
{primMST(edge);//调用求最小生成树的函数return 0;
}

结果如下图所示：

三、Kruskal算法

Kruskal算法是求解的另一种经典贪心算法。

该算法的基本思想是：通过边的权重进行排序，然后逐步将权重最小的边加入生成树。对于每条边，算法检查是否会形成环，如果不形成环，则将这条边加入生成树。这个过程持续到生成树包含所有节点为止。

Kruskal适用于稀疏网，其大致步骤如下：

初始化：
- 将图中所有的边按权重从小到大排序。
- 为每个节点初始化一个独立的集合，通常使用并查集（Union-Find）来高效管理这些集合。
选择边：
- 从权重最小的边开始，检查该边的两个端点是否属于同一个集合。
- 如果不在同一集合中，说明加入这条边不会形成环，将这条边加入生成树，并合并这两个集合。
终止条件：
- 重复以上步骤，直到生成树中包含 n-1条边（其中n是图中节点的数量）。

#include <iostream>
using namespace std;
#include <algorithm>      //使用sort()排序函数要用
#include <vector>//边的结构体，用于表示边，包含起点、终点、权重
struct edge                       
{int src;int dest;int weight;
};//并查集,用于维护每个节点的父节点和秩（rank），以便高效地进行合并操作
struct subset                     
{int parent;int rank;  //秩，后续初始为0，可以理解为等级，等级越高表示树的层数越高//在树的合并时，将层数少的作为子树，并到层数高的树下
};//自定义排序规则，按权重升序排列
bool compareEdge(edge a, edge b)  
{return a.weight < b.weight;
}//用于查找某个节点的根节点，同时压缩路径以提高效率
int find(subset subsets[], int i)
{if (subsets[i].parent != i)   //若该节点的父节点不是它自己，即它不是根节点{subsets[i].parent = find(subsets, subsets[i].parent); //继续查找其根节点并压缩路径}return subsets[i].parent;                      //返回该节点的根节点
}//用于合并两个节点的集合，采用按秩合并的方法
void union_set(subset subsets[], int x, int y)
{int xroot = find(subsets, x);                  //找到x的根节点int yroot = find(subsets, y);                  //找到y的根节点if (subsets[xroot].rank < subsets[yroot].rank) //取秩较大者的集合的根节点作为合并后的根节点{subsets[xroot].parent = yroot;}else if (subsets[xroot].rank > subsets[yroot].rank){subsets[yroot].parent = xroot;}else                                          //若秩相同，则任取一方的根节点为合并后的根节点{subsets[yroot].parent = xroot;subsets[xroot].rank++;}
}//Kruskal算法实现
void Kruskal(vector<edge>& edges, int vertex_num)
{vector<edge> result;//存放结果int edge_count = 0;//记录最小生成树已有的边，达到vertex_num-1时结束sort(edges.begin(), edges.end(), compareEdge);//将所有边按权值升序排列subset* subsets = new subset[vertex_num];for (int i = 0; i < vertex_num; i++)  //为每个节点创建并查集{subsets[i].parent = i;//每个节点初始时其根节点是它自己，因为每个节点最开始都是单独一个subsets[i].rank = 0;              //同时秩（可以理解为层数）也为最低}for (edge e : edges)                  //遍历每条边{int x = find(subsets, e.src);     //找到该边起点的根节点int y = find(subsets, e.dest);    //找到该边终点的根节点if (x != y)//若俩根节点不一致，即起点和终点没有都加入生成树，加入该边不形成环，可合并{result.push_back(e);          //把该边加入生成树union_set(subsets, x, y);     //合并edge_count++;                 //边数+1}if (edge_count == vertex_num - 1) //若边数已达n-1条，退出循环，结束构建{break;}}//输出结果int sum(0);cout << "edge\tweight\n";for (edge edge : result){cout << edge.src << "-" << edge.dest << "\t" << edge.weight << endl;sum += edge.weight;}cout <<"sum_weight:"<< sum;           //一般是求这个，总的最小权重delete[] subsets;                     //释放动态内存，避免内存泄漏
}int main()
{//图的边信息vector<edge> edges = { {0, 1, 10},{0, 2, 6 },{0, 3, 5 },{1, 3, 15},{2, 3, 4 } };int vertex_num = 4;                    //顶点数 Kruskal(edges, vertex_num);            //调用Kruskal算法求最小生成树return 0;
}

结果如图所示：