上面的算法有三个循环,时间复杂度为O(N^3),考虑到由于使用的是贪心策略,则每添加一个新顶点到集合S中的时候,才会改变V中每个点到S中点的最小边的长度。因此可以用一个数组nearest[N](N为顶点个数)记录在生成最小数的过程中,记录V中每个点的到S中点的最小变长,用另外一个数组adjecent[N]记录使得该边最小的对应的邻接点。那么O(N)的时间了找到最短的边,并且能在O(N)的时间里更新nearest[N]和adjecent[N]。因此可以得到O(N^2)的算法。
源码实现如下:
//O(N^2)
#include
using namespace std;
#define N 6 //节点个数
#define M 100000//最大值,表示不可达
//用邻接矩阵表示无向图
int matrix[N][N] =
{
M,6,1,5,M,M,
6,M,5,M,3,M,
1,5,M,5,6,4,
5,M,5,M,M,2,
M,3,6,M,M,6,
M,M,4,2,6,M
};
void prim()
{
//记当前生成树的节点集合为S
//未使用的节点结合为V
bool flag[N]; //标记某个点是否在S中
int nearest[N];//记录V中每个点到S中邻接点的最短边
intadjecent[N];//记录与V中每个点最邻接近的点
int i,j,min;
//初始化集合
for(i = 0; i flag[i] =false; flag[0] = true; for(i = 1; i { nearest[i] =matrix[0][i]; adjecent[i] =0; } int count = N; while(--count) { min = M; j = 0; for(i = 0; i< N; ++i) { if(!flag[i] && nearest[i] < min) { min =nearest[i]; j =i; } } cout< for(i = 0; i< N; ++i) { if(!flag[i] && matrix[i][j] { nearest[i] = matrix[i][j]; adjecent[i] = j; } } } } int main(int argc, char* *argv) { prim(); system("pause"); return 0; }
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。