1

我目前正在学习数据结构（例如 LinkedList、DoublyLinkedList、ArrayList...），并且想知道如何在 Java 中实现（非定向）图。

我在考虑两个类：Graph每个Node<T>
节点都应该知道它连接到哪些其他节点（List<Node<T>>合适吗？哪种列表最好？）然后Graph该类可以提供类似的方法boolean contains(T element)

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

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

4

3 回答 3

1

您可以像这样使 Node 成为私有内部类：

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

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

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

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

于 2017-04-28T13:49:35.960 回答
1

图是一个有序对 G = (V, E)，包括一组 V 顶点或节点或点以及一组 E 边或弧或线，它们是 2 元素子集

以下定义应该为您提供一种组织图表的清晰方法。它由Set<Node>和组成Set<Edge>（实现肯定是HashSet）。Edge是一对from和to Nodes。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;
    }
}
于 2017-04-28T14:01:32.977 回答
0

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

于 2017-04-28T13:55:09.653 回答