Actualmente estoy aprendiendo sobre estructuras de datos (por ejemplo, LinkedList, DoublyLinkedList, ArrayList,...) y me preguntaba cómo implementar un gráfico (no dirigido) en Java.
Estaba pensando en dos clases: Graph y Node<T>
Cada nodo debe saber a qué otros nodos está conectado (¿es apropiado List<Node<T>> ? ¿Qué tipo de lista sería mejor?) La clase Graph podría entonces proporcionar métodos como boolean contains(T element)
La clase Node no tendría otro uso, entonces, ¿cómo restrinjo la visibilidad para que solo Graph tenga acceso?
EDITAR: además, ¿cómo puedo sopesar las conexiones entre nodos? Supongo que necesitaría una implementación completamente diferente a la mencionada anteriormente, ya que una simple lista de nodos conectados no sería suficiente.
Puede hacer que el Nodo sea una clase interna privada como esta:
public class Graph<T> { /* code */ private class Node<T> { /* code */ } } Para pesos de enlace: en lugar de guardar los nodos vecinos como una lista, guárdelos como HashMap<Node, Double> que asigna cada nodo a un cierto peso.
Nota: esta implementación sería en realidad un gráfico dirigido.
Un grafo es un par ordenado G = (V, E) que comprende un conjunto V de vértices o nodos o puntos junto con un conjunto E de aristas o arcos o líneas, que son subconjuntos de 2 elementos
La siguiente definición debería brindarle una forma clara de organizar su gráfico. Consiste en Set<Node> y Set<Edge> (la implementación seguramente sería HashSet ). Edge es un par to Node from origen y destino. Edge puede tener un cost de atributo para el gráfico ponderado. Si necesita un gráfico no dirigido, puede almacenar dos Edge dirigidos que indiquen un borde no dirigido o agregar una propiedad undirected a la clase Edge .
public class Graph<T> { private Set<Node<T>> nodes; private Set<Edge<T>> edges; private class Node<T> { private T value; } private class Edge<T> { private Node<T> to; private Node<T> from; private Number cost; } }Le sugiero que aprenda un paquete de terceros llamado JGraphT y estudie cómo construye un gráfico con diferentes atributos.