如何以有限的可见性实现Java图数据结构和类

Question

我目前正在学习有关数据结构(例如linkedlist，doublylinkedlist，arraylist，...(，我想知道如何在Java中实现A(非定向(图。

。

我正在考虑两个类：Graph和Node<T>
每个节点都应该知道它连接的其他节点(List<Node<T>>是否合适？哪种列表最好？(然后，Graph类可以提供boolean contains(T element)

之类的方法

Node类将没有其他用途，因此如何限制可见性，以便只有Graph才能访问？

编辑：此外，如何权衡节点之间的连接？我想我需要与上面提到的完全不同的实现，因为一个简单的连接节点列表还不够吗？

Answer 1

图是一个有序对G =(v，e(，包括一个顶点的v 或节点或点与边缘或弧线或线的集合一起 是2元素子集

以下定义应为您提供一个清晰的方法来组织图形。它由Set<Node>和Set<Edge>组成(实现肯定是HashSet(。Edge是一对from和to Node s。Edge可以具有加权图的属性cost。如果您需要无方向的图，则可以存储两个指示的Edge s，指示一个无方向的边缘或将属性undirected添加到Edge类。

public class Graph<T> {
    private Set<Node<T>> nodes;
    private Set<Edge<T>> edges;
    private class Node<T> {
        private T value;
    }
    private class Edge<T> {
        private Node<T> to;
        private Node<T> from;
        private Number cost;
    }
}

Answer 2

您可以使节点成为这样的私人内部类：

public class Graph<T> {
    /* code */
    private class Node<T> {
        /* code */
    }
}

对于链接权重：而不是保存相邻节点作为列表，而是将它们保存为HashMap<Node, Double>，将每个节点映射到一定的权重。

注意：此实现实际上是一个有向图。

Answer 3

我建议您应该学习一个名为jgrapht的第三部分软件包，并研究其如何构建具有不同属性的图。