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

本文主要讲解“如何理解java图的对象描述”。本文的解释简单明了，易学易懂。现在，请跟随边肖的思路，一起学习学习《如何理解java图的对象描述》！

00-1010对于画面，我一直是懵懂的。

懂图的意思，但不懂图的具体实现。

对于目前各大厂商的面试问题，无非以下几点：

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

事实上，这些算法听起来并不太难理解，但是当我们实际编写代码时，我们会发现一件事。愚蠢的图的边和点太难描述，导致写的人和写的人都消失了，我们绕不开他们。

图

一、前言

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

对于图，有向图和无向图，如下图所示：

我们可以看到，有向图表示只有一个顶点可以到达另一个顶点，而无向图表示两个顶点可以互相到达。

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

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

当然，还有另外一种图形形式，叫做加权图(主要用来计算一些距离和通行费)，如下图所示：

00-1010我们刷题的时候，题目给出的例子往往是这样的：743。网络延迟时间。

标题会给我们一个二维矩阵。一行矩阵有三个数字：起点、终点和权重。

如何表达这个二维矩阵，成了我们在画图题中要做的一件难事。

在本文中，我们将直接使用特殊的表示来解决这个问题。我们将从最基本的邻接矩阵和邻接表表示开始。

二、什么是图

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

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

有向图的邻接矩阵：行之和为度，列之和为度。

加权图的邻接矩阵

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

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

无向图邻接表：hashmap整数，ArrayList整数

1、邻接矩阵

让我们想一想，以上两种方法是图的表示图像吗？

虽然有些题目用矩阵表示的时候做起来很舒服，但是还是好好想想吧。当我们找到最小生成树时，当我们使用边的连接来解锁点时，我们将使用矩阵。

感觉不是很抽象很难理解，如所示，我们需要定制一个图的表示方法来增强我们对图的理解。

对于图表，我们来思考一下它主要包括哪些内容。

图是由点和边组成的结构，也就是说，如果我们想画一个图，我们必须有点和边。

重点描述：

点的值：整数值

相邻点：数组列表节点下一个

相邻边：数组列表边

度：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图的对象化描述这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！