Java - ¿Cuál es la mejor estructura de implementación para Graph?

Question

El gráfico es muy grande pero no dirigido. Los bordes no son ponderados.

En mi implementación, tengo que encontrar el vértice con grado máximo y eliminarlo en ambos vértices y bordes.

Lista enlazada? ¿Lista de arreglo? ¿Mapa?

¿Cuál es mejor para mi implementación?

Answer 1

Mi sugerencia sería almacenar los vértices en una cola de prioridad.De esta forma, puede tener un acceso muy rápido al vértice con el grado más alto. En cuanto a cómo implementar los vértices, almacenaría cada vértice vecino en algún tipo de conjunto de estructura de datos, como un HashSet o un TreeSet para poder eliminar cosas de manera eficiente. No representaría los bordes explícitamente, no es necesario.

Código, algo a lo largo de las líneas de:

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()); 
    } 

    ... 

} 

Espero que esto ayude.

Answer 2

De lo anterior sugiere que la respuesta sería

Mapa con LinkedList ...

Su estructura de datos podría ser como este (varía según su requisito) ...

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

Básicamente , Los gráficos se implementan mejor con la ayuda de HASHING y la estructura de datos anterior ayuda mucho en eso ...

Answer 3

También podría echar un vistazo a specific-d bibliotecas diseñadas, como JUNG

Answer 4

Si su algoritmo requiere buscar en grado máximo, entonces quiere una estructura de datos ordenada por grado, algo así como PriorityQueue sería bueno.

Luego debe guardar el gráfico en sí. Para eliminarlo rápidamente, recomendaría algo así como una estructura de matriz dispersa. Si tiene que usar estructuras de datos java.util, entonces un HashMap de vértices a la lista de vértices conectados ofrece O (1) eliminación.

Si pudiera usar librerías de terceros, entonces hay a list of answers here de los cuales JGraph y JUNG parecen ser los más populares.

Answer 5

Las dos estructuras de datos fundamentales para la representación de los gráficos son la

• adjacency list

• the adjacency matrix

ver http://en.wikipedia.org/wiki/Adjacency_list y http://en.wikipedia.org/wiki/Adjacency_matrix.
Los artículos también discuten los pros y los contras de esas dos estructuras.

Answer 6

Depende de qué otros requisitos tenga. Un enfoque simple e ingenuo podría ser

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

donde tendría una Lista de todos los nodos en el gráfico. El problema es que esto puede volverse inconsistente; p.ej. el nodo A podría estar en la lista de bordes del nodo B, pero el nodo B podría no estar en la lista del nodo A. Para evitar esto, se puede modelar como tal:

class Edge 
{ 
    Node incidentA; 
    Node incidentB; 
} 

class Node 
{ 
    int id; 
} 

Una vez más, tendría lista y la lista de todos los bordes y nodos en el sistema. Por supuesto, el análisis de esta estructura de datos se haría de una manera muy diferente a la del otro enfoque.

Answer 7

La implementación de gráficos depende de lo que va a hacer con ella. Pero para la mayoría de los casos, la implementación basada en listas de adyacencia ayuda.

En Java puede hacerlo usando un Mapa <>. Aquí está la implementación genérica de la Lista de Adyacencia basada en Graph.Java en mi blog.

Answer 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); 

    } 

}