El gráfico es muy grande pero no dirigido. Los bordes no son ponderados.Java - ¿Cuál es la mejor estructura de implementación para Graph?
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?
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.
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 ...
Esto no es cierto, el hash no siempre es el mejor, a veces una matriz de adyacencia es la mejor estructura. Depende del algoritmo. –
Además, no todos los mapas usan Hashing, por ejemplo TreeMap no lo hace. –
Gracias por el comentario :-) – Rites
También podría echar un vistazo a specific-d bibliotecas diseñadas, como JUNG
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.
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.
Guau, ahí tienes. –
Mi libro sobre estructuras de datos sugiere un mapa de adyacencia, que es una lista de adyacencia con la lista secundaria reemplazada por un mapa. Esto disminuye el tiempo de ejecución esperado de algunos de sus métodos. (Estructuras de datos y algoritmos en Java por Goodrich, Tamassia y Goldwasser) – Fr4nc3sc0NL
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.
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.
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);
}
}
Gracias por el código ... Nunca uso PriorityQueue antes, ¿es fácil de borrar? – user236691
Sí, es realmente simple. Si desea eliminar el elemento con mayor prioridad al mismo tiempo para recuperarlo, simplemente use el método de encuesta. La eliminación de elementos en general se realiza mediante el método de eliminación. Simplemente google "prioridad cola java" para la documentación. – svenningsson
¡Lo tengo, gracias! Una pregunta más, ¿cuál es el propósito de comparar el método en la clase de vértice? – user236691