算法——最小生成树算法

线性表：由同种数据类型的数据元素组成的有序序列。一般用于存储由顺序关系的数据序列。

树：树存储结构不允许存在环路。

图：图存储结构中可以存在环路。

连通图：从任一顶点到另一个顶点都至少存在一条通路。

非连通图：只要有某两个顶点之间找不到通路。

生成树：包含图中所有的顶点。任意顶点之间有且仅有一条通路。

最小生成树：指的就是在连通网中找到的总权值最小的生成树。常用的两种算法：

普里姆（Prim）算法

克鲁斯卡尔（kruskal）算法

普里姆（Prim）算法

普里姆（Prim）算法：任选一个顶点出发，每次都选权值最小的边的顶点与原顶点相连。

采用的是贪心算法的思想。

时间复杂度=O(n²)（n 为顶点数）

适用于稠密图，算法思想是选择点

实现思路：

将连通网中的所有顶点分为两类（假设为 A 类和 B 类）。初始状态下，所有顶点位于 B 类；

选择任意一个顶点，将其从 B 类移动到 A 类；

从 B 类的所有顶点出发，找出一条连接着 A 类中的某个顶点且权值最小的边，将此边连接着的 A 类中的顶点移动到 B 类；

重复执行第 3 步，直至 B 类中的所有顶点全部移动到 A 类，恰好可以找到 N-1 条边。