普里姆算法最小生成树（普里姆算法）

大家好，我是小夏，我来为大家解答以上问题。普里姆算法最小生成树，普里姆算法很多人还不知道，现在让我们一起来看看吧！

1、）生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含图中的所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个生成森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。

2、2）和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历，(Traversing Graph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。

3、3）在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同。

4、在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。

5、常见的求最小生成树的方法有两种：克鲁斯卡尔(Kruskal)算法和普里姆（Prim）算法

本文到此讲解完毕了，希望对大家有帮助。