【数据结构与算法】第十七、十八章：加权无向图、最小生成树（切分定理、贪心算法、Prim算法、kruskal算法）

2024-04-28 08:38
文章标签 算法 数据结构 最小 生成 贪心 切分 定理 加权 prim 十八 kruskal 第十七 无向

本文主要是介绍【数据结构与算法】第十七、十八章：加权无向图、最小生成树（切分定理、贪心算法、Prim算法、kruskal算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

17、加权无向图

加权无向图是一种为每条边关联一个权重值或是成本的图模型。

这种图能够自然地表示许多应用。

在一副航空图中，边表示航线，权值则可以表示距离或是费用。

在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条线所需的时间。

此时很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？

在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4，0-2-4，0-5-3-4，通过哪条路径到达4顶点最好呢？

此时就要考虑，那条路径的成本最低

在这里插入图片描述

17.1、边的表示

加权无向图中的边不能简单的使用v-w两个顶点表示了，而必须要给边 关联一个权重值，因此可以使用 对象 来描述一条边

在这里插入图片描述

17.2、加权无向图的实现

  • API

在这里插入图片描述

  • 代码
package chapter17;import chapter03.Queue;/*** @author 土味儿* Date 2021/9/16* @version 1.0* 加权无向图*/
public class EdgeWeightedGraph {/*** 顶点数量*/private final int vNum;/*** 边数量*/private int eNum;/*** 邻接表*/private Queue<Edge>[] adj;/*** 构造器* @param vNum*/public EdgeWeightedGraph(int vNum) {// 初始化顶点数量this.vNum = vNum;// 初始化边数量this.eNum = 0;// 初始化邻接表this.adj = new Queue[vNum];// 初始化邻接表中的空队列for (int i = 0; i < vNum; i++) {this.adj[i] = new Queue<Edge>();}}/*** 得到顶点数量* @return*/public int getVNum(){return vNum;}/*** 得到边数量* @return*/public int geteNum(){return eNum;}/*** 添加一条边v-w* @param e*/public void addEdge(Edge e){// 因为是无向图，让边e同时出现在e的两个顶点的邻接表中int v = e.either();int w = e.other(v);this.adj[v].enQueue(e);this.adj[w].enQueue(e);// 边数量加1eNum++;}/*** 获取顶点v的所有相邻顶点* @param v* @return*/public Queue<Edge> adj(int v){return this.adj[v];}/*** 获取加权无向图中的所有边* @return*/public Queue<Edge> edges(){// 创建一个队列对象，存储所有的边Queue<Edge> allEdges = new Queue<>();// 遍历图中的每一个顶点，找到每个顶点的邻接表，邻接表中存储了该顶点关联的每一条边for(int v=0;v<vNum;v++){// 遍历顶点v的邻接表，找到每一条和v关联的边for (Edge e : adj(v)) {// 每条边的两个顶点，一大一小，判断大小再添加，可以避免重复if(e.other(v) < v){allEdges.enQueue(e);}}}return allEdges;}
}

18、最小生成树

之前学习的加权图，它的边关联了一个权重，那么可以根据这个权重解决最小成本问题，但如何才能找到最小成本对应的顶点和边呢？最小生成树相关算法可以解决。

18.1、定义及相关约定

  • 图的生成树 是它的一棵含有其 所有顶点 的 无环连通子图，一副加权无向图的最小生成树，是它的一棵权值(树中所有边的权重之和)最小的生成树

在这里插入图片描述

  • 只考虑连通图

    最小生成树的定义说明它只能存在于连通图中， 如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为 最小生成森林

在这里插入图片描述

  • 所有边的权重都各不相同

    如果不同的边权重可以相同，那么一副图的最小生成树就可能不唯一了，虽然算法可以处理这种情况，但为了好理解，约定所有边的权重都各不相同

18.2、最小生成树原理

1）树的性质

  • 用一条边连接树中的任意两个顶点都会产生 一个新的环

在这里插入图片描述

  • 从树中删除任意一条边，将会得到 两棵独立的树

在这里插入图片描述

2）切分定理

要从一副连通图中找出该图的最小生成树，需要通过切分定理完成

  • 切分

    将图的所有顶点按照某些规则分为两个 非空 且 没有交集 的集合

  • 横切边

    连接两个属于不同集合的顶点的边称之为横切边

例如：

将图中的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合，那么效果如下：

在这里插入图片描述

  • 切分定理

    在一副加权图中，给定任意的切分，它的 横切边中的权重最小者 必然属于图中的最小生成树

在这里插入图片描述

  • 注意

    一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边

在这里插入图片描述

3）贪心算法

贪心算法是计算图的最小生成树的基础算法，它的基本原理就是 切分定理

使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边

如果图有 V 个顶点，那么需要找到 V-1 条边，就可以表示该图的最小生成树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

计算图的最小生成树的算法有很多种，但这些算法都可以看做是贪心算法的一种特殊情况，这些算法的不同之处在于 保存切分 和 判定权重最小的横切边 的方式

4）Prim算法

Prim算法，它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中

  • Prim算法的切分规则

    把最小生成树中的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合

在这里插入图片描述

1、Prim算法API设计

在这里插入图片描述

2、Prim算法的实现原理

Prim算法始终将图中的顶点切分成两个集合，最小生成树顶点 和 非最小生成树顶点，通过不断的重复做某些操作，可以逐渐将非最小生成树中的顶点加入到最小生成树中，直到所有的顶点都加入到最小生成树中

在设计API的时候，使用最小索引优先队列存放树中顶点与非树中顶点的有效横切边，那么它是如何表示的
呢？

可以让最小索引优先队列的 索引值表示图的顶点，让最小索引优先队列中的 值 表示从其他某个顶点到当前顶点的 边权重

在这里插入图片描述

初始化状态，先默认0是最小生成树中的唯一顶点，其他的顶点都不在最小生成树中，此时横切边就是顶点0的邻接表中0-2，0-4，0-6，0-7这四条边，只需要将索引优先队列的2、4、6、7索引处分别存储这些边的权重值就可以表示了。

现在只需要从这四条横切边中找出权重最小的边，然后把对应的顶点加进来即可。所以找到0-7这条横切边的权重最小，因此把0-7这条边添加进来，此时0和7属于最小生成树的顶点，其他的不属于，现在顶点7的邻接表中的边也成为了横切边，这时需要做两个操作：

1、0-7这条边已经不是横切边了，需要让它失效：只需要调用最小索引优先队列的delMin()方法即可完成

2、2和4顶点各有两条连接指向最小生成树，需要只保留一条：4-7的权重小于0-4的权重，所以保留4-7，调用索引优先队列的change(4,0.37)即可，0-2的权重小于2-7的权重，所以保留0-2，不需要做额外操作

在这里插入图片描述

不断重复上面的动作，就可以把所有的顶点添加到最小生成树中

3、代码
package chapter18;import chapter03.Queue;
import chapter07.IndexMinPriorityQueue;
import chapter17.Edge;
import chapter17.EdgeWeightedGraph;/*** @author 土味儿* Date 2021/9/17* @version 1.0* 最小生成树prim算法*/
public class PrimMST {/*** 最小边* 索引代表顶点* 值表示当前顶点到最小生成树之间的最小边*/private Edge[] edgeTo;/*** 最小边的权重* 索引代表顶点* 值表示当前顶点到最小生成树之间的最小边的权重*/private double[] distTo;/*** 索引代表顶点* 如果当前顶点已经在树中，则值为true，否则为false*/private boolean[] marked;/*** 存放树中顶点与非树中顶点的有效横切边*/private IndexMinPriorityQueue<Double> pq;/*** 构造器* 根据加权无向图创建最小生成树* @param g*/public PrimMST(EdgeWeightedGraph g) {// 初始化edgeTothis.edgeTo = new Edge[g.getVNum()];// 初始化distTothis.distTo = new double[g.getVNum()];for (int i = 0; i < g.getVNum(); i++) {// 默认值：正无穷大this.distTo[i] = Double.POSITIVE_INFINITY;}// 初始化markedthis.marked = new boolean[g.getVNum()];// 初始化pqpq = new IndexMinPriorityQueue<Double>(g.getVNum());// 默认让顶点0进入到树中，但是树中只有一个顶点0，因此，顶点0没有和任何顶点相连，所以distTo对应位置处的值为0.0distTo[0] = 0.0;pq.insert(0,0.0);// 遍历索引最小优先队列，拿到最小横切边对应的顶点，把该顶点加入到最小树中while(!pq.isEmpty()){visit(g, pq.delMin());}}/*** 获取最小生成树的所有边* @return*/public Queue edges(){// 创建队列对象Queue<Edge> allEdges = new Queue<>();// 把edgeTo中非null的值加入队列for (int i = 0; i < edgeTo.length; i++) {if(edgeTo[i] != null){allEdges.enQueue(edgeTo[i]);}}return allEdges;}/*** 将顶点v添加到最小生成树中，并更新数据* @param g* @param v*/private void visit(EdgeWeightedGraph g,int v){// 把顶点v添加到最小生成树中marked[v] = true;// 更新数据for (Edge e : g.adj(v)) {// 获取边e的另外一个顶点w（当前顶点v）int w = e.other(v);// 判断另一个顶点是否在树中，如果在树中，不做处理；如果不在树中，更新数据if(marked[w]){// 继续下次循环；不是退出，不能用breakcontinue;}// 比较权重：判断边e的权重是否小于 w到最小树中已存在的最小边的权重if(e.getWeight() < distTo[w]){// 更新数据edgeTo[w] = e;distTo[w] = e.getWeight();if(pq.contains(w)){pq.changeItem(w, e.getWeight());}else{pq.insert(w, e.getWeight());}}}}
}
  • 测试
package chapter18;import chapter03.Queue;
import chapter17.Edge;
import chapter17.EdgeWeightedGraph;
import org.junit.Test;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;/*** @author 土味儿* Date 2021/9/17* @version 1.0* 测试prim最小生成树*/
public class PrimMSTTest {@Testpublic void test() throws IOException {// 准备一幅加权无向图BufferedReader br = new BufferedReader(new InputStreamReader(PrimMSTTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));// 顶点数量int total = Integer.parseInt(br.readLine());// 加权无向图EdgeWeightedGraph g = new EdgeWeightedGraph(total);// 边的数量int edges = Integer.parseInt(br.readLine());// 依次读取边for (int i = 0; i < edges; i++) {String line = br.readLine();String[] s = line.split(" ");int v = Integer.parseInt(s[0]);int w = Integer.parseInt(s[1]);double weight = Double.parseDouble(s[2]);// 创建加权无向边Edge edge = new Edge(v, w, weight);// 向图中加入边g.addEdge(edge);}// 创建prim最小生成树对象PrimMST primMST = new PrimMST(g);// 得到最小生成树Queue<Edge> allEdges = primMST.edges();// 输出for (Edge e : allEdges) {int x = e.either();int y = e.other(x);double w = e.getWeight();System.out.println(x + " - " + y + " : " + w);}}
}
  • min_create_tree_test.txt
8
16
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93
  • 运行结果
1 - 7 : 0.19
0 - 2 : 0.26
2 - 3 : 0.17
4 - 5 : 0.35
5 - 7 : 0.28
6 - 2 : 0.4
0 - 7 : 0.16

5）kruskal算法

  • kruskal算法 是计算一副加权无向图的最小生成树的另外一种算法，它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边 不会 与已经加入最小生成树的边构成 环，直到树中含有 V-1 条边为止

  • kruskal算法和prim算法的区别

    • Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边
    • kruskal算法构造最小生成树的时候，也是一条边一条边地构造，但它的 切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树；如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，kruskal算法每一次处理都会将两棵树合并一棵树，直到整个森林中只剩一棵树为止

在这里插入图片描述

1、kruskal算法API设计

在这里插入图片描述

2、kruskal算法的实现原理

在设计API的时候，使用了一个MinPriorityQueue pq存储图中所有的边，每次使用 pq.delMin() 取出权重最小的边，并得到该边关联的两个顶点v和w，通过uf.connect(v,w)判断v和w是否已经连通

如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在

如果不连通，则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst队列中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

3、代码
package chapter18;import chapter03.Queue;
import chapter07.MinPriorityQueue;
import chapter13.UF_Tree_Weighted;
import chapter17.Edge;
import chapter17.EdgeWeightedGraph;/*** @author 土味儿* Date 2021/9/17* @version 1.0* 最小生成树Kruskal算法*/
public class KruskalMST {/*** 保存最小生成树所有边*/private Queue<Edge> edges;/*** 优化并查集* 索引代表顶点* 使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一颗树中* 使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并*/private UF_Tree_Weighted uf;/*** 存储图中所有的边* 使用最小优先队列，对图中的边进行排序*/private MinPriorityQueue<Edge> pq;/*** 构造器* 根据一幅加权无向图，创建最小生成树** @param g*/public KruskalMST(EdgeWeightedGraph g) {// 初始化边队列this.edges = new Queue<Edge>();// 初始化并查集this.uf = new UF_Tree_Weighted(g.getVNum());// 初始化最小优先队列this.pq = new MinPriorityQueue<>(g.getENum());// 把图中所有的边存储到pq中for (Edge e : g.edges()) {this.pq.insert(e);}// 找到权重最小的边，并处理// 最小生成树中边的个数 等于 顶点个数减1int i=0;while (!pq.isEmpty() && edges.size() < g.getVNum() - 1) {// 找出最小边Edge e = pq.delMin();// 找出边的两个点int v = e.either();int w = e.other(v);// 判断这两个点是否在同一棵树中if (uf.connected(v, w)) {// 在同一棵树中，继续下次循环continue;}// 不在同一棵中，把两个点合并uf.union(v, w);// 把当前边加入最小树队列中this.edges.enQueue(e);}}/*** 获取最小生成树的所有边** @return*/public Queue<Edge> getEdges() {return this.edges;}
}

这篇关于【数据结构与算法】第十七、十八章：加权无向图、最小生成树（切分定理、贪心算法、Prim算法、kruskal算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/942795。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题：墙体两侧特征混淆误匹配，导致建图和定位偏差，表现为过门跳变、外月台走歪等 ·解决思路：预期的根治方案IGICP需要较长时间完成上线，先使用切分地图的工程化方案，即墙体两侧切分为不同地图，在某一侧只使用该侧地图进行定位 方案思路 切分原理：切分地图基于关键帧位置，而非点云。 理论基础：光照是直线的，一帧点云必定只能照射到墙的一侧，无法同时照到两侧实践考虑：关
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2