首页 > 其他分享 >【学习笔记】最小生成树

【学习笔记】最小生成树

时间:2024-07-26 16:11:08浏览次数:18  
标签:Prim int Kruskal 最小 笔记 生成 算法 edge

提示:

  • 文中代码是按照洛谷题目 P3366【模板】最小生成树 编写的。
  • 讲的有可能不全部正确,请指出。
  • 伪代码并不标准,但能看。

MST 介绍

MST(最小生成树,全称 Minimum Spanning Tree)是指一张有向连通图中边权之和最小的一棵树。

最小生成树的构造目前其实有三种算法,常用的 Kruskal、Prim 和不常用(我没见过)的 Boruvka 算法(可以看 OI Wiki - 最小生成树 - Boruvka 算法)。Boruvka 算法因为不常见和没学过这里不讲了。

Prim

介绍

Prim 是一种以贪心为主要思想的 MST 算法。

具体过程如下:

  1. 建立一个点集,点集中先包含一个点。
  2. 找到距离点集最近的点,将其加入。
  3. 重复 2.,直到整张图都进入点集。

这样就可以找到一个 MST,这是一个找点的过程。

伪代码

while not 所有点进点集:
	node tmp
	for node X in 所有点集:
		if not X in 点集 and 到 tmp 距离 > 到 X 距离:
			tmp <- x
	tmp 进 点集

代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5005;
int q[N][N], dis[N];
bool vis[N];
int n, m;
long long ans;

void prim(int x){
    dis[x] = 0;
    for (int i = 1; i <= n; i ++){
        int cur = -1;
        for (int j = 1; j <= n; j ++){
            if (!vis[j] && (cur == -1 || dis[j] < dis[cur])){
                cur = j;
            }
        }

        if (dis[cur] >= INF){
            ans = INF;
            return ;
        }
        
        ans += dis[cur];
        vis[cur] = 1;

        for (int k = 1; k <= n; k ++){
            if (!vis[k]) dis[k] = min(dis[k], q[cur][k]);
        }
    }
}

int main(){
    memset(q, 0x3f, sizeof(q));
    memset(dis, 0x3f, sizeof(dis));
    cin >> n >> m;

    for (int i = 1, u, v, w; i <= m; i ++){
        cin >> u >> v >> w;
        q[u][v] = min(q[u][v], w);
        q[v][u] = min(q[v][u], w);
    }

    prim(1);
    if (ans >= INF) puts("orz");
    else cout << ans;
}

Kruskal

介绍

Kruskal 也是一种贪心思想的算法,但与 Prim 的不同之处在于 Prim 是加点,而 Kruskal 是加边。其过程如下:

  1. 只看点集,不看边,认为每一个点孤立。
  2. 找到最小的边,将他连接的点加入集合。
  3. 继续,知道所有点加入集合。

可以证明,Kruskal 进行到最后一定是最小生成树。

伪代码

while not 所有点入集合:
	for edge X in 所有未使用边(边权从小到大):
		X.u, X.v -> 集合
		X 标记使用

代码

为了更方便,Kruskal 算法巧妙地运用了并查集,他通过记录每个节点对应的集合的根节点,记录不同的集合。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
struct node{
	int x, y, z;
} edge[N];
int fa[N];

bool cmp(node a, node b){
	return a.z < b.z;
}

int find(int x){
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main(){
	int n, m;
	cin >> n >> m;
	
	for (int i = 1; i <= m; i ++){
		cin >> edge[i].x >> edge[i].y >> edge[i].z;
	}
	
	sort(edge, edge + 1 + m, cmp);
	
	for (int i = 1; i <= n; i ++){
		fa[i] = i;
	}
	
	long long sum = 0;
	for (int i = 1; i <= m; i ++){
		int x = find(edge[i].x);
		int y = find(edge[i].y);
		if (x != y){
			fa[y] = x;
			sum += edge[i].z;
		}
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i ++){
		if (i == find(i)) ans ++;
	}
	
	if (ans > 1) puts("orz");
	else cout << sum;
}

标签:Prim,int,Kruskal,最小,笔记,生成,算法,edge
From: https://www.cnblogs.com/lym12/p/18325453/mst_study

相关文章

  • flutter 根据网址生成二维码
    依赖qr_flutter:^4.1.0#二维码代码Center(child:Column(children:[Center(child:QrImageView(data:'https://www.baidu.com/',version:QrVersions.auto,......
  • Pytest:测试运行后如何显示生成的报告?
    我将pytest与pytest-html插件结合使用,该插件在测试运行后生成HTML报告。我使用自动连接的会话固定装置自动打开生成的HTML报告浏览器:@pytest.fixture(scope="session",autouse=True)defsession_wrapper(request):print('Sessionwrapperinit...')......
  • 基于CAT的VBM和SBM计算学习笔记(二)感兴趣区(ROI)&全脑体积(TIV)
    前言 回顾一下上文:之前学习了用CAT计算VBM灰质体积的预处理过程,主要分为三步:Preprocessing:从使用DPABI生成T1图像再校准T1原点。Segement:CAT软件自带的自动化分割。Smooth:最后用Spm进行平滑操作。基于CAT的VBM和SBM计算学习笔记(一)VBMhttps://mp.csdn.net/mp_blog/creat......
  • Kruskal 重构树学习笔记
    Kruskal想必大家都不陌生,这是一种求最小生成树的算法。关于Kruskal重构树,就是把一张图转化为一个堆。具体来说,我们可以处理出来从\(u\)到\(v\)路径中的点权或边权的极值。比如上面这张图(前为编号,[]内为点权),我们可以将它重构为小顶堆,如下请注意,这棵树有着严格的方向,......
  • 如何在streamlit python中流式传输由LLM生成的输出
    代码:fromlangchain_community.vectorstoresimportFAISSfromlangchain_community.embeddingsimportHuggingFaceEmbeddingsfromlangchainimportPromptTemplatefromlangchain_community.llmsimportLlamaCppfromlangchain.chainsimportRetrievalQAimports......
  • 导入FontForge生成字体
    导入FontForge生成字体本教程由做字体网(www.zuoziti.com)友情提供!本教程是制作手写字体系列教程,建议从序言部分开始阅读学习!如需交流,请加QQ924268440本节视频教程FontForge导入步骤前面我们切割好了小图片,下面就要正式生成字体了。以下教程是用FontForge导入python......
  • 不依赖本地系统调度jupyter笔记本
    是否可以在不依赖本地系统的情况下调度使用一个驱动器文件的jupyter笔记本。我在公司的共享点中创建了一个驱动器的快捷方式,并在我的jupyter笔记本中读取这些文件(笔记本从onedrive读取csv文件)。我目前每天在jupyterlab中安排笔记本,但这是在我的本地系统中,需要每天打开我......
  • 生成树
    对一个具有n个点的连通图进行遍历,对于遍历后的子图,其包含原图中所有的点且保持图连通,最后的结构一定是一个具有n-1条边的树,通常称为生成树。右边两个子图,就是左边图的生成树。在生成树问题中,最常见的就是最小生成树问题,所谓最小生成树,就是对于一个有n个点的无向连通图的生成树,其......
  • 基于.NET开源、强大易用的短链生成及监控系统
    前言今天大姚给大家分享一个基于.NET开源(MITLicense)、免费、强大易用的短链生成及监控系统:SuperShortLink。项目介绍SuperShortLink是一个基于.NET开源(MITLicense)、免费、强大易用的短链生成及监控系统,包含了短URL的生成、短URL跳转长URL、短URL访问统计以及Web后台监控页面,......
  • C++自学笔记17(const和mutable)
    const在之前的笔记中我们出现很多次constchar*name=“shaojie”,定义一个不可变指针存放字符串。不可变就来自const,表示“只读、常量”为什么需要它呢?我们需要一些东西不可被修改。const加数据变量#include<iostream>intmain(){constintMAX_AGE=99;M......