导航：首页 > 开发技术 >

怎么理解java图的对象化描述

发表于：2024-11-28 作者：千家信息网编辑

千家信息网最后更新 2024年11月28日，这篇文章主要讲解了"怎么理解java图的对象化描述"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"怎么理解java图的对象化描述"吧！一、前言对于图来说

千家信息网最后更新 2024年11月28日怎么理解java图的对象化描述

这篇文章主要讲解了"怎么理解java图的对象化描述"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"怎么理解java图的对象化描述"吧！

一、前言

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

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

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

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

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

二、什么是图

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

对于图来说，分为有向图和无向图，如下图所示：

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

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

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

当然，还有一种图的形式，叫做：带权图（主要用来做一些路程、路费的计算），如下图所示：

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

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

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

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

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

1、邻接矩阵

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

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

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

带权图的邻接矩阵

2、邻接表

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

无向图的邻接表：HashMap>

3、图对象化表示

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

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

对于图来说，我们想一想主要包括什么？

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

点的描述：

点的值：int value

邻接的点：ArrayList nexts

邻接的边：ArrayList edges

入度：int in

出度：int out

public class Node {    public int value;    public int in;    public int out;    public ArrayList nexts;    public ArrayList 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 nodes多个边的集合：Set edges

public class Graph {    public HashMap nodes;    public Set 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 edgeList = graph.nodes.get(2).edges;        for (Edge edge : edgeList) {            System.out.println("从" + edge.from.value + "---->" + edge.to.value + "权值为" + edge.weight);        }    }

最终结果：