Graph的最小生成树算法

目录

1. 关于Prim算法在图的最小生成树计算中的简要介绍
2. Prim算法的具体实例分析及其详细解析
3. Prim算法对应的代码实现部分
4. Kruskal算法在图的最小生成树计算中的概述
5. Kruskal算法的实际应用示例及其深入讲解
6. Kruskal算法的代码实现模块

图的最小生成树算法之Prim算法简介

1、生成树
当连通图G中存在一个子图，该子图为一棵树，并且能够涵盖G中的全部顶点时，该子图被定义为G的生成树（Spanning Tree）。
生成树是连通图中包含所有顶点的最小连通子图。
对于同一张图而言，其生成树并非唯一。通过从不同顶点开始进行遍历操作，可以得到多个不同的生成树。
2.算法简单描述

1).输入：一个具有权重的连通图，其中顶点集合记为V，边集合记为E；

2).初始化：设定Vnew = {x}，其中x是从集合V中任意选取的一个节点（作为起点），同时Enew = {}，即初始为空集；

3).持续执行以下步骤，直至Vnew与V完全一致：

a.从集合E中挑选出一条权值最小的边(u, v)，其中u属于集合Vnew，而v不属于该集合，并且v必须属于V（若存在多条满足上述条件且权值相同的边，则可任选其一）；

b.将节点v添加至集