掌握数据结构与算法第42讲 最小生成树

首先阐述若干基本概念问题：

1. 生成树：对于一个包含n个顶点的连通图而言，其生成树是该图的一个极小连通子图。该子图包含全部n个顶点，但仅由n-1条边构成，且不形成任何回路。

2. 最小生成树：在无向连通图中，若各边均带有权值，则通过计算所有边的权值总和最小的生成树，即称为最小生成树。

因此，在求解最小生成树时，首先需满足以下条件：1. 图必须为无向图；2. 图应为连通图（任意两个顶点之间均存在路径）；3. 图中的边需带有权值。

简而言之，所求对象必须是一个带权的连通图。

在寻找最小生成树的过程中，严蔚敏编著的《数据结构》一书中提出了两种实现方式：普里姆算法与克鲁斯卡尔算法。

普里姆算法：

克鲁斯卡尔算法是一种用于解决最小生成树问题的经典方法，其核心思想是按照边的权重从小到大依次选择边，并确保所选边不会形成环路，从而逐步构建出整个图的最小生成树结构。

**克鲁斯卡尔算法中被排除