首页 > 代码库 > 最小生成树学习总结
最小生成树学习总结
dijkstra算法
floyd算法
最小生成树
将所有的分成两个集合,一个是已经按照最小值排完顺序的,另外一个是没有排完顺序的,每次在查找从排完顺序的集合到未排完顺序的集合的最短路径,然后将未排完顺序的集合里面的值加入到已排完顺序的集合里。
最小生成树算法:
例题,第一行输入N和M,代表点的个数和他们之间存在的连线条数;
下面N行每行有三个整数a,b,L,代表a和b 之间的权值(或长度)为L;
输出: 输出这些点连成一个联通块,所用连线的权值和的最小值;
input:
5 7
1 2 10
1 3 20
1 5 30
2 5 10
2 3 5
4 5 20
4 3 30
output:
45
prim方法:
1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 const int N=10000; 5 int n,m;//the number of villages and roads 6 struct Record 7 { 8 int from,to,value; 9 friend bool operator<(Record A,Record B)10 {11 return A.value>B.value;12 }13 };14 priority_queue<Record>Q;15 int p[N];16 int find(int x)17 {18 if(p[x]==x)return x;19 return p[x]=find(p[x]);20 } 21 int prim()22 {23 int sum=0;24 Record re;25 while(!Q.empty())26 {27 re=Q.top();28 Q.pop();29 int fa=find(re.from);30 int fb=find(re.to);31 if(fa!=fb)32 p[fa]=fb,sum+=re.value;33 }34 return sum;35 }36 int main()37 {38 while(cin>>n>>m)39 {40 for(int i(0);i<=n;i++)p[i]=i;41 Record IN;42 for(int i(1);i<=m;i++)43 {44 scanf("%d %d %d",&IN.from,&IN.to,&IN.value);45 Q.push(IN);46 }47 int getvalue=http://www.mamicode.com/prim();48 cout<<getvalue<<endl;49 }50 return 0;51 }
prim方法不太适合大量数据的计算;
Kruskal 方法:
Dijkstra 算法:
#include<iostream>using namespace std;const int N=1100;const int INF=101000000; int map[N][N];int low[N];//记录最短路径 int n,m;//代表点的个数和路线的个数 int kruskal(int s) { for(int i=1;i<=n;i++) { low[i]=map[s][i]; } low[s]=-1; int sum=0,v; for(int i=1;i<n;i++) { int Min=INF; for(int j=1;j<=n;j++) { if(low[j]!=-1&&low[j]<Min) { Min=low[j]; v=j; } } //我经常把这个大括号放错地方,太马虎 if(Min==INF)return -1;//represent no solution at last; sum+=Min; low[v]=-1; for(int j=1;j<=n;j++)//update the length { if(low[j]!=-1&&low[j]>map[j][v]) low[j]=map[j][v]; } } return sum;}int main(){ while(cin>>n>>m) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=INF; int a,b,c; for(int i=1;i<=m;i++) { scanf("%d %d %d",&a,&b,&c); if(map[a][b]>c)map[a][b]=map[b][a]=c;//避免两点之间有多条路径,取最小路径 } int q=kruskal(1);//在任何节点开始找都行,因为他们都必须连在一颗树里 cout<<q<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。