并查集与最小生成树 原理讲解、c++代码。
并查集是⼀一种树型的数据结构，⽤用于处理理⼀一些不不相交集合的合并及查询问题。
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
代码如下:#include #define MAX 100#define MAXCOST 100000int graph[MAX][MAX];int Prim(int graph[MAX][MAX], int n){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ int lowcost[MAX]; /* mst[i]记录对应lowcost[i]的起点 */ int mst[MAX]; int i, j, min, minid, s
