代码随想录第五十七天
prim算法
1.算法基本概念
最小生成树 (Minimum Spanning Tree, MST)：
- 是图中的一个子图，包含所有顶点
- 构成一棵树（无环连通图）
- 所有边的权重和最小
Prim 算法核心思想：
- 从单个顶点开始生长
- 采用贪心策略，每次选择最优的当前选择
- 通过切分定理保证正确性
prim三部曲：
- 第一步，选距离生成树最近节点
- 第二步，最近节点加入生成树
- 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
minDist数组 用来记录 每一个节点距离最小生成树的最近距离。
2.例题 53.寻宝
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=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 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6.
思路：
这道题要求我们求出以最小化公路建设长度，确保可以链接到所有岛屿的值，我们可以用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 = malloc(sizeof(int*)*(V+1));
for(int i = 0;i <= V;i++)
{
graph[i] = malloc(sizeof(int)*(V+1));
}
for(int i = 0;i <= V;i++)
{
for(int j = 0;j <= V;j++)
{
graph[i][j] = 10001;
}
}
while(E--)
{
scanf("%d %d %d",&x,&y,&k);
graph[x][y] = k;
graph[y][x] = k;
}
int* minilist = malloc(sizeof(int)*(V+1));
for(int i = 0;i <= V;i++)
{
minilist[i] = 10001;
}
bool* istree = malloc(sizeof(bool)*(V+1));
for(int i = 0;i <= V;i++)
{
istree[i] = false;
}
for(int i = 1;i <= V;i++)
{
int cur = -1;
int minvalue = INT_MAX;
for(int j = 1;j <= V;j++)
{
if(!istree[j] && minvalue > minilist[j])
{
minvalue = minilist[j];
cur = j;
}
}
istree[cur] = true;
for(int j = 1;j <= V;j++)
{
if(!istree[j] && minilist[j] > graph[cur][j])
{
minilist[j] = graph[cur][j];
}
}
}
int result = 0;
for(int i = 2;i <= V;i++)
{
result += minilist[i];
}
printf("%d",result);
}
kruskal算法
-
Kruskal 算法的核心思想：
按照边的权重从小到大的顺序,选择不会形成环的边来构建最小生成树。
-
算法步骤:
- 将图中所有边按权重从小到大排序
- 初始时,每个顶点都是一个单独的连通分量
- 依次考察每条边,如果这条边连接的两个顶点不在同一个连通分量中,就选择这条边
- 使用并查集来判断和合并连通分量
- 重复这个过程直到选择了n-1条边(n 是顶点数)
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
53.寻宝
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=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 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6.
思路：
为了解决这道题，我们首先将所有边按权重从小到大排序，然后从最小权重的边开始选择。每次选择一条边时，通过并查集判断这条边的两个顶点是否已经连通（在同一个集合中）。如果不连通，就将这条边加入最小生成树，并在并查集中合并这两个顶点所在的集合；如果已经连通，说明加入这条边会形成环，就跳过这条边。当选择的边数达到顶点数减一时，算法结束，此时所有选中边的权重之和就是最小生成树的总权重。这个过程中，并查集主要用于快速判断顶点是否连通和合并顶点所在的集合。
解答：
#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 = 10001;
int* father;
void init()
{
father = malloc(sizeof(int)*N);
for(int i = 0;i < N;i++)
{
father[i] = i;
}
}
int find(int x)
{
if(father[x] != x)father[x] = find(father[x]);
return father[x];
}
void unite(int x,int y)
{
x = find(x);
y = find(y);
if(x == y)return;
father[y] = x;
}
int main()
{
int V,E;
int result_val = 0;
scanf("%d %d",&V,&E);
struct Edges* edges = malloc(sizeof(struct Edges)*E);
for(int i = 0; i < E;i++)
{
scanf("%d %d %d",&edges[i].l,&edges[i].r,&edges[i].value);
}
qsort(edges,E,sizeof(struct Edges),compare);
init();
int count = 0;
for(int i = 0;i < E;i++)
{
int x = find(edges[i].l);
int y = find(edges[i].r);
if(x != y)
{
result_val += edges[i].value;
unite(x,y);
count++;
if(count == V-1)
{
break;
}
}
}
printf("%d",result_val);
}
原文地址：https://blog.csdn.net/2301_80630236/article/details/144406622
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！