求最小生成樹最基本的兩種演算法，當然，還有其他演算法，
最小生成樹
概念
一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊，
概述
在一給定的無向圖G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集（即）且為無回圈圖，使得 的 w(T) 最小，則此 T 為 G 的最小生成樹，
最小生成樹其實是最小權重生成樹的簡稱，
性質
最小生成樹性質：設G=(V，E）是一個連通網路，U是頂點集V的一個非空真子集，若(u，v）是G中一條“一個端點在U中（例如：u∈U），另一個端點不在U中的邊（例如：v∈V-U），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包括此邊（u，v），
（以上來自百度百科） 注：一個圖中的最小生成樹不一定只有一個，若各邊權值不等，則最小生成樹唯一，若有2潭訓2條以上的邊權值相等，則最小生成樹可能不唯一Prim
和dijkstra類似，采用紅白點思想，就是選中一個起始點，標為紅點，其他為白點，然后開始回圈，找離所有被標記的紅點最近的那個點，并將其標為紅點，接著用這個點更新剩余的白點到所有的紅點的最短距離，
如此回圈n次，得到答案，
圖解
我們選中V1為起始點，并標記為紅點，則此時：
dis[V2]=6,dis[V3]=1,dis[V5]=7,dis[V6]=5,dis[V4]=5；
則離紅點最近的點是V3，我們選中V3為紅點并分別更新其它點到紅點的最短距離則此時：
dis[V2]=5,dis[V5]=6,dis[V6]=4,dis[V4]=5；
那么，我們繼續回圈以上步驟：
此時離紅點最近的點是V6
dis[V2]=5,dis[V5]=6,dis[V4]=2；
此時離紅點最近的點是V4
dis[V2]=5,dis[V5]=6；
此時離紅點最近的點是V2
dis[V5]=6；
完成！！！
代碼（普通）
#include<bits/stdc++.h> using namespace std; int f[100][100],mt,ft[100],dis[100],n,m; void input() { int u,v,w; cin>>n>>m; memset(f,0x7f,sizeof(f)); memset(ft,0,sizeof(ft)); memset(dis,0x7f,sizeof(dis)); ft[1]=true; dis[1]=0; for(int i=1;i<=m;i++) { cin>>u>>v>>w; f[i][i]=0; f[u][v]=f[v][u]=w; } for(int i=1;i<=n;i++) dis[i]=min(dis[i],f[1][i]); } void prim() { int k,minn; for(int i=1;i<=n;i++) { k=0;minn=1e9; for(int i=1;i<=n;i++) { if(!ft[i]&&dis[i]<minn) { k=i; minn=dis[i]; } } ft[k]=true; if(k==0) break; mt=mt+dis[k]; for(int i=1;i<=n;i++) if(!ft[i]) dis[i]=min(dis[i],f[i][k]); } } void output() { cout<<mt; } void text1() { input(); prim(); output(); } int main() { text1(); return 0; }
代碼（堆優化）
堆優化類似dijkstra的堆優化，詳情見dijkstra
Kruscal
這個思路很簡單，從最小的邊開始從小到大列舉，若此邊所連的兩點至少一點還沒有被標記，那么，將此邊加入最小生成樹并標記點，
#include<bits/stdc++.h> using namespace std; int father[100],n,m,k,mt; struct ed { int from; int to; int w; }edge[100]; bool cmp(ed a,ed b) { if(a.w!=b.w) return a.w<b.w; } int fat(int x) { if(father[x]!=x) father[x]=fat(father[x]); return father[x]; } void unionn(int a,int b) { int fa,fb; fa=fat(a); fb=fat(b); if(fa!=fb) father[fa]=fb; } void input() { cin>>n>>m; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) cin>>edge[i].from>>edge[i].to>>edge[i].w; sort(edge+1,edge+m+1,cmp); } void kruscal() { for(int i=1;i<=m;i++) { if(fat(edge[i].from)!=fat(edge[i].to)) { k++; mt+=edge[i].w; unionn(edge[i].from,edge[i].to); } if(k==n-1) break; } } void output() { cout<<mt; } void text1() { input(); kruscal(); output(); } int main() { text1(); return 0; }
后記：nothing
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69638.html
標籤：其他
下一篇：動態規劃刷題