c++数据结构：最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图。

• 一个图可以有多个不同的生成树
• 生成树的特点
  • 顶电数和图的顶点数相同
  • 生成树是图的极小连通子图
  • n个顶点，则有n-1条边
  • 生成树再加一条边就形成回路
  • 生成树两点路径唯一（两点只有一条边）

最小生成树： 

最小生成树：给定一个无向网，在该网中的所有生成树中，使得各边权值之和最小的那颗生成树称为该网的最小生成树（最小代价生成树）。

构建最小生成树的算法 ：

MST（Minimum Spanning tree）构建最小生成树

设N=（V，E）是一个连通网，U是顶点集V的一个非空子集。若边（u，v）是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一颗包含边（u，v）的最小生成树。

方法有两种：

• Prim（普里姆算法）
• kruskal（克鲁斯卡尔算法 ）

Prim（普里姆算法） ：

算法的基本流程： 

1. 使用两个数组分别存放顶点的位置和权值
2. 设V1为起点，把v1的权值设为0代表已经访问
3. 初始化，两个数组，分别存储V1相邻顶点的位置和权值
4. 找到权值最小的边，把对应的顶点的权值设为0
5. 查找该顶点相邻的边，如果权值更小，则把它替换
6. （4-5）需要执行n-1次（n为顶点个数）直到数组中的权值全为0

算法思想为：（根据顶点来判定）

#define INFINITY INT_MAX
struct//需要两个数组
{
	char adjvex;//存放所到的顶点
	int lowcost;//存放权值
}closeedge[Max_Num];
void Adj_matrix::Prim(char p)//普里姆算法
{
	
	int v = find_num(p);//获取数据在矩阵的位置
	for (int i = 0; i < vexnum; i++)//数组的初始化
	{
		if (i != v)
		{
            closeedge[i] = { p,arcs[v][i]};
		}		
	}
	closeedge[v].lowcost = 0;//起点已访问，设置为0
	for (int i = 1; i < vexnum; i++)//一共有 n个顶点，减去本身 有 n-1个，所以只需要n-1次
	{
		//需要找到权值最小的顶点
		int index = -1;//存储最小的顶点的数组位置
		int min = INFINITY;//存储最小权值
		for (int j = 0; j < vexnum; j++)
		{
			if (min > closeedge[j].lowcost && closeedge[j].lowcost != 0)//当lowcost大于min 且不等于0时
			{
				min = closeedge[j].lowcost;//获取最小值
				index = j;//获取位置
			}
		}
		v = index;
		//输出权值和顶点
		cout << closeedge[v].adjvex << " " << vexs[v];
		closeedge[v].lowcost = 0;//走过的赋值为0
 
		for(int m=0;m<vexnum;m++)//查找新顶点的边
		{
			if (arcs[v][m] < closeedge[m].lowcost)//如果新的边权值更小，就替换掉原来的边
			{
				closeedge[m].adjvex = vexs[v];
				closeedge[m].lowcost = arcs[v][m];
			}
		}
	}
 
}

kruskal（克鲁斯卡尔算法 ）

算法思想为：（根据边来判定）

1. 先把图中的所有的边取出来放到一个容器中
2. 把所有的边按照权值的大小进行排序
3. 从小到大取出边放到树中
4. 判断边放到树上后会不会生成回路，生成回路则丢弃
5. 假设顶点个数为n，直到边的个数为n-1时结束

代码就不实现了：有需求可以看下面这个视频

数据结构-最小生成树kruskal(克鲁斯卡尔)算法-C语言实现_哔哩哔哩_bilibili