最小生成树数据结构的问题

我也没有ctrl+c，ctrl+v这里有答案，还有分析。

这种**是互联网上的一堆。

如果图形边缘的权重不同，则其最小生成树是唯一的。

n 个点由 n-1 条边连接，形状只能是一棵树。 可以这样理解：树的每个节点都有一个唯一的父节点，即至少有n条边，除了根节点，所以它是n-1条边。

那么，对于一个n点加权图，它的生成树就是用n-1条边来连接n个点，那么最小生成树就是n-1条边的边权总和，简单的理解就是只用这个图n-1条边，n-1条边的边权重之和是最小的。 红色边是此图的最小生成树。

树形图的概念。

无圆且相连的无向图称为树。 树木通常表示为 t。 作为树的定义，它也可以用以下方式表示：

1） T 已连接，没有环路或环路。

2） T 未带圆圈，有 n 条边（如果有 n 个节点）。

3） T 与 n 1 边连接。

4）T没有环，但两个彼此不相邻的节点连接到一侧，只有一个圆。

5） t 已连接，但如果移除 t 的任何边，则 t 未连接。（也就是说，在具有相同点集的图形中，树是边最少的连接图形。 ）

6） t 的任意两个节点之间正好有一条主链。

通常先找到最小生成树，然后找到它亚小型生成树（具体来说，可以枚举图上的其他边并将它们添加到树中，同时删除重复的边，并找到权重和最小边删除方法），如果子小生成树的权重和不等于最小生成树，则最小生成树是唯一的， 否则它不是唯一的。

没有一个所有权值相等，或者存在相等的边，但在构建生成树的过程中，权重相等的边包含在生成树中，最小生成树是唯一的。 - 天琴。

当加权连接图的任何一个环包含不同的权重时，其 MST 是唯一的。 --从王道。

任何一个环中包含的边缘的重量都是不同的。

最小生成树应用于图论知识的实际问题。 生成树和最小生成树具有许多重要的应用。

例如，如果要在n个城市之间铺设光缆，主要目标是使这n个城市中的任意两个之间进行通信，但是铺设光缆的成本非常高，并且铺设光缆的成本因城市而异，因此另一个目标是将铺设光缆的总成本降至最低。 这需要找到最小加权生成树。

生成树协议的工作原理：如果在任何交换机中到达根网桥。

有两个或多个链接。 生成树协议只保留一个交换机，切断其他交换机，从而保证任意两个交换机之间只有一个活动链路。 由于生成的这种拓扑。

它很像以根开关为主干的树结构，因此称为生成树协议。

以上内容是指：百科全书 - 最小生成树。

以上内容请参考：百科全书-生成树协议。

求解最小生成树。

方法如下：

连接图：在无向图中，如果任意两个顶点 VI 和 VJ 具有相互通信的路径，则称为无向图为连接图。

强大的连接图。 在有向图中，如果任意两个顶点 VI 和 VJ 具有共同的路径，则称有向图是强连接的。

连接网络：在连接图中，如果图的边有一定的含义，则每条边对应一个数字，称为权重; 右图表示连接顶点的成本，这种连通性图称为连通性网络。

生成树：连接图的生成树是一个连接子图，它包含图中的所有 n 个顶点，但只有足够的 n-1 条边来形成树。 具有 n 个顶点的生成树具有且只有 n-1 条边，如果将另一条边添加到生成树中，则必须对其进行循环。

最小生成树：连接网络的所有生成树中所有边和最小生成树的成本称为最小生成树。

以下是最小生成树的一些解决方案。

Prime算法的基本思想。

1.清除生成树，并取任意顶点加入嵊州正城树。

2.在一个端点位于生成树中而另一个端点不在活动树中的边中，选择权重最小的边，然后将其和另一个端点添加到生成树中。

3.重复步骤 2，直到所有顶点都进入生成树，生成树是最小的生成树。

Kruskal 算法：构造一个只有 n 个顶点和一个空边集的子图，如果子图中的每个顶点都看作是每棵树的根节点，则它就是一个有 n 棵树的森林。

然后，从网的边集中选择一条权重最小的边，如果边的两个顶点属于不同的树，则将其添加到子图中，即将两个顶点所在的两棵树合并成一棵树。 相反，如果边的两个顶点落在同一棵树上，则不建议采用权重最小的边。 依此类推，直到森林里只有一棵树。

Kruskal 算法可以在并行集的基础上非常快速地实现。 结合算例介绍具体算法实现（合并查询部分的合并查询部分可以在合并查询部分的介绍中找到）。

生成树的概念：连接图g的子图 如果它是一棵树，其中包含g的拍摄轨迹的顶点，那么该子图称为g的生成树 生成树是连接图的一个非常小的连接子图。 所谓的最低限度：

如果随机向树添加一条边，则会出现一个循环; 如果删除一条边，则会使它编程为一个断开连接的图。 生成树两侧的权重之和称为基因的权重。 权重最小的生成树称为最小生成树，常用的算法有素数算法和kruskal算法。

所谓的最小生成树是具有 n 个顶点的加权连接图 g，如果存在子图 g'，它包含图 g 中的所有顶点和边的子集，不形成循环，并且是子图 g'每边的权重之和最小，称为g'是图 g 的最小生成树。 从定义中，我们可以看到最小生成树的三个属性：

最小生成树不能有循环。

最小生成树可以是一个，也可以是多个。

生成树边的最小数量等于顶点数减去 1。 在本文中，我们将介绍两种最小生成树算法，即 Kruskal 算法和 Prim 算法。

Kruskal 算法的核心思想是，在加权连接图中，在边集中不断找到最小的边，如果边满足获得最小生成树的条件，则构造它，直到最终获得最小生成树。

Kruczcard算法的执行步骤：

第 1 步：在加权连接图中，对边的权重进行排序。

第 2 步：确定是否需要选择此边（此时，图形中的边已按权重从小到大的顺序排列）。 判断的依据是边的两个顶点是否连接，如果连接，则继续到下一个; 如果未连接，则选择使其连接。

第 3 步：循环第二步，直到图中的所有顶点都在同一个连接的组件中，即获得最小生成树。

下面我将用图表来说明 Kruskal 算法的工作流程，如下图所示：

请参阅贪婪算法 - 最小生成树算法。

贪婪策略：对算法的理解：

循环不变量：键亩。

在每个循环之前，a 是某个最小生成树的子集。

安全边：满足以下条件的边称为安全边。

将边 （u， v） 添加到集合 a 中，使 a 不违反循环不变量，即 au 也是最小生成树的子集。

在贪婪策略中识别安全边缘的规则：

推论：如果一个问题的最优解包含子问题的最优解，则该问题具有最优子结构。

最小生成树满足最优子结构，证明如下：