Java中的图形：用代码表示图形

╰+哭是因爲堅強的太久メ 2023-10-04 08:53 48阅读 0赞

### **Java中的图形：用代码表示图形** ###

*通过奥利维拉·波波维奇（OliveraPopović） • [0评论][0]*

#### **介绍** ####

图形是存储某些类型的数据的便捷方法。该概念是从数学移植而来的，适合于计算机科学的需求。

由于许多事物可以用图形表示，因此图形遍历已成为一项常见的任务，尤其是在数据科学和机器学习中。图遍历是指通过连接边访问图中的节点（又称顶点）的过程。这通常用于在图形中查找特定节点，或用于绘制图形。

在本系列中，我们将研究在计算机科学中如何使用和表示图形，以及一些流行的遍历算法：

*  [Java中的图][Java]
    
     *  **用代码表示图**
     *  [深度优先搜索（DFS）][DFS]
     *  [广度优先搜索（BFS）][BFS]
     *  [Dijkstra的算法][Dijkstra]

#### **用代码表示图** ####

现在我们已经了解了什么是图形以及何时使用它们，我们应该知道如何在代码中实现它们。

解决此问题的主要两种方法是*邻接矩阵*和*邻接表*。

**邻接矩阵**

让我们开始假设我们有`n`节点并且它们被方便地命名`0,1,...n-1`，并且它们包含与它们具有相同名称的值。当然，这种情况很少发生，但是它使解释邻接矩阵更加容易。

我们的节点/顶点是对象（最有可能是对象）的情况非常复杂，并且需要很多维护方法，这些维护方法会使邻接矩阵比大多数情况下麻烦，因此，我们仅提供执行“简单”案例。

假设我们有以下图形：

![1a3f99a6d351a43d1dc87cf54fada573.png][]

在此图中，有5个节点-（0,1,2,3,4），其边缘为\{1,2\}，\{1,3\}，\{2,4\}，\{3,0\}。根据定义，当我们来看一个未加权无向图-的位置`(i,j)`在我们的邻接矩阵是1，如果节点之间存在的边缘`i`和`j`，否则其为0。在无向图的邻接矩阵是对称的情况下。

上一个示例的邻接矩阵如下所示：

![d5dc982acd40d4aa0ab8802dedf800c9.png][]

我们也可以颠倒该过程，从给定的邻接矩阵绘制一个图。

我们将给出一个反向过程的示例，但带有加权图的邻接矩阵。在这种情况下的位置`(i,j)`在我们的矩阵等于节点之间的边的权重`i`和`j`如果存在的话，否则它等于无穷大。

**注意**：使用无穷大作为权重被认为是表明边缘不存在的“安全”方法。但是，例如，如果我们知道我们只有正权重，则可以改用-1或任何合适的值来决定。

让我们从以下邻接矩阵构造一个加权图：

![2acfdacb98feced90e1686151ad1e81c.png][]

![fc5699383b27c012e4de65b883ceff33.png][]

作为最后一个示例，我们将显示如何使用邻接矩阵表示有向加权图：

![bf68cea4bae22943ea7e7d5203926f4a.png][]

![44a611913ec1a18f712a2310e7924e10.png][]

注意，有向图的邻接矩阵**是**如何不对称的，例如，我们的值是（0,3）而不是（3,0）。同样也没有理由为什么一个节点不能成为边缘的起点和终点，而我们可以拥有完全未连接的节点。

**实施邻接矩阵**

现在我们已经了解了邻接矩阵在纸上的工作方式，我们需要考虑它们的实现。如果我们的“节点”确实只是简单的整数值`0,1,...n-1`，则实现将非常简单。

但是，由于通常不是这种情况，因此我们需要弄清楚当节点是对象时，如何利用矩阵索引作为节点的便利性。

在我们的实现中，我们将使我们的课程尽可能多才多艺。这反映在更多的方法和一些边缘情况中。

我们还将提供有向图和无向图以及加权/未加权图之间的选择。

public class Graph {
    
        private int numOfNodes;
        private boolean directed;
        private boolean weighted;
        private float[][] matrix;
    
        /*
         This will allow us to safely add weighted graphs in our class since
         we will be able to check whether an edge exists without relying
         on specific special values (like 0)
        */
        private boolean[][] isSetMatrix;
    
        // ...
    }

然后，我们将有一个简单的构造函数：

public Graph(int numOfNodes, boolean directed, boolean weighted) {
    
        this.directed = directed;
        this.weighted = weighted;
        this.numOfNodes = numOfNodes;
    
        // Simply initializes our adjacency matrix to the appropriate size
        matrix = new float[numOfNodes][numOfNodes];
        isSetMatrix = new boolean[numOfNodes][numOfNodes];
    }

现在，让我们编写一个允许添加边的方法。我们要确保在图形被加权且未提供权重的情况下，将边值设置为0，如果未加权则仅添加1：

/*
     Since matrices for directed graphs are symmetrical, we have to add
     [destination][source] at the same time as [source][destination]
    */
    public void addEdge(int source, int destination) {
    
        int valueToAdd = 1;
    
        if (weighted) {
            valueToAdd = 0;
        }
    
        matrix[source][destination] = valueToAdd;
        isSetMatrix[source][destination] = true;
    
        if (!directed) {
            matrix[destination][source] = valueToAdd;
            isSetMatrix[destination][source] = true;
        }
    }

如果未对图形进行加权并提供了权重，则我们只需忽略该`[source,destination]`值，并将其值设置为1，就表示确实存在边：

public void addEdge(int source, int destination, float weight) {
    
        float valueToAdd = weight;
    
        if (!weighted) {
            valueToAdd = 1;
        }
    
        matrix[source][destination] = valueToAdd;
        isSetMatrix[source][destination] = true;
    
        if (!directed) {
            matrix[destination][source] = valueToAdd;
            isSetMatrix[destination][source] = true;
        }
    }

在这一点上，让我们添加一个方法，使我们可以轻松打印出邻接矩阵：

public void printMatrix() {
        for (int i = 0; i < numOfNodes; i++) {
            for (int j = 0; j < numOfNodes; j++) {
                // We only want to print the values of those positions that have been marked as set
                if (isSetMatrix[i][j])
                    System.out.format("%8s", String.valueOf(matrix[i][j]));
                else System.out.format("%8s", "/  ");
            }
            System.out.println();
        }
    }

之后，一种方便的方法以一种更易理解的方式打印出边缘：

/*
     We look at each row, one by one.
     When we're at row i, every column j that has a set value represents that an edge exists from
     i to j, so we print it
    */
    public void printEdges() {
        for (int i = 0; i < numOfNodes; i++) {
            System.out.print("Node " + i + " is connected to: ");
            for (int j = 0; j < numOfNodes; j++) {
                if (isSetMatrix[i][j]) {
                    System.out.print(j + " ");
                }
            }
            System.out.println();
        }
    }

最后，让我们编写两个辅助方法，这些方法将在以后使用：

public boolean hasEdge(int source, int destination) {
        return isSetMatrix[source][destination];
    }
    
    public Float getEdgeValue(int source, int destination) {
        if (!weighted || !isSetMatrix[source][destination])
            return null;
        return matrix[source][destination];
    }

为了展示邻接矩阵是如何工作的，让我们使用我们的类来制作一个图，用关系填充它，并打印它们：

public class GraphShow {
        public static void main(String[] args) {
    
            // Graph(numOfNodes, directed, weighted)
            Graph graph = new Graph(5, false, true);
    
            graph.addEdge(0, 2, 19);
            graph.addEdge(0, 3, -2);
            graph.addEdge(1, 2, 3);
            graph.addEdge(1, 3); // The default weight is 0 if weighted == true
            graph.addEdge(1, 4);
            graph.addEdge(2, 3);
            graph.addEdge(3, 4);
    
            graph.printMatrix();
    
            System.out.println();
            System.out.println();
    
            graph.printEdges();
    
            System.out.println();
            System.out.println("Does an edge from 1 to 0 exist?");
            if (graph.hasEdge(0,1)) {
                System.out.println("Yes");
            }
            else System.out.println("No");
        }
    }

这给了我们输出：

/       /      19.0    -2.0     /
         /       /       3.0     0.0     0.0
        19.0     3.0     /       0.0     /
        -2.0     0.0     0.0     /       0.0
         /       0.0     /       0.0     /
    
    
    Node 0 is connected to: 2 3
    Node 1 is connected to: 2 3 4
    Node 2 is connected to: 0 1 3
    Node 3 is connected to: 0 1 2 4
    Node 4 is connected to: 1 3
    
    Does an edge from 1 to 0 exist?
    No
    null

如果我们基于此矩阵构造图，则其外观如下所示：

![0128cc3ad3ba0c659c8e151362e8440f.png][]

**邻接表**

邻接表的实现要直观得多，并且比邻接表的使用频率更高。

顾名思义，我们使用列表来表示节点具有边缘的所有节点。通常，这是通过`HashMap`s和`LinkedList`s实现的。

![1a3f99a6d351a43d1dc87cf54fada573.png][]

邻接表倾向于有向图，因为这是最直接的地方，无向图只需要多一点维护。

在此示例中，我们可以看到：

Node 0 is connected with node 3
    Node 1 is connected with nodes 3, 2
    Node 2 is connected with nodes 1, 4
    Node 3 is connected with nodes 1, 0
    Node 4 is connected with node 2

显然，对于节点0，我们将创建一个`LinkedList`包含节点3的节点。对于节点1，我们将创建一个`LinkedList`包含节点3和2的节点，依此类推。

对于加权图，如下图所示，我们需要数组列表而不是节点列表。数组将包含位于边缘另一端的节点作为第一个参数，并将关联的权重作为第二个参数。

![fc5699383b27c012e4de65b883ceff33.png][]

0: [1,-50] -> [3,3]
    1: [0,-50]
    2: [3, 10]
    3: [0,3] -> [2,10] -> 4,7
    4: [3,7]

![bf68cea4bae22943ea7e7d5203926f4a.png][]

0: [2,10]
    1: null
    2: [2,5] -> [3,5] -> [4,3]
    3: [0,-2]
    4: [3,5]

邻接列表的一大优点是，与邻接矩阵相比，处理对象要容易得多。

我们将以对象作为节点而不是索引来实现邻接表。在解释邻接表时，这既受青睐，*又*对了解更为有用，因为您可能会在项目中使用对象。

**实施邻接表**

乍一看，该代码可能看起来很复杂，但是当您仔细观察时，它很简单。首先，让我们从一个简单的`Node`类开始：

public class Node {
        int n;
        String name;
    
        Node(int n, String name){
            this.n = n;
            this.name = name;
        }
    }

现在，让我们定义一个`Graph`：

public class Graph {
    
    // Each node maps to a list of all his neighbors
    private HashMap<Node, LinkedList<Node>> adjacencyMap;
    private boolean directed;
    
    public Graph(boolean directed) {
        this.directed = directed;
        adjacencyMap = new HashMap<>();
    }

现在，让我们添加方法`addEdge()`。尽管这一次我们将使用两种方法，辅助方法和实际方法。

在辅助方法中，我们还将检查可能的重复边缘。在`A`和之间添加边之前`B`，我们*先将其删除，*然后再添加。如果存在（我们要添加重复边），则将其删除，然后再次添加后，只有一个。

不过，如果它不存在，那么删除不存在的边将导致，`NullPointerException`因此我们引入了该列表的临时副本：

public void addEdgeHelper(Node a, Node b) {
        LinkedList<Node> tmp = adjacencyMap.get(a);
    
        if (tmp != null) {
            tmp.remove(b);
        }
        else tmp = new LinkedList<>();
        tmp.add(b);
        adjacencyMap.put(a,tmp);
    }
    
    public void addEdge(Node source, Node destination) {
    
        // We make sure that every used node shows up in our .keySet()
        if (!adjacencyMap.keySet().contains(source))
            adjacencyMap.put(source, null);
    
        if (!adjacencyMap.keySet().contains(destination))
            adjacencyMap.put(destination, null);
    
        addEdgeHelper(source, destination);
    
        // If a graph is undirected, we want to add an edge from destination to source as well
        if (!directed) {
            addEdgeHelper(destination, source);
        }
    }

最后，我们将使用`printEdges()`和`hasEdge()`帮助器方法，它们非常简单：

public void printEdges() {
            for (Node node : adjacencyMap.keySet()) {
                System.out.print("The " + node.name + " has an edge towards: ");
                if (adjacencyMap.get(node) != null) {
                    for (Node neighbor : adjacencyMap.get(node)) {
                        System.out.print(neighbor.name + " ");
                    }
                    System.out.println();
                }
                else {
                    System.out.println("none");
                }
            }
        }
    
        public boolean hasEdge(Node source, Node destination) {
            return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null && adjacencyMap.get(source).contains(destination);
        }

为了展示邻接表是如何工作的，让我们实例化几个节点并用它们填充图：

public class GraphShow {
        public static void main(String[] args) {
    
            Graph graph = new Graph(true);
            Node a = new Node(0, "A");
            Node b = new Node(1, "B");
            Node c = new Node(2, "C");
            Node d = new Node(3, "D");
            Node e = new Node(4, "E");
    
            graph.addEdge(a,b);
            graph.addEdge(b,c);
            graph.addEdge(b,d);
            graph.addEdge(c,e);
            graph.addEdge(b,a);
    
            graph.printEdges();
    
            System.out.println(graph.hasEdge(a,b));
            System.out.println(graph.hasEdge(d,a));
        }
    }

我们得到输出：

The A has an edge towards: B
    The B has an edge towards: C D A
    The C has an edge towards: E
    true
    false

**注意：**当然，这在很大程度上取决于Java如何对待内存中的对象。`a`在`main`将其添加到图形中之后，我们必须确保对其中的节点的进一步更改*将*反映在图形中！有时这是我们的目标，但有时并非如此。无论哪种方式，我们都应该注意，在这种情况下，`a`图中的`a`节点与中的节点相同`main`。

当然，我们可以以不同的方式实现这一目标。另一种流行的方法是将传出边列表添加到`Node`对象本身，并`Graph`适当地更改类：

public class Node {
        int n;
        String name;
        LinkedList<Node> adjacentNodes;
    
        Node(int n, String name) {
            this.n = n;
            this.name = name;
            adjacentNodes = new LinkedList<>();
        }
    
        public void addEdge(Node node) {
            if (!adjacentNodes.contains(node))
                adjacentNodes.add(node);
        }
    }

两种方法都以它们自己的方式遵循了面向对象封装概念的精神，所以两种方法都很好。

**邻接矩阵与邻接列表**

邻接矩阵的查找时间比邻接列表要快得多。例如，如果我们要检查节点是否`0`有一条通向节点的边，`4`我们可以只检查索引处的矩阵，`[0,4]`这样可以给我们恒定的执行时间。

另一方面，我们可能需要检查`0`其邻接列表中的邻居的整个列表，以发现是否存在通向node的边`4`，这给了我们线性**（O（n））**查找时间。

在邻接矩阵增加边也快得多-简单地改变位置值`[i,j]`从节点添加一个边缘`i`到节点`j`，而与列表（如果我们没有进入指针最后一个元素）也需要**为O（n ）**时间，尤其是当我们需要检查列表中是否已存在该边缘时。

就空间而言，由于非常简单的原因，邻接表效率更高。大多数现实生活中的图就是我们所说的*稀疏图*，这意味着边的数量比可能的最大边数量少得多。

为什么这很重要？好吧，在邻接矩阵中，我们总是有一个*n* x *n*大小的矩阵（其中*n*是节点数），而不管我们是只有几个边还是几乎是最大数（每个节点相互连接）。

实际上，这占用了很多不必要的空间，因为正如我们所说，大多数现实生活中的图都是稀疏的，并且我们为这些边中的大多数分配了空间，这些空间是不存在的。另一方面，邻接列表仅跟踪现有边缘。

更具体地说，如果我们有一个具有*N个*节点和*E个*边的图，则这两种方法的空间复杂度将是：

![68759dc86728e1aaaba2c4033f48909a.png][]

**我应该选择实施哪一个？**

简短答案-邻接表。当使用对象时，它们更加简单明了，并且大多数时候，我们不关心与代码维护和可读性相比，邻接矩阵提供的查询时间稍长一些。

但是，如果我们要处理高度*密集的图*（与*sparse*相对），则有必要投资必要的内存以通过邻接矩阵实现我们的图。

因此，例如，如果您最有可能要使用的操作是：

*  检查边是否为图的一部分：**邻接矩阵**，因为检查边是否为图的一部分需要**O（1）**时间，而在邻接表中则需要**O（lengthOfList）**时间
 *  从图中添加或删除边：**邻接矩阵**，与前面的情况相同
 *  遍历图形：**邻接表**，需要**O（N + E）**时间而不是**O（N ^ 2）**

#### **结论** ####

图形是存储某些类型的数据的便捷方法。该概念是从数学移植而来的，适合于计算机科学的需求。

由于许多事物可以用图形表示，因此图形遍历已成为一项常见的任务，尤其是在数据科学和机器学习中。

用代码表示图的主要两种方法是*邻接矩阵*和*邻接表*。

[0]: https://stackabuse.com/graphs-in-java-representing-graphs-in-code/#disqus_thread
[Java]: https://stackabuse.com/graphs-in-java
[DFS]: https://stackabuse.com/graphs-in-java-depth-first-search-dfs/
[BFS]: https://stackabuse.com/graphs-in-java-breadth-first-search-bfs/
[Dijkstra]: https://stackabuse.com/graphs-in-java-dijkstras-algorithm/
[1a3f99a6d351a43d1dc87cf54fada573.png]: https://img-blog.csdnimg.cn/img_convert/1a3f99a6d351a43d1dc87cf54fada573.png
[d5dc982acd40d4aa0ab8802dedf800c9.png]: https://img-blog.csdnimg.cn/img_convert/d5dc982acd40d4aa0ab8802dedf800c9.png
[2acfdacb98feced90e1686151ad1e81c.png]: https://img-blog.csdnimg.cn/img_convert/2acfdacb98feced90e1686151ad1e81c.png
[fc5699383b27c012e4de65b883ceff33.png]: https://img-blog.csdnimg.cn/img_convert/fc5699383b27c012e4de65b883ceff33.png
[bf68cea4bae22943ea7e7d5203926f4a.png]: https://img-blog.csdnimg.cn/img_convert/bf68cea4bae22943ea7e7d5203926f4a.png
[44a611913ec1a18f712a2310e7924e10.png]: https://img-blog.csdnimg.cn/img_convert/44a611913ec1a18f712a2310e7924e10.png
[0128cc3ad3ba0c659c8e151362e8440f.png]: https://img-blog.csdnimg.cn/img_convert/0128cc3ad3ba0c659c8e151362e8440f.png
[68759dc86728e1aaaba2c4033f48909a.png]: https://img-blog.csdnimg.cn/img_convert/68759dc86728e1aaaba2c4033f48909a.png