最后复习之最小生成树_最小生成树优缺点

作者：煮酒与君饮 | 2024-07-27 17:48:56

踩

最小生成树优缺点

这里写图片描述
就我所知的求最小生成树的方法有两种，prim算法和kruskal算法。各有优缺点，下面我来详细的介绍一下这两种算法。
一、prim算法：
基本过程：刚开始把1放入目前找到的最小生成树，然后不断地寻找离已知的最小生成树最近的点，将其放入最小生成树并对这棵树进行更新。
根据这个找点的过程可知prim适合稠密图。
证明：首先每个点和最小生成树的连边都是这个点到其他每个点的连边里边权尽可能小的边，因为既要考虑边权又要考虑构成一棵树。既然要考虑构成树，就可以不断地找和树相连的点，既然要考虑边权，那么每次找和树相邻的边权最小的点就行了，那么上面的基本过程真是再好不过了是吧。。。（强行证明）
代码都是以模板题codevs1078最小生成树为例。

#include<cstdio>
#include<iostream>
using namespace std;
int g[110][110],dis[1
2
3
4

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/891122