255 字
1 分钟
数据库系统工程师—3.7图的相关算法
图的相关算法
生成树与最小生成树
生成树
生成树：设图G=(V,E)是个连通图，如果其子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
最小生成树
最小生成树：对于连通网来说，边是带权值的，生成树的各边也带权值，于是就把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。
普里姆算法
- 以顶点为主
- 取任意一点，寻找与之距离最近（权值）的点和线，加入其中作为一个整体
- 重复上述操作，直至最小生成树形成
克鲁斯卡尔算法
- 以边为主
- 取最小边，把边两侧顶点记录下来，循环以上操作直至形成
图源：
[AcWing]859. Kruskal算法求最小生成树（C++实现）Kruskal算法模板题_kruskal模板题-CSDN博客
数据库系统工程师—3.7图的相关算法
https://minthana.github.io/blog/posts/数据库系统工程师-3-7图的相关算法/