克鲁斯卡尔求最小生成树——并查集的应用

参考：https://www.cnblogs.com/yoke/p/6697013.html

克鲁斯卡尔算法

克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边（u，v）。
具体实现过程如下：
<1>　设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。
<2>　在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。
<3>　如此重复下去，直到所有顶点在同一连通分量上为止。
下面是伪代码：

 1 // 把所有边排序，记第i小的边为e[i] (1<=i<=m)m为边的个数 
 2 // 初始化MST为空
 3 // 初始化连通分量，使每个点各自成为一个独立的连通分量
 4 
 5 for (int i = 0; i < m; i++)
 6 {
 7     if (e[i].u和e[i].v不在同一连通分量)
 8     {
 9         // 把边e[i]加入ＭＳＴ
10         // 合并e[i].u和e[i].v所在的连通分量 
11     } 
12 }

上面的伪代码，最关键的地方在于“连通分量的查询和合并”，需要知道任意两个点是否在同一连通分量中，还需要合并两个连通分量。
这个问题正好可以用并查集完美的解决

并查集

并查集（Union-Find set）这个数据结构可以方便快速的解决这个问题。基本的处理思想是：初始时把每个对象看作是一个单元素集合；然后依次按顺序读***通边，将连通边中的两个元素合并。在此过程中将重复使用一个搜索（Find）运算，确定一个集合在那个集合中。当读入一个连通边（ｕ，ｖ）时，先判断ｕ和ｖ是否在同一个集合中，如果是则不用合并；如果不是，则用一个合并（Union）运算把ｕ、ｖ所在集合合并，使得这两个集合中的任意两个元素都连通。因此并查集在处理时，主要用到搜索和合并两个运算。
为了方便并查集的描述与实现，通常把先后加入到一个集合中的元素表示成一个树结构，并用根结点的序号来表示这个集合。因此定义一个parent[n]的数组，parent[i]中存放的就是结点ｉ所在的树中结点ｉ的父亲节点的序号。例如，如果parent[4]=5，就是说４号结点的父亲结点是５号结点。约定：如果ｉ的父结点（即parent[i]）是负数，则表示结点ｉ就是它所在的集合的根结点，因为集合中没有结点的序号是负的；并且用负数的绝对值作为这个集合中所含结点的个数。例如，如果parent[7]=-4，说明７号结点就是它所在集合的根结点，这个集合有四个元素。初始时结点的parent值为－１（每个结点都是根结点，只包含它自己一个元素）。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//边类
class edge
{
   
public:
 int i, j, w;
 edge(int i, int j, int w) :i(i), j(j), w(w) {
   }
};
vector<edge> ev;
int n, * parent,**a;
//sort的比较函数
bool cmp(edge a, edge b)
{
   
 return a.w < b.w;
}
//初始化parent数组
void initparent()
{
   
 for (int i = 0; i < n; ++i)
  parent[i] = -1;
}
//查找树根
int find(int x)
{
   
 int s;
 for (s = x; parent[s] >= 0; s = parent[s]);
 while (s != x)
 {
   
  int temp = parent[x];
  parent[x] = s;
  x = temp;
 }
 return s;
}
//合并
void Union(int a,int b)
{
   
 int p1, p2,temp;
 p1 = find(a);
 p2 = find(b);
 temp = parent[p1] + parent[p2];
 if (parent[a] > parent[b])//此处注意都是负数
 {
   
  parent[p1] = p2;
  parent[p2] = temp;
 }
 else
 {
   
  parent[p2] = p1;
  parent[p1] = temp;
 }
}
//克鲁斯卡尔算法
void Kruskal()
{
   
 int sumw = 0, nume = 0, u,v;
 initparent();
 for (auto k : ev)
 {
   
  u = k.i; v = k.j;
  if (find(u) != find(v))
  {
   
   sumw += k.w;
   Union(u, v);
   a[u][v] = k.w;
   a[v][u] = k.w;
  }
  if (nume >= n - 1)break;
 }
 cout << "最小生成树的权值为" << sumw << endl;
}
int main()
{
   
cout << "输入矩阵维数：" << endl;
 cin >> n;
 a = new int* [n];
 for (int i = 0; i < n; ++i)
  a[i] = new int[n];
  parent = new int[n];
 cout << "输入赋权图" << endl;
 for(int i=0;i<n;++i)
  for (int j = 0; j < n; ++j)
  {
   
   a[i][j] = 0;
   int w;
   cin >> w;
   if(w!=0)
   ev.push_back({
    i, j, w });
  }
 sort(ev.begin(), ev.end(), cmp);
 Kruskal();
 cout << "最小生成树：" << endl << '\t';
 for (int i = 0; i < n; ++i)
  cout << i << '\t';
 cout << endl;
 for (int i = 0; i < n; ++i)
 {
   
  cout << i << '\t';
  for (int j = 0; j < n; ++j)
   cout << a[i][j] << '\t';
  cout << endl;
 }
}

实验的分析与思考

该实验利用克鲁斯卡尔算法求最小生成树，特点为利用了并查集的相关知识。克鲁斯卡尔算法中的两个重要操作：
1.判断当前边的两个节点是否位于两个不同的连通分量中。
2.若分别位于两个不同的连通分量则把这两个连通分量合并。
这两个操作并查集能够完美的执行。分别利用find函数和union函数即可。
解决了这两个问题，按照伪代码就能够直接写出。

克鲁斯卡尔求最小生成树——并查集的应用

克鲁斯卡尔算法

并查集

代码：

实验的分析与思考

全站热榜