搜索与图论-最小生成树(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;
}














目录
打赏
0
0
0
0
2
分享
相关文章
基于Qlearning强化学习的机器人迷宫路线搜索算法matlab仿真
本内容展示了基于Q-learning算法的机器人迷宫路径搜索仿真及其实现过程。通过Matlab2022a进行仿真,结果以图形形式呈现,无水印(附图1-4)。算法理论部分介绍了Q-learning的核心概念,包括智能体、环境、状态、动作和奖励,以及Q表的构建与更新方法。具体实现中,将迷宫抽象为二维网格世界,定义起点和终点,利用Q-learning训练机器人找到最优路径。核心程序代码实现了多轮训练、累计奖励值与Q值的可视化,并展示了机器人从起点到终点的路径规划过程。
72 0
阿里云 AI 搜索开放平台:从算法到业务——AI 搜索驱动企业智能化升级
本文介绍了阿里云 AI 搜索开放平台的技术的特点及其在各行业的应用。
406 3
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
122 24
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
224 62
算法系列之搜索算法-深度优先搜索DFS
|
5月前
|
算法系列之搜索算法-广度优先搜索BFS
广度优先搜索(BFS)是一种非常强大的算法,特别适用于解决最短路径、层次遍历和连通性问题。在面试中,掌握BFS的基本实现和应用场景,能够帮助你高效解决许多与图或树相关的问题。
224 1
算法系列之搜索算法-广度优先搜索BFS
【狂热算法篇】并查集:探秘图论中的 “连通神器”,解锁动态连通性的神秘力量(通俗易懂版)
【狂热算法篇】并查集:探秘图论中的 “连通神器”,解锁动态连通性的神秘力量(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
基于遗传优化ELM网络的时间序列预测算法matlab仿真
本项目实现了一种基于遗传算法优化的极限学习机(GA-ELM)网络时间序列预测方法。通过对比传统ELM与GA-ELM,验证了参数优化对非线性时间序列预测精度的提升效果。核心程序利用MATLAB 2022A完成,采用遗传算法全局搜索最优权重与偏置,结合ELM快速训练特性,显著提高模型稳定性与准确性。实验结果展示了GA-ELM在复杂数据中的优越表现,误差明显降低。此方法适用于金融、气象等领域的时间序列预测任务。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等