本文共 1681 字,大约阅读时间需要 5 分钟。
题目链接:
prim算法:算法从任意一个顶点开始,每次选择一个与当前顶点集最近的一个顶点,并将两顶点之间的边加入到树中。Prim
算法在找当前最近顶点时使用到了贪婪算法。
代码实现:
#includeusing namespace std;const int maxn=105;const int INF=0x3f3f3f3f;//初始化无穷大int dis[maxn];//dis[i]//记录边权bool vis[maxn];//标记边int edge[maxn][maxn];void prim(int n){ for(int i=1;i<=n;i++) dis[i]=edge[1][i];//初始时候记录1到其他顶点距离 int ans=0; dis[1]=0; vis[1]=true;//将用过的点标记,避免重复访问 for(int i=2;i<=n;i++)//进行n-1次操作 { int u=INF; int pos;//记录最小权值的顶点的下标 for(int j=1;j<=n;j++)//在未加入点中,找到一个最小的权值 { if(!vis[j]&&u>dis[j]) { u=dis[j];//更新最小值 pos=j; } } if(u==INF) break;//图不是连通图 vis[pos]=true;//将加入点进行标记 ans+=u;//加边权 for(int j=1;j<=n;j++)//枚举所有点 {//在未加入点中找到与此点相连的权值最小的边 if(!vis[j]&&dis[j]>edge[pos][j]) { dis[j]=edge[pos][j];//更新权值 } } } printf("%d\n",ans);}int main(){ int n; while(scanf("%d",&n)&&n) { memset(vis,false,sizeof(vis)); int m=(n-1)*n/2; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); edge[u][v]=edge[v][u]=w; } prim(n); } return 0;}
kruskal算法:
kruskal算法主要是加边,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
1. 把图中的所有边按代价从小到大排序; 2. 把图中的n个顶点看成独立的n棵树组成的森林; 3. 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi ,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。代码:
#includeusing namespace std;const int maxn=1e4+5;typedef long long LL;int father[maxn];struct node{ int u,v,val;//u-v之间边权为val}edge[maxn];bool cmp(node a,node b)//按照边权小到大排序{ return a.val
转载地址:http://apncf.baihongyu.com/