算法分析的一般步骤:
1、文字描述:如果一个算法文字描述不清楚,就说明思路不清楚,也不可能写好。
prim算法是实现图的最小生成树。既然是图,就假设包含n个顶点,m条边。prim算法是从顶点出发的,其算法时间复杂度与顶点数目有关系。
(注意:prim算法适合稠密图,其时间复杂度为O(n^2),其时间复杂度与边得数目无关,而kruskal算法的时间复杂度为O(eloge)跟边的数目有关,适合稀疏图。)
算法思路:从某个顶点开始,假设v0,此时v0属于最小生成树结点中的一个元素,该集合假设u,剩下的V-v0为待判定的点,此时选取u中的顶点到V-v0中顶点的一个路径最小的边,并且将其中非u中的顶点加入到u中,循环直到u中的顶点包含图所有的顶点为止。
算法在选取最小路径的时候需要优化,具体思路:w[]数组保存各个顶点的最短路径,b[]数组保存到i顶点最短路径的顶点,比如,到0号顶点最短的路径是<v0,v3>,那么w[0]=<v0,v3>,b[0]=3;这样每次找最小路径就不是o(n*n)的代价了。
2、举例说明:
3、程序实现与说明:
#include#include #define count 6void prim(int a[][count],int u[],int w[],int b[],int n){ int i=0,j=0,m=0,min=100; for(i=0;i
4、时间复杂度:o(n*n)