Java - Какая лучшая структура реализации для Graph?

Ответ 1

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

Код, что-то вроде строк:

class Graph {

  PriorityQueue<Vertex> vertexes;

  public Graph() {
    vertexes = new PriorityQueue<Vertex>(10,new Vertex());
  }

  public Vertex maxDegreeVertex() {
    return vertexes.peek();
  }

  ...

}

class Vertex implements Comparator<Vertex> {
  HashSet<Vertex> edges;

  public Vertex() {
    edges = new HashSet<Vertex>();
  }

  public compare(Vertex v1, Vertex v2) {
    v2.edges.size().compareTo(v1.edges.size());
  }

  ...

}

Надеюсь, что это поможет.

Ответ 2

Две фундаментальные структуры данных для представления графов - это

• adjacency list

• the adjacency matrix

см. http://en.wikipedia.org/wiki/Adjacency_list и http://en.wikipedia.org/wiki/Adjacency_matrix.
В статьях также обсуждаются плюсы и минусы этих двух структур.

Ответ 3

Из сказанного выше ответ будет

Карта с LinkedList...

Ваша структура данных может быть такой (зависит от вашего требования)...

Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>

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

Ответ 4

Если ваш алгоритм требует поиска на максимальной степени, то вам нужна структура данных, упорядоченная по степени, что-то вроде PriorityQueue было бы хорошо.

Затем вам нужно сохранить график. Для удаления быстро я бы рекомендовал нечто вроде структуры разреженных массивов. Если вам нужно использовать структуры данных java.util, то HashMap из вершин в список подключенных вершин предлагает O (1) удаление.

Если вы можете использовать сторонние библиотеки, то есть список ответов здесь, о которых JGraph и JUNG кажутся наиболее популярными.

Ответ 5

Выполнение графика зависит от того, что вы собираетесь с ней делать. Но для большинства случаев реализация на основе списка Adjacency помогает.

В Java вы можете сделать это с помощью Map < > . Вот общий список Adjacency List, основанный на Graph.Java в моем блоге.

Ответ 6

Вы также можете взглянуть на специально разработанные библиотеки, такие как JUNG

Ответ 7

В зависимости от других требований. Наивный, простой подход может быть

class Node
{
  List<Node> edges;
  int id;
}

где у вас будет список всех узлов на графике. Проблема в том, что это может стать непоследовательным; например node A может быть в списке node B edge, но node B не может быть в списке node A. Чтобы обойти это, вы могли бы моделировать его как таковой:

class Edge
{
  Node incidentA;
  Node incidentB;
}

class Node
{
  int id;
}

Опять же, у вас будет список и список всех ребер и узлов в системе. Разумеется, анализ этой структуры данных будет выполнен совсем по-другому, чем в другом подходе.

Ответ 8

    public class Graph {
    private Set<Vertex>vertices;
    private Set<Edge>edges;
    private Map<Vertex,List<Edge>>adj;
    // Getter setter



    public Graph(Set<Vertex> vertices, Set<Edge> edges, Map<Vertex, List<Edge>> adj) {
        super();
        this.vertices = vertices;
        this.edges = edges;
        this.adj = adj;
    }
}

// Vertex class
public class Vertex {
    private String name;

    public Vertex(String name) {
        super();
        this.name = name;
    }


}

// Edge class 

public class Edge {
    private Vertex from;
    private Vertex to;
    private int weight;

    public Edge(Vertex from, Vertex to,int weight) {
        super();
        this.from = from;
        this.to = to;
        this.weight = weight;
    }


}

// Driver class 

import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void  main(String[]args) {
        Graph gr = new Graph();
        Vertex a = new Vertex("a");
        Vertex b = new Vertex("b");
        Vertex c = new Vertex("c");
        Vertex d = new Vertex("d");
        Vertex e = new Vertex("e");
        Vertex f = new Vertex("f");
        Vertex g = new Vertex("g");


        Set<Vertex>vertices = gr.getVertices();
        if(vertices == null){
            vertices  = new HashSet<>();
            vertices.add(a);
            vertices.add(b);
            vertices.add(c);
            vertices.add(d);
            vertices.add(e);
            vertices.add(f);
            vertices.add(g);
        }

        Edge ae = new Edge(a, e, 3);        
        Edge ac = new Edge(a, c, 1);
        Edge cf = new Edge(c, f, 9);
        Edge cd = new Edge(c, d, 4);
        Edge eb = new Edge(e, b, 2);
        Edge bd = new Edge(b, d, 5);
        Edge df = new Edge(d, f, 7);

    Set<Edge>edges = gr.getEdges();
    if(edges == null){
        edges = new HashSet<Edge>();
        edges.add(ae);
        edges.add(ac);
        edges.add(cf);
        edges.add(cd);
        edges.add(eb);
        edges.add(bd);
        edges.add(bd);
    }
        gr.setVertices(vertices);
        gr.setEdges(edges);

    }

}