求無向網的最小生成樹的算法有兩種:Prim和Kruskal,它們都是利用最小生成樹的MST性質得到的。
Prim算法思想:
逐漸長成一棵最小生成樹。假設G=(V,E)是連通無向網,T=(V,TE)是求得的G的最小生成樹中邊的集合,U是求得的G的最小生成樹所含的頂點集。初态時,任取一個頂點u加入U,使得U={u},TE=Ø。重複下述操作:找出U和V-U之間的一條最小權的邊(u,v),将v并入U,即U=U∪{v},邊(u,v)并入集合TE,即TE=TE∪{(u,v)}。直到V=U為止。最後得到的T=(V,TE)就是G的一棵最小生成樹。也就是說,用Prim求最小生成樹是從一個頂點開始,每次加入一條最小權的邊和對應的頂點,逐漸擴張生成的。
我們舉一個例子?來模仿一下Prim的操作流程:
(1)初始化U={v0},TE=Ø
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yNwcDO1YTY2YDOmBjNkJmMzYzXxEzNyETMyIzLclDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
(2)U={v0,v2},TE={(v0,v2)}
(3)U={v0,v2,v5},TE={(v0,v2),(v2,v5)}
(4)U={v0,v2,v5,v3},TE={(v0,v2),(v2,v5),(v5,v3)}
(5)U={v0,v2,v5,v3,v1},TE={(v0,v2),(v2,v5),(v5,v3),(v2,v1)}
(6)U={v0,v2,v5,v3,v1,v4},TE={(v0,v2),(v2,v5),(v5,v3),(v2,v1),(v2,v4)}
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int MaxSize=100;
const int MAX=9999;
class MGraph
{
string vertex[MaxSize]; //圖的頂點資訊
int adj[MaxSize][MaxSize]; //圖的鄰接矩陣
int vertexNum,edgeNum;
public:
MGraph(int n);
int W(int i,int j);
void InsertEdge(int i,int j,int p);
int VexNum()
{
return vertexNum;
}
friend void Prim(MGraph &g,int u0);
};MGraph::MGraph(int n)
{
vertexNum=n;
edgeNum=0;
memset(adj,0,sizeof(adj)); //将鄰接矩陣所有元素賦為0
}void MGraph::InsertEdge(int i,int j,int p) //插入頂點i、j依附的邊以及該邊的權值
{
adj[i][j]=adj[j][i]=p;
edgeNum++;
}int MGraph::W(int i,int j)
{
return adj[i][j];
}void Prim(MGraph &g,int u0)
{
int k;
int n=g.VexNum();
struct node
{
int adjvex;
int lowcost;
}closedge[MaxSize];
closedge[u0].adjvex=u0;
closedge[u0].lowcost=0;
for(int v=0;v<n;v++)
{
if(v!=u0)
{
closedge[v].adjvex=u0;
closedge[v].lowcost=g.W(u0,v);
}
}
closedge[u0].lowcost=0;
for(int i=0;i<=n-2;i++)
{
k=0;
int minw=MAX;
for(int v=0;v<=n-1;v++)
{
if(closedge[v].lowcost>0&&closedge[v].lowcost<minw)
{
k=v;
minw=closedge[v].lowcost;
}
}
cout<<"("<<closedge[k].adjvex<<","<<k<<")"<<":"<<minw<<" "<<endl;
closedge[k].lowcost=0; //頂點k并入U集
for(int v=0;v<=n-1;v++)
{
if(closedge[v].lowcost!=0&&g.W(k,v)<closedge[v].lowcost)
{
closedge[v].lowcost=g.W(k,v);
closedge[v].adjvex=k;
}
}
}
}int main()
{
struct Edge
{
int from,end,power;
};int n=6; //6個頂點
int e=10;
Edge b[]={{0,1,6},{0,2,1},{0,3,5},{1,2,5},{1,4,3},{2,3,5},{2,4,6},{2,5,4},{3,5,2},{4,5,6}};
MGraph m(n);
for(int k=0;k<e;k++)m.InsertEdge(b[k].from,b[k].end,b[k].power); //插入所有邊,将鄰接矩陣指派
Prim(m,0);
return 0;
</div>