最小生成树prim算法详解

embedded/2024/10/18 5:37:59/

prim算法解决的是最小生成树问题，即在一个给定的无向图G中求一棵生成树T，使得这棵树拥有图G中的所有顶点，且所有边都是来自图G中的边，并且满足整棵树的边权之和最小。

prim算法的基本思想是对图G设置集合S来存放已被访问的顶点，然后执行n次下面的两个步骤：

（1）每次从集合V-S中选择与集合S最近的一个顶点（记为u），访问u并将其加入集合S，同时把这条离集合S最近的边加入到最小生成树中。

（2）令顶点u作为集合S与集合V-S连接的接口，优化从u能到达的未访问顶点v与集合S的最短距离

prim算法和Dijkstra算法使用的思想几乎完全相同。只有在数组d[]的含义上有所区别。其中，Dijkstra算法的数组d[]含义为起点s到达顶点Vi的最短距离，而prim算法的数组d[]含义为顶点Vi与集合S的最短距离，两者的区别仅在于最短距离是顶点Vi针对“起点s”还是“集合S”。另外，对最小生成树问题而言，如果仅是求最小边权之和，那么在prim算法中就可以随意指定一个顶点为初始点，例如在下面的代码中默认使用0号顶点为初始点。实现的伪代码如下：

Prim(G,d[]){初始化;for(循环n次){u=使d[u]最小的还未被访问的顶点的标号;记u已被访问;for(从u出发能到达的所有顶点v){if(v未被访问&&以u为中介点使得v与集合S的最短距离d[v]更优){将G[u][v]赋值给v与集合S的最短距离d[v]; }} } 
}

下面给出分别使用邻接矩阵和邻接表的prim算法代码：

（1）邻接矩阵版

const int maxn=1000;
const int INF=1000000000;
int n,G[maxn][maxn];
int d[maxn];
bool vis[maxn]={false};
int prim(){//默认0为起始点，函数返回最小生成树的边权之和 fill(d,d+maxn,INF);d[0]=0;int ans=0;for(int i=0;i<n;i++){int u=-1,MIN=INF;for(int j=0;j<n;j++){//找到未访问的顶点中d[]最小的 if(vis[j]==false&&d[j]<MIN){u=j;MIN=INF;}}if(u==-1){return -1;}vis[u]=true;ans+=d[u];for(int v=0;v<n;v++){if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v]){d[v]=G[u][v];}}}return ans;
}

（2）邻接表版

struct node{int v,dis;
};
vector<node> Adj[maxn];
int n;
int d[maxn];
bool vis[maxn]={false};
int prime(){fill(d,d+maxn,INF);d[0]=0;int ans=0;for(int i=0;i<n;i++){int u=-1,MIN=INF;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<MIN){u=j;MIN=d[j];}}if(u==-1){return -1;}vis[u]=true;ans+=d[u];for(int j=0;j<Adj[u].size();j++){int v=Adj[u][j].v;if(vis[v]==false&&Adj[u][j].dis<d[v]){d[v]=Adj[u][j].dis;}}}return ans;
}

和Dijkstra算法一样，使用这种写法的复杂度为 $O\left ( V^{2} \right )$ ，其中邻接表实现的prim算法可以使用堆优化使时间复杂度降为 $O\left ( VlogV+E \right )$ 。所以尽量在图的顶点数目较少而边数较多的情况下使用prim算法。