最小生成树算法概览

一句话简介

最小生成树是图论经典问题，本文介绍生成树定义、最小生成树应用场景，以及 Kruskal 和 Prim 两种经典算法的核心原理。

生成树 是无向连通图 $G$ 的一个子图，包含 $G$ 中的所有顶点，且是一棵树（无环连通图）。

特性：

一个图可以有多个不同的生成树。

如果图是加权图，最小生成树 就是边权重总和最小的生成树。

应用场景：

边的权重可以代表距离、成本、时间等。

两种经典算法都基于贪心思想：

具体代码实现在 Kruskal 算法和 Prim 算法中讲解。

最小生成树算法经过改造后，可用于生成游戏中的随机化迷宫、洞穴等场景。

核心思想：利用最小生成树算法 能够连接所有顶点且无环路 的特性，确保生成地图的连通性。通过引入随机性，创造每次都不同、看起来自然且复杂的地图结构。

观察不同算法的特点：

生成的地图特点不同，可以用 BFS/DFS 算法体会不同算法生成地图的特点。