搜索与图论-最小生成树(Prim 算法和 Kruskal 算法)

简介: 搜索与图论-最小生成树(Prim 算法和 Kruskal 算法)

文章目录

一、最小生成树简介

二、Prim 算法实现最小生成树

1. Prim 算法

2. Prim 算法具体实现详见例题 Prim 算法求最小生成树。

三、Kruskal 算法实现最小生成树

1. Kruskal 算法思路

2. Kruskal 算法实现过程

3. Kruskal 算法具体实现详见例题 Kruskal 算法求最小生成树。

四、Prim 算法例题——Prim 算法求最小生成树

五、Kruskal 算法例题——Kruskal 算法求最小生成树


一、最小生成树简介

最小生成树是指一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。

在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集且为无循环图,使得联通所有结点的的 w(T) 最小,则此 T 为 G 的最小生成树。

最小生成树是最小权重生成树的简称,可以用 Kruskal(克鲁斯卡尔)算法或 Prim(普里姆)算法求出。

这里需要注意的是:

(1) 最小生成树可能有多个,但边的权值之和总是唯一且最小的。

(2) 最小生成树的边数 = 定点数 - 1,砍掉一条则不连通,增加一条则会出现回路。

(3) 若一个连通图本身就是一颗树,则其最小生成树就是它本身。

(4) 只有连通图才有生成树,非连通图只有生成森林


二、Prim 算法实现最小生成树

1. Prim 算法


  • Prim 算法采用的是一种贪心的策略。
  • 每次将离连通部分的最近的点和点对应的边加入的连通部分,连通部分逐渐扩大,最后将整个图连通起来,并且边长之和最小。
  • 我们将图中各个节点用数字 1 ~ n 编号。
  • 120d9c1c40c04171b318174693ce6724.png


要将所有景点连通起来,并且边长之和最小,步骤如下:

(1) 用一个 state 数组表示节点是否已经连通。state[i] 为真,表示已经连通,state[i] 为假,表示还没有连通。初始时,state 各个元素为假。即所有点还没有连通。

用一个 dist 数组保存各个点到连通部分的最短距离,dist[i] 表示 i 节点到连通部分的最短距离。初始时,dist 数组的各个元素为无穷大。

用一个 pre 数组保存节点的是和谁连通的。pre[i] = k 表示节点 i 和节点 k 之间需要有一条边。初始时,pre 的各个元素置为 -1。

00fa466fd0fe473f8cdb01460bdee2ab.png

(2) 从 1 号节点开始扩充连通的部分,所以 1 号节点与连通部分的最短距离为 0,即 disti[1] 置为 0。

e4b09479c3814a30b04644b18eb09591.png

(3) 遍历 dist 数组,找到一个还没有连通起来,但是距离连通部分最近的点,假设该节点的编号是 i。i 节点就是下一个应该加入连通部分的节点,stata[i] 置为 1。

用青色点表示还没有连通起来的点,红色点表示连通起来的点。

这里青色点中距离最小的是 dist[1],因此 state[1] 置为 1。

e2f1d8299ac34102a2c5c38d0a412113.png


(4)遍历所有与 i 相连但没有加入到连通部分的点 j,如果 j 距离连通部分的距离大于 i j 之间的距离,即 dist[j] > w[i][j](w[i][j] 为 i,j 节点之间的距离),则更新 dist[j] 为 w[i][j]。

这时候表示,j 到连通部分的最短方式是和 i 相连,因此,更新 pre[j] = i。

与节点 1 相连的有 2, 3, 4 号节点。1->2 的距离为 100,小于 dist[2],dist[2] 更新为 100,pre[2] 更新为1。1->4 的距离为 140,小于 dist[4],dist[4] 更新为 140,pre[2] 更新为1。1->3 的距离为 150,小于 dist[3],dist[3] 更新为 150,pre[3] 更新为1。

26a0973cc26240e8a3584971792a2a8d.png


  • (5)重复 3,4 步骤,直到所有节点的状态都被置为 1。
  • 这里青色点中距离最小的是 dist[2],因此 state[2] 置为 1


515f0b56baf94e038bc45a588700d70c.png


与节点 2 相连的有 5, 4 号节点。2->5 的距离为 80,小于 dist[5],dist[5] 更新为 80,pre[5] 更新为 2。2->4 的距离为 80,小于 dist[4],dist[4] 更新为 80,pre[4] 更新为 2。

5d1f27aa1c4e436b96052e7f672c4737.png



  • 选 dist[4],更新 dist[3],dist[5],pre[3],pre[5]。


48fe551a7dd54ff88f8c1531f20208e5.png


79778a983fd14ceeb6043faffa056d21.png选 dist[5],没有可更新的。

2079f3d974df4892bf702e40bdddc5df.png


选 dist[3],没有可更新的。


1cc4ed896ee1473a93fb289a8e91366e.png


此时 dist 数组中保存了各个节点需要修的路长,加起来就是。pre 数组中保存了需要选择的边。

48b45a52e3fd46ffb68a9643f511d838.png


2. Prim 算法具体实现详见例题 Prim 算法求最小生成树。

三、Kruskal 算法实现最小生成树

1. Kruskal 算法思路

将所有边按照权值的大小进行升序排序,然后从小到大一一判断。

如果这个边与之前选择的所有边不会组成回路,就选择这条边分;反之,舍去。

直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为:使用并查集。

在初始状态下给各个个顶点在不同的集合中。

遍历过程的每条边,判断这两个顶点的是否在一个集合中。

如果边上的这两个顶点在一个集合中,说明两个顶点已经连通,这条边不要。如果不在一个集合中,则要这条边。


2. Kruskal 算法实现过程


举个例子,下图一个连通网,Kruskal 算法查找图 1 对应的最小生成树,需要经历以下几个步骤:

4ddd10f2a92a4291b0ce1f424f685870.png



  • 将连通网中的所有边按照权值大小做升序排序:


c569defc9ab7472ba3408c4fd2aae2bb.png


从 B-D 边开始挑选,由于尚未选择任何边组成最小生成树,且 B-D 自身不会构成环路,所以 B-D 边可以组成最小生成树。

86b8d9d365014ab9986828f2097815fc.png


  • D-T 边不会和已选 B-D 边构成环路,可以组成最小生成树:

aae4e56f690541889bb1d2db63e6e718.png



  • A-C 边不会和已选 B-D、D-T 边构成环路,可以组成最小生成树:

33f5f4fc4f464b4f896bd644367f453c.png


  • C-D 边不会和已选 A-C、B-D、D-T 边构成环路,可以组成最小生成树:


78223e86d54145a4b2679e394fa22ae3.png



C-B 边会和已选 C-D、B-D 边构成环路,因此不能组成最小生成树:

20a7e39de437460cacd6db52203efb9b.png

B-T 、A-B、S-A 三条边都会和已选 A-C、C-D、B-D、D-T 构成环路,都不能组成最小生成树。而 S-A 不会和已选边构成环路,可以组成最小生成树

7186d92a8462498cabd2bd31402d4edd.png


如图下图 所示,对于一个包含 6 个顶点的连通网,我们已经选择了 5 条边,这些边组成的生成树就是最小生成树。

5000cbffce924d078b1601e71df54cf7.png



3. Kruskal 算法具体实现详见例题 Kruskal 算法求最小生成树。

四、Prim 算法例题——Prim 算法求最小生成树

题目描述


给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G = (V,E),其中 V 表示图中点的集合,E 表示图中边的集合,n = |V|,m = |E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。


输入格式


第一行包含两个整数 n 和 m。

接下来 m 行,每行包含三个整数 u,v,w,表示点 u 和点 v 之间存在一条权值为 w 的边。


输出格式


共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。


数据范围


1 ≤ n ≤ 500

1 ≤ m ≤ 1e5

图中涉及边的边权的绝对值均不超过 10000。


输入样例


4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4


输出样例


6


实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
//dist[N]表示边长
int dist[N];
//st[N]表示是否使用过
bool st[N];
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        if (i && dist[t] == INF)
        {
            return INF;
        }
        if (i)
        {
            res += dist[t];
        }
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        //可能会有重边,取最小值
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF) 
    {
        puts("impossible");
    }
    else
    {
        cout << t << endl;
    }
    return 0;
}


五、Kruskal 算法例题——Kruskal 算法求最小生成树

题目描述



给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G = (V,E),其中 V 表示图中点的集合,E 表示图中边的集合,n = |V|,m = |E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。


输入格式


第一行包含两个整数 n 和 m。

接下来 m 行,每行包含三个整数 u,v,w,表示点 u 和点 v 之间存在一条权值为 w 的边。


输出格式


共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。


数据范围


1 ≤ n ≤ 1e5

1 ≤ m ≤ 2∗1e5

图中涉及边的边权的绝对值均不超过 1000。


输入样例


4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4


输出样例


6



实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];
int find(int x)
{
    if (p[x] != x)
    {
        p[x] = find(p[x]);
    }
    return p[x];
}
int kruskal()
{
    sort(edges, edges + m);
    for (int i = 1; i <= n; i ++ ) 
    {
        p[i] = i;    // 初始化并查集
    }
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1)
    {
        return INF;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    int t = kruskal();
    if (t == INF)
    {
        puts("impossible");
    }
    else 
    {
        cout << t << endl;
    }
    return 0;
}














相关文章
|
25天前
|
算法 搜索推荐 数据库
二分搜索:高效的查找算法
【10月更文挑战第29天】通过对二分搜索的深入研究和应用,我们可以不断挖掘其潜力,为各种复杂问题提供高效的解决方案。相信在未来的科技发展中,二分搜索将继续发挥着重要的作用,为我们的生活和工作带来更多的便利和创新。
40 1
|
2月前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
|
3月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
59 2
|
2月前
|
算法 决策智能
基于prim算法求出网络最小生成树实现网络社团划分和规划
该程序使用MATLAB 2022a版实现路线规划,通过排序节点权值并运用Prim算法生成最小生成树完成网络规划。程序基于TSP问题,采用遗传算法与粒子群优化算法进行路径优化。遗传算法通过编码、选择、交叉及变异操作迭代寻优;粒子群优化算法则通过模拟鸟群觅食行为,更新粒子速度和位置以寻找最优解。
|
2月前
|
存储 算法 C++
【搜索算法】 跳马问题(C/C++)
【搜索算法】 跳马问题(C/C++)
|
2月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
2月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
2天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
14天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。