Реализация графа в 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();

Основной метод будет в классе графа.

Я немного сбит с толку относительно того, почему существуют методы create для каждого класса, а не конструкторы.

Также кто-нибудь может посоветовать, следует ли мне хранить ребра, используя матрицу смежности или список смежности?

Любая помощь будет принята с благодарностью.

Спасибо

Answer 1

Я с вами на вопрос о целесообразности размещения методов создания в интерфейсе. Методы в интерфейсе должны быть реализованы как методы экземпляра в реализующих классах, и обычно такие методы, когда они используются вместо конструкторов, являются методами класса, а именно статическими фабричными методами, которые не могут появляться в интерфейсах.

Единственная причина иметь метод создания в интерфейсе Java - клонирование, что здесь не так. Когда вы реализуете эти интерфейсы, методы создания будут вызывать ваш конструктор (который вы можете реализовать любым удобным для вас способом), но эти методы довольно глупы, потому что в качестве методов экземпляра вам понадобятся существующие объекты, для которых они будут вызываться.,

Что касается вашего второго вопроса, то выбор матрицы смежности, списка смежности или списка инцидентов полностью зависит от вас.

Answer 2

Интерфейсы не могут определять конструкторы. Для некоторого обсуждения, смотрите эту вики-страницу.

См. Страницу википедии о компромиссах в списке смежности для краткого обсуждения, которое может привести вас в правильном направлении.