本文共 2678 字，大约阅读时间需要 8 分钟。

prim算法是求最小生成树的算法，与求最短路径的dijstra算法类似。是以点为基础进行扩展的。算法的执行过程为：划分两个集合，一个是已放置好的点，另一个数未放置好的点。从任意一个点开始，将这个点放入第一个集合，然后找到与第二个集合中与第一个集合中点距离最近的点，加入第一个集合，重复此操作，一直到所有点都加入为止。

时间复杂度：未优化之前的复杂度是O(v^2)，使用优先级队列优化后可以达到O(ElogE)。

未优化前：无论是使用邻接表还是邻接矩阵，时间复杂度都是O(v^2)，因为需要加入v条边即外层循环V次O(v)，内层需要遍历所有点O(v)来找下一个出发点以更新dis数组，总的复杂度为O(v^2)。

代码（邻接矩阵）：

#include 
   
    #include 
    
     #define INF 0xfffffff#define N 550int V, E;bool vis[N];int dis[N], map[N][N];					// dis数组保存与i点相连的最短边，map为邻接矩阵 void Init(){						// 初始化 	for(int i = 1; i <= V; i ++){		for(int j = 1; j <= V; j ++){			map[i][j] = INF;		}		vis[i] = 0;	}}int Prime(int choose){					// choose 为最小生成树的出发点，其实在这儿不重要，可默认为1 	for(int i = 1; i <= V; i ++){			// 更新dis数组 		dis[i] = map[choose][i];	}	vis[choose] = 1;				// 标记出发点 	dis[choose] = 0;	int ans = 0;	for(int j = 1; j < V; j ++)	{		int min = INF;		for(int i = 1; i <= V; i ++)		{					// 选取边权最小的点作为下一个出发点 			if(!vis[i] && min > dis[i]){				min = dis[i];				choose = i;			}		}		ans += min;		vis[choose] = 1;		for(int i = 1; i <= V; i ++){		// 以最新的出发点的边更新dis数组 			if(!vis[i] && dis[i] > map[choose][i]){				dis[i] = map[choose][i];			}		}	}	return ans;}int main(){	int loop;	int start, end, len;	scanf("%d", &loop);	while(loop --){		scanf("%d%d", &V, &E);		Init();		for(int i = 0; i < E; i ++){			// 建图 			scanf("%d%d%d", &start, &end, &len);			map[start][end] = map[end][start] = len;		}		int ans = Prime(1);		printf("%d\n", ans);	}	return 0;}
    
   

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define INF 0xfffffff#define N 550struct Node{	int to, len;	bool operator <(const Node &a)const{		return len > a.len;	}};int V, E;bool vis[N];vector
       
         G[N];priority_queue
        
          Q;void Init(){ for(int i = 1; i <= V; i ++){ G[i].clear(); vis[i] = 0; } while(!Q.empty())Q.pop();}int Prime(int choose){ Node p; for(int i = 0; i < G[choose].size(); i++) Q.push(G[choose][i]); vis[choose] = 1; int ans = 0, cnt = V - 1; while(!Q.empty() && cnt){ p = Q.top();Q.pop(); if(vis[p.to])continue; vis[p.to] = 1; ans += p.len; cnt--; choose = p.to; for(int i = 0; i < G[choose].size(); i++){ p = G[choose][i]; if(!vis[p.to]) Q.push(p); } } return ans;}int main(){ int loop; int start, end, len; Node p; scanf("%d", &loop); while(loop --){ scanf("%d%d", &V, &E); Init(); for(int i = 0; i < E; i ++){ scanf("%d%d%d", &start, &end, &len); p.len = len; p.to = end; G[start].push_back(p); p.to = start; G[end].push_back(p); } int ans = Prime(1); printf("%d\n", ans); } return 0;}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/zhj_fly/article/details/74028978 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！