用 Java 实现图

Question

我接到一个任务，用 java 实现一个图表。它将最终用于测试搜索方法（广度优先、深度优先和迭代加深）。要创建的三个类必须实现三个相应的接口：

public interface Node {
    public Node createNode(String name, int ID, float weight);
    public Node[] getNeighbours();
    public Edge[] getEdges();
    public void addEdge(Edge e);
    public void removeEdge(Edge e);
    public String getName();
    public int getID();
    public float getWeight();
    public String toString();

public interface Edge {
    public Edge createEdge(String name, int ID, float weight);
    public Node getStartNode();
    public void setStartNode(Node n);
    public Node getEndNode();
    public void setEndNode(Node n);
    public String getName();
    public int getID();
    public float getWeight();
    public String toString();

public interface Graph {
    public Graph createGraph(String name, int ID, Node[] nodes, Edge[] edges, Node root);
    public String getName();
    public Edge[] getEdges();
    public void addEdge(Edge e);
    public Edge getEdge(String name, int ID);
    public void removeEdge(Edge e);
    public Node[] getNodes();
    public void addNode(Node n);
    public Node getNode(String name, int ID);
    public void removeNode(Node n);
    public void setRoot(Node n);
    public Node getRoot();  
    public boolean isTree();        <= optional!
    public String toString();

main 方法将位于图类中。

我有点困惑为什么每个类都有创建方法而不是构造函数。

任何人都可以建议我是否应该使用邻接矩阵或邻接列表来存储边？

任何和所有的帮助将不胜感激。

谢谢

Answer 1

我和你一起质疑在界面中放置创建方法是否明智。接口中的方法必须在实现类中实现作为实例方法，通常像这样的方法，当它们用来代替构造函数时，是类方法，即静态工厂方法，不能出现在接口中。

在 Java 接口中拥有创建方法的唯一原因是进行克隆，但这里的情况似乎并非如此。当您实现这些接口时，创建方法将调用您的构造函数（您可以自由地以任何您想要的方式实现），但这些方法有点愚蠢，因为作为实例方法，您将需要有现有的对象来调用它们。

至于你的第二个问题，邻接矩阵、邻接表或关联表的选择完全取决于你。

Answer 2

接口不能定义构造函数。有关一些讨论，请参阅此 wiki 页面。

请参阅有关邻接表权衡的维基百科页面，了解可能引导您进行的简短讨论正确的方向。