最小生成树算法：Kruskal 与 Prim算法 |
您所在的位置：网站首页 › kruskal算法实现 › 最小生成树算法：Kruskal 与 Prim算法 |
|
Ⅰ. 最小生成树 连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。 若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边。因此构造最小生成树的准则有三条： 只能使用图中的边来构造最小生成树 只能使用恰好 n-1 条边来连接图中的 n 个顶点 选用的 n-1 条边不能构成回路构造最小生成树的方法：Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的贪心策略。 贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解（也就是说这两种算法不是万能的）。 🔴 并且 最小生成树是不唯一的！ Ⅱ、Kruskal算法任给一个有 n 个顶点的连通网络 N={V,E}， 首先构造一个由这 n 个顶点组成、不含任何边的图 G={V,NULL}，其中每个顶点自成一个连通分量， 其次不断从 E 中取出权值最小的一条边 ( 若有多条任取其一 ) ，若该边的两个顶点来自不同的连通分量，则将此边加入到 G 中。 如此重复，直到所有顶点在同一个连通分量上为止。 核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。 具体实现的时候，由于考虑到每次都要选最小的一条边，那这里就用 优先级队列，也就是一个堆，来进行存放，并且是一个小堆，每次堆顶是最小的边！一般来说我们操作的一般是无向图，所以只需要将矩阵中的上三角行列式中的边入队列即可~ 除此之外，还要 判断连接起来的边会不会形成环路，这个时候我们就可以用 并查集 来判断，每次将选择的边对应的邻接顶点加入到并查集中，然后每次新增边的时候 判断一下新增的边引入的邻接顶点是否已经在并查集中，是的话说明形成回路了，则不选这条边~ （ 🦅 并查集的具体实现翻笔记查找 ） 另外我们还需要单独 弄个结构体包装一下边的属性： // 为下面一些算法如Kruskal算法做准备的 struct Edge { size_t _srci; size_t _dsti; W _weight; Edge(size_t srci, size_t dsti, const W& weight) :_srci(srci) , _dsti(dsti) , _weight(weight) {} // 下面要比较边的大小，所以要重载一下比较 bool operator>(const Edge& e) const { return _weight > e._weight; } };// 下面Kruskal算法接收的参数需要用到默认构造函数 Graph() = default; typedef Graph Self; // Kruskal算法 // 下面的minTree是接收的一般是未初始化的图，所以我们要有默认的构造函数 W Kruskal(Self& minTree) { // 初始化一下最小生成树的模板 size_t n = _vertexs.size(); minTree._vIndexMap = _vIndexMap; minTree._vertexs = _vertexs; minTree._matrix.resize(n); for (size_t i = 0; i < n; ++i) { // 默认这些顶点都是不相通的 minTree._matrix[i].resize(n, MAX_W); } // 由于我们要从小到大排序，所以得传仿函数过去 priority_queue pq; // 将矩阵中的边入队列 for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { // 由于是无向图，我们只需要将上三角行列式中的边加入即可 if (i < j && _matrix[i][j] != MAX_W) { pq.push(Edge(i, j, _matrix[i][j])); } } } // 贪心算法，从最小的边开始选 int size = 0; // 选出n-1条边，所以用size来计数 W sum = W(); // 最后结束的时候返回最小生成树的总权值 UnionFindSet ufs(n); // 并查集 while (!pq.empty()) { Edge min = pq.top(); pq.pop(); // 判断是否成环 if (!ufs.IsInSameSet(min._srci, min._dsti)) { cout b [2]->c [3]->d [4]->e [5]->f [6]->g [7]->h [8]->i 0 1 2 3 4 5 6 7 8 0 * 4 * * * * * * * 1 4 * 8 * * * * * * 2 * 8 * 7 * 4 * * 2 3 * * 7 * 9 * * * * 4 * * * 9 * * * * * 5 * * 4 * * * 2 * * 6 * * * * * 2 * 1 * 7 * * * * * * 1 * * 8 * * 2 * * * * * *Ⅲ、Prim算法除了 Kruskal 算法以外，普里姆算法（Prim 算法）也是常用的最小生成树算法。虽然在效率上差不多。但是贪心的方式和 Kruskal 完全不同。prim 算法的核心信仰是：从已知扩散寻找最小。它的实现方式和 Dijkstra算法相似但稍微有所区别，Dijkstra 是求单源最短路径。而每计算一个点需要对这个点从新更新距离。而 prim 甚至不用更新距离。直接找已知点的邻边最小加入即可！ Prim算法原理： 以某一个点开始，寻找当前该点可以访问的所有的边；在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；寻找当前集合可以访问的所有边，重复步骤2的过程，直到没有新的点可以加入；此时由所有边构成的树即为最小生成树。在实现过程中，考虑到每次要挑选已有点的边的最小权值问题，所以我们还是得用**优先级队列，效率会比较高一些！但是要注意的是，我们不能一开始就将所有的边入队列，因为 Prim 算法是通过顶点来找边的，只能找已经确认的点的邻接边，所以我们只能边走边将邻接边入队列**！ 除此之外，我们还 需要判断一下加入的边会不会构成环，考虑到 Prim 算法与 Kruskal 算法不同的点也在于 Prim 算法是以点为对象的，所以我们时时刻刻都知道哪些点是已经确定的，所以我们可以用一个 vector 来标记这些顶点，true 表示这些顶点在这个集合，false 表示这些顶点不在！（当然也可以用两个 set ，一个 set 存储已经存在的顶点，另一个 set 存储还没有确认的顶点，然后分别去查找、插入、删除。但是显然没有我们用 vector 快，所以这里我们选用 vector！） // Prim算法 // minTree是接收的未初始化的图，所以我们要有默认的构造函数 // src是首个顶点 W Prim(Self& minTree, const V& src) { size_t srci = GetVertexIndex(src); // 初始化图，与Kruskal算法一样 size_t n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._vIndexMap = _vIndexMap; minTree._matrix.resize(n); for (size_t i = 0; i < n; ++i) minTree._matrix[i].resize(n, MAX_W); // 使用vector来存储顶点的确认情况：是否在生成树中已经确认（默认是不确认） // true表示确认存在 // false表示还不确认存在 vector vState(n, false); vState[srci] = true; // 注意将首个顶点设置为true // 初始化优先级队列（与Kruskal算法一样） // 先将与首个顶点邻接的边入队列 priority_queue pq; for (size_t i = 0; i < n; ++i) { if (_matrix[srci][i] != MAX_W) pq.push(Edge(srci, i, _matrix[srci][i])); } size_t size = 0; W sum = W(); cout h [8]->i 0 1 2 3 4 5 6 7 8 0 * 4 * * * * * 8 * 1 4 * * * * * * * * 2 * * * 7 * 4 * * 2 3 * * 7 * 9 * * * * 4 * * * 9 * * * * * 5 * * 4 * * * 2 * * 6 * * * * * 2 * 1 * 7 8 * * * * * 1 * * 8 * * 2 * * * * * *Ⅳ、两种最小生成树算法的区别两种算法其实在效率是差不多的，只不过实现的方式是不一样的，具体问题具体分析！ 🔴 总的来说，Prim 算法是 以点为对象，挑选与点相连的最短边来构成最小生成树。而 Kruskal 算法是以边为对象，不断地加入新的不构成环路的最短边来构成最小生成树。 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |