本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程。
1.什么是最小生成树算法?
简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小。这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法。
2.Prim算法的步骤是什么?
这就要涉及一些图论的知识了。
a.假定图的顶点集合为V,边集合为E.
b.初始化点集合U={u}.//u为V中的任意选定的一点
c.从u的邻接结点中