一、Prim算法
Prim算法时间复杂度为O(n ^ 2)
Prim算法的具体思路是,每次根据最小那条边的顶点松弛边,然后再根据dis数组继续松弛,一直到n-1条边数完。
优化后的时间复杂度为O(nlogn)
1 #include "bits/stdc++.h" 2 using namespace std; 3 int Graph[110][110];//邻接矩阵 4 int vis[110];//标记小标是否搜集完 5 int dis[110];//存储权值 6 int m,n; 7 int s = 0; 8 void Prim() 9 { 10 int mmin = INT_MAX; 11 for(int i = 1;i <= n;i++) 12 dis[i] = Graph[1][i]; 13 vis[1] = 1;//标记以1为顶点的边全部搜集完 14 for(int i = 2;i <= n;i++){ 15 mmin = INT_MAX; 16 int k = 1; 17 for(int j = 1;j <= n;j++){ 18 if(!vis[j] && dis[j] < mmin){//查找当前最短的那条路 19 mmin = dis[j]; 20 k = j; 21 } 22 } 23 s += dis[k];//加上选择的最小的边的距离 24 cout << dis[k] << endl; 25 vis[k] = 1;//加入MST(最小代价生成树) 26 for(int j = 2;j <= n;j++) 27 if(!vis[j] && dis[j] > Graph[k][j])////用k为顶点更新最小的边,实际上是一个以j为中转点,松弛的一个过程 28 dis[j] = Graph[k][j];//如果有多个顶点到同一个顶点,那么就选择最小的那条路, 29 } 30 } 31 int main() 32 { 33 cin >> n >> m; 34 int sx,sy,sw; 35 for(int i = 1;i <= n;i++) 36 for(int j = 1;j <= n;j++) 37 if(i == j) 38 Graph[i][j] = 0; 39 else 40 Graph[i][j] = INT_MAX; 41 for(int i = 1;i <= m;i++){ 42 cin >> sx >> sy >> sw; 43 Graph[sx][sy] = sw; 44 Graph[sy][sx] = sw; 45 } 46 Prim(); 47 cout << s << endl; 48 return 0; 49 }
二、KrusKal算法
时间复杂度为O(e + loge) e是边的数目。
Kruskal是根据边来找最小生成树的算法,但是这个算法需要判断是否已经形成了环,则就不可以用这个算法,所以我们可以利用并查集看是否构成了环。剩下的就是把边排个序就行了,权值从小到大选够n-1条边即可。(你选了n-1条边后如果再选一定可以构成环)
1 /* 2 MST test case: 3 9 15//9是顶点数,15是边数 4 3 9 8 5 1 2 10 6 5 8 7 7 1 6 11 8 2 7 16 9 2 9 12 10 4 8 16 11 5 6 26 12 2 3 18 13 6 7 17 14 7 8 19 15 4 9 21 16 4 5 20 17 4 7 24 18 3 4 22 19 */ 20 #include "bits/stdc++.h" 21 using namespace std; 22 struct node { 23 int s,e,w; 24 }edges[110]; 25 int pre[110]; 26 int n,m; 27 void init()//利用并查集检查是否存在环 28 { 29 for(int i = 1;i <= n;i++) 30 pre[i] = i; 31 } 32 int find(int u) 33 { 34 return u == pre[u] ? u : pre[u] = find(pre[u]); 35 } 36 void kruskal()//O(mlogm) 37 { 38 for(int i = 1;i <= m;i++){ 39 int sx = find(edges[i].s); 40 int sy = find(edges[i].e); 41 if(sx != sy){//判断是否有环 42 pre[sx] = sy; 43 cout << edges[i].s << "--->" << edges[i].e << ':' << edges[i].w << endl; 44 } 45 } 46 } 47 bool cmp(node a,node b) 48 { 49 return a.w < b.w; 50 } 51 int main() 52 { 53 cin >> n >> m; 54 for(int i = 1;i <= m;i++)//从小到大依次选择边 55 cin >> edges[i].s >> edges[i].e >> edges[i].w; 56 sort(edges + 1,edges + m + 1,cmp); 57 init(); 58 kruskal(); 59 return 0; 60 }