Реализация ориентированного графа в Java

Question

Я сейчас беру класс по структурам данных в java, и мы должны выяснить, как реализовать класс орграфа.
Просто я подумал, что у нас есть класс вида Linked List с полем значенияи массив полей ссылок (самоссылочных), таких как приведенный ниже код:

    public class Digraph<T>
    {
        T vertex;
        Digraph<T>[] edge;

        public Digraph(T val, int maxDegree)
        {
            vertex = val;
            edge = new Digraph<T>[maxDegree];
        }
    }

После того, как я это написал, я понял, что это не совсем бесполезный способ приближения к этому приглашению.Как я могу реализовать орграф, который не так грязен, как мой код?Или это нормальный подход?

Answer 1

Я думаю, что использование вашего связного списка для реализации графа не очень хорошая идея. В отличие от связанного списка и дерева, Graph не является рекурсивной структурой по своей природе.

Я буду реализовывать ее на основе того факта, что граф состоит из списка вершин, икаждая вершина связана со своими соседями с помощью Edges :

class Graph<E> {
    public List<Vertex<E>> vertexs; 
}

class Vertex<E> {
    public E val;
    public List<Edge<E>> connections; 
}

class Edge<E> {
    public Vertex<E> source;
    public Vertex<E> destination;
}   

Но самый простой способ представить граф - это использовать Adjacency_matrix