如何实现 Java 图形数据结构和 class 可见性受限？

Question

我目前正在学习数据结构（例如 LinkedList、DoublyLinkedList、ArrayList 等），我想知道如何在 Java.

中实现（非定向）图

我在考虑两个 classes：Graph 和 Node<T>
每个节点都应该知道它连接到哪些其他节点（List<Node<T>> 合适吗？什么样的列表最好？） Graph class 可以提供像 boolean contains(T element)

这样的方法

Node class 没有其他用途，那么我如何限制可见性以便只有 Graph 可以访问？

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

Answer 1

您可以像这样使节点成为私有内部 class：

public class Graph<T> {
    /* code */

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

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

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

Answer 2

我建议你学习一个名为JGraphT的第三方包，研究它如何构建具有不同属性的图。

Answer 3

A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes or points together with a set E of edges or arcs or lines, which are 2-element subsets

以下定义应该可以让您清楚地组织图表。它由 Set<Node> 和 Set<Edge> 组成（实现肯定是 HashSet）。 Edge 是一对 from 和 to Node。 Edge 可以有一个属性 cost 用于加权图。如果您需要无向图，您可以存储两个有向 Edge 表示一个无向边或将属性 undirected 添加到 Edge class.

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;
    }
}

如何实现 Java 图形数据结构和 class 可见性受限？

How to implement Java graph data-structure and class with restricted visibility?

java

data-structures

graph

visibility

class-visibility