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是一对fromto 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 回答