Kruskal

Kruskal算法与并查集

算法思路

• 以边入手

从边入手，将边按照权递增排序，所以我们需要使用边集数组。

• 并查集判断

  由于使用了边，但是我们要判断是否会形成回路。所以使用查集。

代码细节

• 边集数组

  typedef struct {
  	int begin, end;
  	ArcType weight;		// ? the begin mean the point of the arcs
  }Edge;
  
  // 并且我们也要用到并查集的知识 感觉非常巧妙
  //算法的是现实思想 这个就是使用的边集数组 对应的特有的数据结构

• 并查集

  /先理解我们并查集的思想吧
  // 实现所需要具有的数据结构 一个整数数组 两个函数 find and join
  const int N{ 1000 };
  int pre[N];
  int Rank[N];		// find 函数优化时所需要使用的一个标记数组
  
  void init(int n)
  {
  	for (int i = 0; i < n; i++)
  	{
  		pre[i] = i;		// 起始的时候全部为自己代表自己全部时分开的
  		Rank[i] = 1;	// 深度全是1	0 也可以
  	}
  }
  
  int find(int x)		// 查找 x 的根结点 还是一个树形结构
  {
  	if (x == pre[x])
  		return x;
  	return find(pre[x]);
  }
  
  int find_pro(int x)	// 查找的时候顺便完成一个路径压缩
  {
  	while (x == pre[x])
  		return x;
  	return pre[x] = find_pro(pre[x]);
  }
  
  int find_(int x)	// 因为是一个尾递归所以可以写成以一个循环
  {
  	while (x != pre[x])
  		x = pre[x];
  	return x;
  }	// 我们使用的 
  // 并查集 还有一个方法就是 并join()
  // pro的非递归写法
  int find_pro_(int x)
  {
  	int temp;
  	int r = x;
  	while (pre[r] != r)
  	{
  		r = pre[r];
  	}
  	while (x != r)
  	{
  		temp = pre[x];
  		pre[x] = r;
  		x = temp;
  	}
  	return r;
  }
  
  bool issame(int x, int y)
  {
  	return find(x) == find(y);		// 优雅
  }
  
  Status join(int x, int y)
  {
  	x = find(x);
  	y = find(y);
  	if (x == y)
  		return false;
  	if (Rank[x] < Rank[y])
  		pre[x] = y;
  	else
  	{
  		if (Rank[x] == Rank[y])
  			Rank[x]++;
  		pre[y] = x;
  	}
  	return true;
  }
  
  // OKay so far 我们写我们要使用的函数 Find
  int Find(int* parent, int f)
  {
  	while (parent[f]>0)
  		f = parent[f];
  	return f;
  }
  // 排序的时候可以用 qsort 也可以自己写

思路整理 ，首先运用一个整数数组来存每个元素的前驱，然后设定一个代表元，通过不断向上访问得到代表元。所以并查集本质任然是一个树形结构，研究连通的关系。

• 将邻接矩阵转换为一个边集数组

  inline void edgecpy(const AMGraph& G, Edge* e)	//
  {
  	int k = 0;
  	for(int i=0;i<G.vertexnum-1;i++)
  		for(int j=i+1;j<G.vertexnum;j++)
  			if (G.arcs[i][j] < INF)
  			{
  				e[k].begin = i;
  				e[k].end = j;
  				e[k].weight = G.arcs[i][j];
  				++k;
  			}
  }

然后我们基本就得到了全部了

附上完整代码

Status  cmp_(void const* e1, void const* e2)
{
	return (((Edge*)e1)->weight > ((Edge*)e2)->weight);
}

void MST_Kruskal(const AMGraph& G)
{
	Edge* edges = new Edge[MVNum];	//	创建一个边集数组
	int* parent = new int[G.vertexnum];
	int m = 0, n = 0;
	int i = 0;
	int min_casts = 0;

	memset(parent, 0, sizeof(parent));
	edgecpy(G, edges);
	qsort(edges,G.arcnum, sizeof(Edge), cmp_);
	for (i = 0; i < G.arcnum; i++)
	{
		m = Find(parent, edges[i].begin);
		n = Find(parent, edges[i].end);
		if (m != n)
		{
			parent[m] = n;
			cout << "( " << edges[i].begin << "," << edges[i].end << " )\n";
			min_casts += edges[i].weight;
		}
	}
}

结语

从边出发，并查集的思想很重要