java图搜索算法之图的对象化描述示例详解

目录
  • 一、前言
  • 二、什么是图
  • 三、怎么存储一个图的结构
    • 1、邻接矩阵
    • 2、邻接表
    • 3、图对象化表示
  • 四、图的作用

你好,我是小黄,一名独角兽企业的Java开发工程师。
校招收获数十个offer,年薪均20W~40W。
感谢茫茫人海中我们能够相遇,
俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习,
希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想。

一、前言

对于图来说,我一直以来都似懂非懂

懂的是图的含义,不懂的是图具体的实现

对于当前各大厂面试的图题,不外乎以下几点:

深度优先搜索、广度优先搜索:DFS、BFS最小生成树:Kruskal、Prim最短路径:Dijkstra、Dijkstra加强堆版拓扑排序:TopologicalSort

这几个算法其实听起来不太难懂,但真正写代码的时候会发现一个事情,傻逼图的边和点太难描述,导致我们写着写着人就没了,绕进去出不来了

本篇系列文章,将从对象的角度来描述一个图的产生,并用最简单的思路去介绍上述所有算法,让我们走进本篇文章吧。

二、什么是图

图是我们现实生活中连接关系的抽象,例如朋友圈、微博的关注关系。

简单抽象如下图所示:

对于图来说,分为有向图和无向图,如下图所示:

我们可以看出来,有向图代表只能从一个顶点到达另一个顶点,而无向图代表两个顶点之间可以相互到达。

图1中,V4到达V1,而V1无法到达V4

图2中,V4到达V1,V1也可以到达V4

当然,还有一种图的形式,叫做:带权图(主要用来做一些路程、路费的计算),如下图所示:

三、怎么存储一个图的结构

我们在刷题的时候,题目给我们的样例经常是这种的:743. 网络延迟时间

题目会给我们一个二维的矩阵,一行矩阵有三个数字,分别是:起始点、终止点、权重

如何将这个二维的矩阵表示出来,成为了我们在做图题目中比较困难的一件事

本文将直接使用一种特殊的表示形式来解决这个难题,我们先从最基本的 邻接矩阵 和 邻接表 表示开始

1、邻接矩阵

邻接矩阵是表示图中顶点之间相邻关系的矩阵。

对于无向图的邻接矩阵:对称矩阵:int[][]

有向图的邻接矩阵:各行之和是出度,各列之和是入度

带权图的邻接矩阵

2、邻接表

邻接表是一种链式存储结构,类似于链表数组。

无向图的邻接表:HashMap<Integer, ArrayList<Integer>>

3、图对象化表示

我们思考,上述两个方法对于图的表示形象嘛?

虽然有的题目在用矩阵表示的时候,做起来很舒服,但我们想一想,当我们求最小生成树时,利用边的连接解锁点时,用矩阵会
不会感觉很抽象难懂,所示,我们要自定义一个图的表示方法,来增强我们对图的理解

对于图来说,我们想一想主要包括什么?

图是由点和边组成的一个结构,也就是我们想要勾画一个图,必须有:点、边

点的描述:

点的值:int value

邻接的点:ArrayList<Node> nexts

邻接的边:ArrayList<Edge> edges

入度:int in

出度:int out

public class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

边的描述:

来自哪里:Node from去往哪里:Node to边的权重:int weight

public class Edge {
    Node from;
    Node to;
    int weight;

    public Edge(Node from, Node to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

图的描述:

多个点的集合:HashMap<Integer, Node> nodes多个边的集合:Set<Edge> edges

public class Graph {
    public HashMap<Integer, Node> nodes;
    public Set<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

这里可能有疑问了,你这样写虽然形象,但是怎么进行转化呢?

别急,下面我们就进行转化。

public static Graph createGraph(int[][] matrix) {
        // 初始化一个图
        Graph graph = new Graph();

        for (int[] arr : matrix) {
            // 来的点
            int from = arr[0];
            // 去的点
            int to = arr[1];
            // 权重
            int value = arr[2];

            // 生成相对应的点
            Node fromNode = new Node(from);
            Node toNode = new Node(to);

            // 查看当前有没有这个点的信息
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, fromNode);
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, toNode);
            }

            // 生成一个边(这里的边是有向边)
            Edge edge = new Edge(fromNode, toNode, value);

            // 点里面加入边
            graph.nodes.get(from).edges.add(edge);

            //  点里面加入下一个点
            graph.nodes.get(from).nexts.add(toNode);

            // 点里面加入入度和出度
            graph.nodes.get(from).out++;
            graph.nodes.get(to).in++;

            // 图里面加入边
            graph.edges.add(edge);

        }
        return graph;
    }

当我们转化完的时候,进行测试:

public static void main(String[] args) {
        int[][] arr = new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        Graph graph = createGraph(arr);
        // 从2开始的边有哪些
        List<Edge> edgeList = graph.nodes.get(2).edges;
        for (Edge edge : edgeList) {
            System.out.println("从" + edge.from.value + "---->" + edge.to.value + "权值为" + edge.weight);
        }
    }

最终结果:

从2---->1权值为1
从2---->3权值为1

以后我们在做题的时候,都可以保存此转化代码,直接进行调用即可

简单形象的描绘了我们的图

四、图的作用

图经常用在以下地方:

  • 深度优先搜索、广度优先搜索:DFS、BFS
  • 最小生成树:Kruskal、Prim
  • 最短路径:Dijkstra、Dijkstra加强堆版
  • 拓扑排序:TopologicalSort

之后的章节会慢慢的讲解以上所有的应用

以上就是java算法图的对象化描述示例详解的详细内容,更多关于java图的对象化描述算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java经典排序算法之归并排序详解

    一.归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直

  • Java编程实现深度优先遍历与连通分量代码示例

    深度优先遍历 深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达. 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点. 当回退到的路口已没有可走的通道时继续回退. 而连通分量,看概念:无向图G的极大连通子图称为G的连通分量( Connected Component).任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量. 下面看看具体实例: package com.dataStructure.gra

  • 深入介绍Java对象初始化

    前言 在Java中,一个对象在可以被使用之前必须要被正确地初始化,这一点是Java规范规定的. 自动初始化(默认值) 一个类的所有基本数据成员都会得到初始化,运行下面的例子可以查看这些默认值: class Default{ boolean t; char c; byte b; short s; int i; long l; float f; double d; public void show() { System.out.println("基本类型 初始化值\n"+ "bo

  • Java实现图片对比功能

    之前用按键精灵写过一些游戏辅助,里面有个函数叫FindPic,就上在屏幕范围查找给定的一张图片,返回查找到的坐标位置. 现在,Java来实现这个函数类似的功能. 算法描述: 屏幕截图,得到图A,(查找的目标图片为图B): 遍历图A的像素点,根据图B的尺寸,得到图B四个角映射到图A上的四个点: 得到的四个点与图B的四个角像素点的值比较.如果四个点一样,执行步骤4:否则,回到步骤2继续: 进一步对比,将映射范围内的全部点与图B全部的点比较.如果全部一样,则说明图片已找到:否则,回到步骤2继续: 这里

  • java图搜索算法之图的对象化描述示例详解

    目录 一.前言 二.什么是图 三.怎么存储一个图的结构 1.邻接矩阵 2.邻接表 3.图对象化表示 四.图的作用 你好,我是小黄,一名独角兽企业的Java开发工程师. 校招收获数十个offer,年薪均20W~40W. 感谢茫茫人海中我们能够相遇, 俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习, 希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想. 一.前言 对于图来说,我一直以来都似懂非懂 懂的是图的含义,不懂的是图具体的实现 对于当前各大厂面试的图题,不外乎以下几

  • Go Java算法之外观数列实现方法示例详解

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Go Java算法之Excel表列名称示例详解

    目录 Excel表列名称 方法一:数学(Java) 方法一:数学(Go) Excel表列名称 给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称. 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 示例 1: 输入:columnNumber = 1 输出:"A" 示例 2: 输入:columnNumber = 28 输出:"AB"

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • java中常见的6种线程池示例详解

    之前我们介绍了线程池的四种拒绝策略,了解了线程池参数的含义,那么今天我们来聊聊Java 中常见的几种线程池,以及在jdk7 加入的 ForkJoin 新型线程池 首先我们列出Java 中的六种线程池如下 线程池名称 描述 FixedThreadPool 核心线程数与最大线程数相同 SingleThreadExecutor 一个线程的线程池 CachedThreadPool 核心线程为0,最大线程数为Integer. MAX_VALUE ScheduledThreadPool 指定核心线程数的定时

  • java面向对象设计原则之接口隔离原则示例详解

    目录 概念 实现 拓展 概念 小接口原则,即每个接口中不存在子类用不到却必须实现的方法,如果不然,就要将接口拆分.如下图所示定义了一个接口,包含了5个方法,实现类A用到了3个方法.实现类B用到了3个方法,类图如下: 类A没有方法4.方法5,却要实现它:类B没有方法2.方法3,但还是要实现这两个方法,不符合接口隔离原则.改造为将其拆分为三个接口,实现方式改为下图所示,符合接口隔离原则: 实现 面向对象机制中一个类可以实现多个接口,通过多重继承分离,通过接口多继承(实现)来实现客户的需求,代码更加清

  • java编程创建型设计模式工厂方法模式示例详解

    目录 1.什么是工厂方法模式? 2.案例实现 3.JDK中的工厂方法模式 1.什么是工厂方法模式? 工厂方法模式设计方案:  将披萨项目的实例化功能抽象成抽象方法,在不同的口味点餐子类中具体实现. 工厂方法模式:  定义了一个创建对象的抽象方法,由子类决定要实例化的类.工厂方法模式将对象的实例化推迟到子类. 何时使用?  不同条件下创建不用实例时.方法是让子类实现工厂接口. 2.案例实现 假如说,我们现在有这样一个需求:客户在点披萨时,可以点不同口味的披萨,比如北京的奶酪pizza.北京的胡椒p

  • Java实现超简单抖音去水印的示例详解

    目录 一.前言 二.原理与步骤 三.代码实现 四.总结 一.前言 抖音去水印方法很简单,以前一直没有去研究,以为搞个去水印还要用到算法去除,直到动手的时候才发现这么简单,不用编程基础都能做. 二.原理与步骤 其实抖音它是有一个隐藏无水印地址的,只要我们找到那个地址就可以了 1.我们在抖音找一个想要去水印的视频链接 注意:这里一定要是https开头的,不是口令 打开浏览器访问: 访问之后会重定向到这个地址,后面有一串数字,这个就是视频的id,他是根据这个唯一id来找到视频播放的 按F12查看网络请

  • java zxing合成复杂二维码图片示例详解

    目录 说明: 整体思路: 图片合成四部曲 踩过的坑 说明: 最近接到需要将二维码合成复杂图片的需求,要求给二维码上下或者左侧添加相关文字描述,技术没有难点,整理本文主要记录思路和踩过的坑. 整体思路: 引入zxing成熟的二维码生成接口,生成标准二维码文件,通过java图形图像处理API为二维码添加相关文字描述,根据需要,可以为合成后的图片添加相关背景.示例如下图所示: 1.先拿点位图来说,生成二维码图片核心代码如下 /** * 定义二维码的参数 */ HashMap<EncodeHintTyp

  • java中Servlet监听器的工作原理及示例详解

    监听器就是一个实现特定接口的普通java程序,这个程序专门用于监听另一个java对象的方法调用或属性改变,当被监听对象发生上述事件后,监听器某个方法将立即被执行. 监听器原理 监听原理 1.存在事件源 2.提供监听器 3.为事件源注册监听器 4.操作事件源,产生事件对象,将事件对象传递给监听器,并且执行监听器相应监听方法 监听器典型案例:监听window窗口的事件监听器 例如:swing开发首先制造Frame**窗体**,窗体本身也是一个显示空间,对窗体提供监听器,监听窗体方法调用或者属性改变:

随机推荐