12. 图的进阶

12. 图的进阶

12.1 有向图

在实际生活中,很多应用相关的图都是有方向性的,最直观的就是网络,可以从A页面通过链接跳转到B页面,那么a和b连接的方向是a->b,但不能说是b->a,此时我们就需要使用有向图来解决这一类问题,它和我们之前学习的无向图,最大的区别就在于连接是具有方向的,在代码的处理上也会有很大的不同。

image-20230326103314638

12.1.1 有向图的定义及相关术语

定义:

有向图是一副具有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连着一对有序的顶点。

出度:

由某个顶点指出的边的个数称为该顶点的出度。

入度:

指向某个顶点的边的个数称为该顶点的入度。

有向路径:

由一系列顶点组成,对于其中的每个顶点都存在一条有向边,从它指向序列中的下一个顶点。

有向环:

一条至少含有一条边,且起点和终点相同的有向路径。

image-20230326104550401

一副有向图中两个顶点v和w可能存在以下四种关系:

  1. 没有边相连;

  2. 存在从v到w的边v—>w;

  3. 存在从w到v的边w—>v;

  4. 既存在w到v的边,也存在v到w的边,即双向连接

理解有向图是一件比较简单的,但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了。

image-20230326104718361

12.1.2 有向图API设计

类名Digraph
构造方法Digraph(int V):创建一个包含V个顶点但不包含边的有向图
成员方法1.public int V():获取图中顶点的数量
2.public int E():获取图中边的数量
3.public void addEdge(int v,int w):向有向图中添加一条边 v->w
4.public Queue adj(int v):获取由v指出的边所连接的所有顶点
5.private Digraph reverse():该图的反向图
成员变量1.private final int V: 记录顶点数量
2.private int E: 记录边数量
3.private Queue[] adj: 邻接表

在api中设计了一个反向图,其因为有向图的实现中,用adj方法获取出来的是由当前顶点v指向的其他顶点,如果能得到其反向图,就可以很容易得到指向v的其他顶点。

12.1.3 有向图实现

package com.ynu.Java版算法.U12_图的进阶.T1_有向图;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ybh
 * @date 2023.03.26 10:56
 */
public class Digraph {

    // 记录顶点的数量
    private int V;

    // 边的数量
    private int E;

    // 邻接表
    private Queue<Integer>[] adj;


    public Digraph(int V) {
        this.V = V;
        E = 0;
        // 邻接表的大小应该和顶点数量相同
        this.adj = new Queue[V];

        // 初始化邻接表的空队列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new LinkedList<>();
        }

    }


    // 获取顶点数量
    public int getV() {
        return V;
    }

    //获取边的数目
    public int E() {
        return E;
    }

    //向有向图中添加一条边 v->w
    public void addEdge(int v, int w) {
        //由于有向图中边是有向的,v->w 边,只需要让w出现在v的邻接表中,而不需要让v出现在w的邻接表中
        //无向图的话两个都要加
        adj[v].add(w);
        //边的数目自增1
        E++;
    }


    //获取由v指出的边所连接的所有顶点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }

    //该图的反向图
    private Digraph reverse() {
        //创建新的有向图对象
        Digraph r = new Digraph(V);
        //遍历0~V-1所有顶点,拿到每一个顶点v
        for (int v = 0; v < V; v++) {
        //得到原图中的v顶点对应的邻接表,原图中的边为 v->w,则反向图中边为w->v;
            for (Integer w : adj(v)) {
                r.addEdge(w, v);
            }
        }
        return r;
    }

}

12.2 拓扑排序

​ 在现实生活中,我们经常会同一时间接到很多任务去完成,但是这些任务的完成是有先后次序的。以我们学习java学科为例,我们需要学习很多知识,但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础,到jsp/servlet,到ssm,到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础,学习ssm框架前要掌握jsp/servlet之类才行。

image-20230326171609360

为了简化问题,我们使用整数为顶点编号的标准模型来表示这个案例:

image-20230326114225024

此时如果某个同学要学习这些课程,就需要指定出一个学习的方案,我们只需要对图中的顶点进行排序,让它转换为一个线性序列,就可以解决问题,这时就需要用到一种叫拓扑排序的算法。

拓扑排序:

给定一副有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素,此时就可以明确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图:

image-20230326114256979

能进行拓扑排序的必然是一个无环的图。

12.2.1 检测有向图中的环

如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了,我们就没有办法学习了,因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环:

image-20230326114346872

因此,如果我们要使用拓扑排序解决优先级问题,首先得保证图中没有环的存在。

12.2.1.2 检测有向环的API设计
类名DirectedCycle
构造方法DirectedCycle(Digraph G):创建一个检测环对象,检测图G中是否有环
成员方法1.private void dfs(Digraph G,int v):基于深度优先搜索,检测图G中是否有环
2.public boolean hasCycle():判断图中是否有环
成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
2.private boolean hasCycle: 记录图中是否有环
3.private boolean[] onStack:索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上
12.2.1.2 检测有向环实现

在API中添加了onStack[] 布尔数组,索引为图的顶点,当我们深度搜索时:

  1. 如果当前顶点正在搜索,则把对应的onStack数组中的值改为true,标识进栈
  2. 如果当前顶点搜索完毕,则把对应的onStack数组中的值改为false,标识出栈;
  3. 如果即将要搜索某个顶点,但该顶点已经在栈中,则图中有环;

image-20230326123505014

代码:

package com.ynu.Java版算法.U12_图的进阶.T1_有向图;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ybh
 * @date 2023.03.26 10:56
 */
public class Digraph {

    // 记录顶点的数量
    private int V;

    // 边的数量
    private int E;

    // 邻接表
    private Queue<Integer>[] adj;


    public Digraph(int V) {
        this.V = V;
        E = 0;
        // 邻接表的大小应该和顶点数量相同
        this.adj = new Queue[V];

        // 初始化邻接表的空队列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new LinkedList<>();
        }

    }


    // 获取顶点数量
    public int V() {
        return V;
    }

    //获取边的数目
    public int E() {
        return E;
    }

    //向有向图中添加一条边 v->w
    public void addEdge(int v, int w) {
        //由于有向图中边是有向的,v->w 边,只需要让w出现在v的邻接表中,而不需要让v出现在w的邻接表中
        //无向图的话两个都要加
        adj[v].add(w);
        //边的数目自增1
        E++;
    }


    //获取由v指出的边所连接的所有顶点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }

    //该图的反向图
    private Digraph reverse() {
        //创建新的有向图对象
        Digraph r = new Digraph(V);
        //遍历0~V-1所有顶点,拿到每一个顶点v
        for (int v = 0; v < V; v++) {
        //得到原图中的v顶点对应的邻接表,原图中的边为 v->w,则反向图中边为w->v;
            for (Integer w : adj(v)) {
                r.addEdge(w, v);
            }
        }
        return r;
    }

}




package com.ynu.Java版算法.U12_图的进阶.T2_拓扑排序;

import com.ynu.Java版算法.U12_图的进阶.T1_有向图.Digraph;

/**
 * @author ybh
 * @date 2023.03.26 13:41
 */
public class DirectedCycleTest {
    public static void main(String[] args) {

        // 创建有4个顶点的图
        Digraph digraph = new Digraph(4);
        digraph.addEdge(0,1);
        digraph.addEdge(1,2);
        digraph.addEdge(2,3);
        digraph.addEdge(3,0);

        DirectedCycle cycle = new DirectedCycle(digraph);

        System.out.println("图"+ (cycle.hasCycle()?"有环":"无环"));

    }
}

12.2.2 有向无环图基于深度优先的顶点排序

​ 如果要把图中的顶点生成线性序列其实是一件非常简单的事,之前我们学习并使用了多次深度优先搜索,我们会发现其实深度优先搜索有一个特点,那就是在一个连通子图上,每个顶点只会被搜索一次,如果我们能在深度优先搜索的基础上,添加一行代码,只需要将搜索的顶点放入到线性序列的数据结构中,我们就能完成这件事。

12.2.2.1 顶点排序API设计
类名DepthFirstOrder
构造方法DepthFirstOrder(Digraph G):创建一个顶点排序对象,生成顶点线性序列;
成员方法1.private void dfs(Digraph G,int v):基于深度优先搜索,生成顶点线性序列
2.public Stack reversePost():获取顶点线性序列
成员变量1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索
2.private Stack reversePost: 使用栈,存储顶点序列
12.2.2.2 顶点排序实现

在API的设计中,我们添加了一个栈reversePost用来存储顶点,当我们深度搜索图时,每搜索完毕一个顶点,把该顶点放入到reversePost中,这样就可以实现顶点排序。

image-20230326172323934

package com.ynu.Java版算法.U12_图的进阶.T2_拓扑排序.S2_深度优先顶点排序;

import com.ynu.Java版算法.U12_图的进阶.T1_有向图.Digraph;

import java.util.Queue;
import java.util.Stack;

/**
 * @author ybh
 * @date 2023.03.26 17:25
 */
public class DepthFirstOrder {

    //索引代表顶点,值表示当前顶点是否已经被搜索
    private boolean[] marked;

    //使用栈,存储顶点序列
    private Stack<Integer> reversePost;

    //创建一个检测环对象,检测图G中是否有环
    public DepthFirstOrder(Digraph digraph) {
        //创建一个和图的顶点数一样大小的marked数组
        this.marked = new boolean[digraph.V()];
        this.reversePost = new Stack<>();

        // 遍历搜索图的每个节点
        for (int i = 0; i < digraph.V(); i++) {
            if (!marked[i]){
                //如果当前顶点没有搜索过,则搜索
                dfs(digraph,i);
            }
        }

    }

    //基于深度优先搜索。
    private void dfs(Digraph digraph, int v) {

        //把当前顶点标记为已搜索
        marked[v] = true;

        //遍历v顶点的邻接表,得到每一个顶点w
        Queue<Integer> adj = digraph.adj(v);
        for (Integer w : adj) {
            //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
            if (!marked[w]){
                dfs(digraph,w);
            }
        }


        //当前顶点已经搜索完毕,让当前顶点入栈
        reversePost.push(v);
    }

    //获取顶点线性序列
    public Stack<Integer> reversePost(){
        return reversePost;
    }
}

12.2.3 拓扑排序实现

前面已经实现了环的检测以及顶点排序,那么拓扑排序就很简单了,基于一幅图,先检测有没有环,如果没有环,则调用顶点排序即可。

API设计:

类名TopoLogical
构造方法TopoLogical(Digraph G):构造拓扑排序对象
成员方法1.public boolean isCycle():判断图G是否有环
2.public Stack order():获取拓扑排序的所有顶点
成员变量1.private Stack order: 顶点的拓扑排序

代码:

package com.ynu.Java版算法.U12_图的进阶.T2_拓扑排序.S2_深度优先顶点排序;

import com.ynu.Java版算法.U12_图的进阶.T1_有向图.Digraph;

import java.util.Queue;
import java.util.Stack;

/**
 * @author ybh
 * @date 2023.03.26 17:25
 */
public class DepthFirstOrder {

    //索引代表顶点,值表示当前顶点是否已经被搜索
    private boolean[] marked;

    //使用栈,存储顶点序列
    private Stack<Integer> reversePost;

    //创建一个检测环对象,检测图G中是否有环
    public DepthFirstOrder(Digraph digraph) {
        //创建一个和图的顶点数一样大小的marked数组
        this.marked = new boolean[digraph.V()];
        this.reversePost = new Stack<>();

        // 遍历搜索图的每个节点
        for (int i = 0; i < digraph.V(); i++) {
            if (!marked[i]){
                //如果当前顶点没有搜索过,则搜索
                dfs(digraph,i);
            }
        }

    }

    //基于深度优先搜索。
    private void dfs(Digraph digraph, int v) {

        //把当前顶点标记为已搜索
        marked[v] = true;

        //遍历v顶点的邻接表,得到每一个顶点w
        Queue<Integer> adj = digraph.adj(v);
        for (Integer w : adj) {
            //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
            if (!marked[w]){
                dfs(digraph,w);
            }
        }


        //当前顶点已经搜索完毕,让当前顶点入栈
        reversePost.push(v);
    }

    //获取顶点线性序列
    public Stack<Integer> reversePost(){
        return reversePost;
    }
}

12.3 加权无向图

持续学习中

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/13597.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【jvm系列-09】垃圾回收底层原理和算法以及JProfiler的基本使用

JVM系列整体栏目 内容链接地址【一】初识虚拟机与java虚拟机https://blog.csdn.net/zhenghuishengq/article/details/129544460【二】jvm的类加载子系统以及jclasslib的基本使用https://blog.csdn.net/zhenghuishengq/article/details/129610963【三】运行时私有区域之虚拟机栈…

为什么许多人吐槽C++11,那些语法值得我们学习呢?

致前行的人&#xff1a; 人生像攀登一座山&#xff0c;而找寻出路&#xff0c;却是一种学习的过程&#xff0c;我们应当在这过程中&#xff0c;学习稳定冷静&#xff0c;学习如何从慌乱中找到生机。 目录 1.C11简介 2.统一的列表初始化 2.1 &#xff5b;&#xff5d;初始化 …

git 常用命令及遇到问题

自己没事&#xff0c;把git常用命令做个记录总结。方便自己和初学者查看&#xff0c;本文针对初学者&#xff0c;如果你已经是工作多年高手&#xff0c;请跳过。 git的几个区认识&#xff0c;分别为工作区&#xff0c;缓存区&#xff0c;版本库。 工作区&#xff1a;包含.git…

【Unity VR开发】结合VRTK4.0:添加碰撞忽略器

语录&#xff1a; 最远的旅行&#xff0c;是从自己的身体到自己的心&#xff0c;是从一个人的心到另一个人的心。坚强不是面对悲伤不流一滴泪&#xff0c;而是擦干眼泪后微笑面对以后的生活。 前言&#xff1a; 模块化提供了一种允许两个或者多个对象忽略彼此碰撞的方法&#x…

揭秘移动云大会展区前沿科技

2023年4月25日-26日 我们苏州金鸡湖国际会议中心见&#xff01; 1场重磅主论坛、10场分论坛、2600㎡展区 数字中国新未来 尽在2023移动云大会 2023移动云大会设有中国移动和合作伙伴两大展区&#xff0c;联合40余家优质合作伙伴&#xff0c;全方位展示移动云在自主能力、行…

vue yarn npm

2016年左右 &#xff0c;facebook针对npm包管理工具存在的性能问题进行了针对性开发并发布了yarn新的node包开发管理工具&#xff0c;具体对比&#xff0c;同学们自行网上搜索资料对比。 配置 1、先下载好NodeJS&#xff0c;然后输入如下命令安装yarn npm install -g yarn 2、…

如何微调Segment Anything Model

文章目录 什么是SAM&#xff1f;什么是模型微调&#xff1f;为什么要微调模型&#xff1f;如何微调 Segment Anything 模型背景与架构创建自定义数据集输入数据预处理训练设置循环训练保存检查点并从中启动模型 下游应用程序的微调 随着 Meta 上周发布的 Segment Anything Mode…

线程等待其他线程执行同步类CountDownLatch

文章目录 前言核心原理源码解析同步源码分析await源码分析countDown源码分析 实战演示1、创建演示代码2、创建测试用例3、测试结果演示 写在最后 前言 大家都知道多线程在我们实际编码过程中运用很多&#xff0c;很多情况我们需要靠多线程来提升系统性能。但是有些时候我们需要…

C语言开发环境搭建及调试

C简介 可移植 标准C C/C &#xff08;系统硬件操作的接口&#xff0c;windows&#xff0c;Linux不一样&#xff09; 跨平台 Java Python 下载 去官网选择Visual Studio 2019下载 安装过程中勾选使用C的桌面开发 安装好之后点击创建新项目——空项目 位置最好放在根目录下&…

【vue2】近期bug收集与整理02

⭐【前言】 在使用vue2构建页面时候&#xff0c;博主遇到的问题难点以及最终的解决方案。 &#x1f973;博主&#xff1a;初映CY的前说(前端领域) &#x1f918;本文核心&#xff1a;博主遇到的问题与解决思路 目录 ⭐数据枚举文件的使用⭐elementUI中分页组件使用的注意事项⭐…

OpenAI-ChatGPT最新官方接口《从0到1生产最佳实例》全网最详细中英文实用指南和教程,助你零基础快速轻松掌握全新技术(十一)(附源码)

Production Best Practices 生产最佳实例 前言Introduction 导言Setting up your organization 设置您的组织Managing billing limits 管理计费限额API keys API密钥Staging accounts 演示账户 Building your prototype 构建您的原型Additional tips 其它技巧 Techniques for i…

C++函数重载

目录 函数重载函数重载是怎样实现的 函数重载 函数重载&#xff1a;是函数的一种特殊情况&#xff0c;C允许在同一作用域中声明几个功能类似的同名函数&#xff0c;这些同名函数的形参列表(参数个数 或 类型 或 类型顺序)不同&#xff0c;常用来处理实现功能类似数据类型不同的…

找PPT模板就上这5个网站~

分享几个可以永久免费下载PPT模板、素材的网站&#xff0c;上万个模板随便下载&#xff0c;赶紧收藏起来~ 1、菜鸟图库 https://www.sucai999.com/search/ppt/0_0_0_1.html?vNTYxMjky 网站素材非常全面&#xff0c;主要以设计类素材为主&#xff0c;办公类素材也很多&#x…

Spring MVC 接收 json 和返回 json (14)

目录 总入口 测试case 源码分析 1. 针对RequestBody的参数解析 2. 针对 ResponseBody 的返回值处理 总入口 通过上一篇Spring MVC 参数解析&#xff08;13&#xff09;_chen_yao_kerr的博客-CSDN博客的说明&#xff0c;相信大家对Sping MVC的参数解析有了一定的了解&…

8. 优先队列

8. 优先队列 普通的队列是一种先进先出的数据结构&#xff0c;元素在队列尾追加&#xff0c;而从队列头删除。在某些情况下&#xff0c;我们可能需要找出队列中的最大值或者最小值&#xff0c;例如使用一个队列保存计算机的任务&#xff0c;一般情况下计算机的任务都是有优先级…

【有功-无功协调优化】基于改进多目标粒子群优化算法(小生境粒子群算法)的配电网有功-无功协调优化研究(Matlab代码实现)

&#x1f4a5; &#x1f4a5; &#x1f49e; &#x1f49e; 欢迎来到本博客 ❤️ ❤️ &#x1f4a5; &#x1f4a5; &#x1f3c6; 博主优势&#xff1a; &#x1f31e; &#x1f31e; &#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 …

中断嵌套实验

使用汇编语言&#xff0c;要求&#xff1a; 外部中断1可以嵌套外部中断0 没有中断时&#xff0c;8个LED发光二极管以0.1s的速度闪烁。 有外部中断0时&#xff0c;8个LED发光二极管以0.1s的速度流水点亮。&#xff08;中断子程序0&#xff09; 有外部中断1时&#xff0c;会打断外…

gdb调试常用指令及案例讲解

文章目录 前言一、常用指令二、案例说明1、测试源文件2、编译和调试 三、其他指令四、案例说明 前言 GDB是一个由GNU开源组织发布的、UNIX/LINUX 操作系统下的、基于命令行的、功能强大的程序调试工具。 GDB 支持断点、单步执行、打印变量、观察变量、查看寄存器、查看堆栈等调…

每天一道大厂SQL题【Day22】华泰证券真题实战(四)

每天一道大厂SQL题【Day22】华泰证券真题实战(四) 大家好&#xff0c;我是Maynor。相信大家和我一样&#xff0c;都有一个大厂梦&#xff0c;作为一名资深大数据选手&#xff0c;深知SQL重要性&#xff0c;接下来我准备用100天时间&#xff0c;基于大数据岗面试中的经典SQL题&…

2023软件测试工程师必备技能?要卷,谁还不会了......

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 软件测试岗位是怎…