曹旭辉 发表于 2024-12-12 18:34:47

代码随想录第五十七天

prim算法

1.算法根本概念

最小生成树 (Minimum Spanning Tree, MST)：


[*]是图中的一个子图，包罗所有顶点
[*]构成一棵树（无环连通图）
[*]所有边的权重和最小
Prim 算法核心思想：


[*]从单个顶点开始生长
[*]采用贪婪计谋，每次选择最优的当前选择
[*]通过切分定理包管正确性
prim三部曲：

[*]第一步，选距离生成树迩来节点
[*]第二步，迩来节点加入生成树
[*]第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
minDist数组 用来纪录 每一个节点距离最小生成树的迩来距离。
2.例题 53.寻宝

标题形貌
在天下的某个地区，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王计划在这些岛屿上建公路，方便运输。
差别岛屿之间，路途距离差别，国王盼望你可以规划建公路的方案，怎样可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，此中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入形貌
第一行包罗两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。比方：V&#6

1;2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和止境，val代表边的权值。
输出形貌
输出联通所有岛屿的最小路径总距离
输入示例
7 11
1 2 1
1 3 1
1 5 2
2 6

1
2 4 2
2 3 2
3 4 1
4 5 1
5 6

2
5 7 1
6

7 1
输出示例
6

提示信息
数据范围：
2 <&#6

1; V <&#6

1; 10000;
1 <&#6

1; E <&#6

1; 100000;
0 <&#6

1; val <&#6

1; 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6

.
https://i-blog.csdnimg.cn/img_convert/aac5cafda86

59b9b2ad3b88ee89bd4b5.png
思路：
这道题要求我们求出以最小化公路建设长度，确保可以链接到所有岛屿的值，我们可以用prim算法来对其举行解答。我们需要设一个数组专门来存储最小权重，其次我们需要找出局部最优的值，并且每找出一个点我们需要更新最短距离，然后继续寻找下面的节点，最后找出答案就行了。
解答：
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <limits.h>int main(){    int V,E;    int x,y,k;    scanf("%d %d",&V,&E);    int** graph &#6

1; malloc(sizeof(int*)*(V+1));    for(int i &#6

1; 0;i <&#6

1; V;i++)    {      graph &#6

1; malloc(sizeof(int)*(V+1));    }    for(int i &#6

1; 0;i <&#6

1; V;i++)    {      for(int j &#6

1; 0;j <&#6

1; V;j++)      {            graph &#6

1; 10001;      }    }    while(E--)    {      scanf("%d %d %d",&x,&y,&k);      graph &#6

1; k;      graph &#6

1; k;    }    int* minilist &#6

1; malloc(sizeof(int)*(V+1));    for(int i &#6

1; 0;i <&#6

1; V;i++)    {      minilist &#6

1; 10001;    }    bool* istree &#6

1; malloc(sizeof(bool)*(V+1));    for(int i &#6

1; 0;i <&#6

1; V;i++)    {      istree &#6

1; false;    }    for(int i &#6

1; 1;i <&#6

1; V;i++)    {      int cur &#6

1; -1;      int minvalue &#6

1; INT_MAX;      for(int j &#6

1; 1;j <&#6

1; V;j++)      {            if(!istree && minvalue > minilist)            {                minvalue &#6

1; minilist;                cur &#6

1; j;            }      }      istree &#6

1; true;      for(int j &#6

1; 1;j <&#6

1; V;j++)      {            if(!istree && minilist > graph)            {                minilist &#6

1; graph;            }      }    }    int result &#6

1; 0;    for(int i &#6

1; 2;i <&#6

1; V;i++)    {      result +&#6

1; minilist;    }    printf("%d",result);} kruskal算法


[*] Kruskal 算法的核心思想：
按照边的权重从小到大的顺序,选择不会形成环的边来构建最小生成树。
[*] 算法步调:


[*]将图中所有边按权重从小到大排序
[*]初始时,每个顶点都是一个单独的连通分量
[*]依次观察每条边,如果这条边连接的两个顶点不在同一个连通分量中,就选择这条边
[*]利用并查集来判定和合并连通分量
[*]重复这个过程直到选择了n-1条边(n 是顶点数)
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
53.寻宝

标题形貌
在天下的某个地区，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王计划在这些岛屿上建公路，方便运输。
差别岛屿之间，路途距离差别，国王盼望你可以规划建公路的方案，怎样可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，此中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入形貌
第一行包罗两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。比方：V&#6

1;2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和止境，val代表边的权值。
输出形貌
输出联通所有岛屿的最小路径总距离
输入示例
7 11
1 2 1
1 3 1
1 5 2
2 6

1
2 4 2
2 3 2
3 4 1
4 5 1
5 6

2
5 7 1
6

7 1
输出示例
6

提示信息
数据范围：
2 <&#6

1; V <&#6

1; 10000;
1 <&#6

1; E <&#6

1; 100000;
0 <&#6

1; val <&#6

1; 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6

.
https://i-blog.csdnimg.cn/img_convert/aac5cafda86

59b9b2ad3b88ee89bd4b5.png
思路：
为相识决这道题，我们首先将所有边按权重从小到大排序，然后从最小权重的边开始选择。每次选择一条边时，通过并查集判定这条边的两个顶点是否已经连通（在同一个集合中）。如果不连通，就将这条边加入最小生成树，并在并查集中合并这两个顶点地点的集合；如果已经连通，分析加入这条边会形成环，就跳过这条边。当选择的边数到达顶点数减一时，算法竣事，此时所有选中边的权重之和就是最小生成树的总权重。这个过程中，并查集主要用于快速判定顶点是否连通和合并顶点地点的集合。
解答：
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <limits.h>struct Edges{    int l,r,value;};int compare(const void* a,const void* b){   return ((struct Edges*)a)->value - ((struct Edges*)b)->value;}int N &#6

1; 10001;int* father;void init(){    father &#6

1; malloc(sizeof(int)*N);    for(int i &#6

1; 0;i < N;i++)    {      father &#6

1; i;    }}int find(int x){    if(father !&#6

1; x)father &#6

1; find(father);    return father;}void unite(int x,int y){    x &#6

1; find(x);    y &#6

1; find(y);    if(x &#6

1;&#6

1; y)return;    father &#6

1; x;}int main(){    int V,E;    int result_val &#6

1; 0;    scanf("%d %d",&V,&E);    struct Edges* edges &#6

1; malloc(sizeof(struct Edges)*E);    for(int i &#6

1; 0; i < E;i++)    {      scanf("%d %d %d",&edges.l,&edges.r,&edges.value);    }    qsort(edges,E,sizeof(struct Edges),compare);    init();    int count &#6

1; 0;    for(int i &#6

1; 0;i < E;i++)    {      int x &#6

1; find(edges.l);      int y &#6

1; find(edges.r);      if(x !&#6

1; y)      {            result_val +&#6

1; edges.value;            unite(x,y);            count++;            if(count &#6

1;&#6

1; V-1)            {                break;            }      }    }    printf("%d",result_val);}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: 代码随想录第五十七天