首页 > 代码库 > 最小生成树学习总结

最小生成树学习总结

2024-07-12 14:04:10   221人阅读

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;}


联系
我们