数据结构（八）最小生成树

文章结构概述

• 1. 最小生成树
  • • 1.1 定义
    • 1.2 Prim方法
    • 1.3 Kruskal方法

最小生成树概念与应用

1.概念界定与核心定义

生成树 ：由全部顶点构成的最小连通子图。
①添加一条边后，将产生一个环路。
②移除一条边后，该图将不再保持连通性。

最小生成树 ：在所有生成树中，具有最小边权值总和的结构。

获取最小生成树通常采用两种算法：Prim算法与Kruskal算法，二者均遵循贪心策略进行计算。

1.2 Prim算法

（1）算法思路

• 首先从图中任取一个顶点纳入树T的结构之中。
• 随后不断寻找与当前树T距离最短的顶点，将其连同相应的边一同纳入树T，此过程持续至所有顶点均被包含于树T之内。

通常需要对两个向量isjoin[n]和lowcost[n]进行维护，其中前者用于标识节点是否已被纳入树结构，后者则用于记录该节点与树之间的最短距离。

（2）特点

• 算法的时间复杂度为O(V^2)，适用于