Una de las estructuras de datos más complejas y más útiles son los grafos (Graphs), en este post se explicará paso a paso como implementar uno en Java. Para este ejemplo se creará uno sobre algunas de las ciudades que se encuentran en México.
Conceptos básicos
Antes de crear el grafo debemos entender algunos conceptos básicos:
- Vértice (Vertex) : Es un punto donde varias líneas se unen
- Arista (Edge) : Es un término matemático que representa una línea que conecta 2 vértices
- Grafo (Graph) : Es el término que representa un conjunto de vértices y aristas.
Ejemplo práctico
En el ejemplo que se presentará se creará un Grafo de ciudades, cada nodo será una ciudad (DF, Toluca, Cuernavaca, Puebla y Tlaxcala) que se unirán con un conjunto de aristas con su distancia, la siguiente imagen es una representación gráfica:
Creando el modelo
Como siempre el primer paso será crear el modelo con las clases a utilizar, para esto crearemos 3 clases Node, Edge y Grap que serán mostradas a continuación:
Node.java
import java.util.ArrayList; import java.util.List; /** * @author raidentrance * */ public class Node { private String city; private List<Edge> edges; public Node(String city) { this.city = city; } public String getCity() { return city; } public void setCity(String city) { this.city = city; } public List<Edge> getEdges() { return edges; } public void addEdge(Edge edge) { if (edges == null) { edges = new ArrayList<>(); } edges.add(edge); } @Override public String toString() { return "\n \tNode [city=" + city + ", edges=" + edges + "]"; } }
Edge.java
/** * @author raidentrance * */ public class Edge { private Node origin; private Node destination; private double distance; public Edge(Node origin, Node destination, double distance) { this.origin = origin; this.destination = destination; this.distance = distance; } public Node getOrigin() { return origin; } public void setOrigin(Node origin) { this.origin = origin; } public Node getDestination() { return destination; } public void setDestination(Node destination) { this.destination = destination; } public double getDistance() { return distance; } public void setDistance(double distance) { this.distance = distance; } @Override public String toString() { return "\n Edge [origin=" + origin.getCity() + ", destination=" + destination.getCity() + ", distance=" + distance + "]"; } }
Graph
import java.util.ArrayList; import java.util.List; /** * @author raidentrance * */ public class Graph { private List<Node> nodes; public void addNode(Node node) { if (nodes == null) { nodes = new ArrayList<>(); } nodes.add(node); } public List<Node> getNodes() { return nodes; } @Override public String toString() { return "Graph [nodes=" + nodes + "]"; } }
A continuación se presenta la explicación:
- Un Graph contiene una lista de nodos
- Cada nodo contiene el nombre de una ciudad y una lista de aristas
- Cada arista contiene la unión de las ciudades así como la distancia entre ellas
Creando el grafo de ciudades
Una vez que se creó el modelo el siguiente paso será llenarlo con la información de las ciudades.
/** * @author raidentrance * */ public class MapRepresentation { public static Graph getCities() { Node df = new Node("DF"); Node toluca = new Node("Toluca"); Node cuernavaca = new Node("Cuernavaca"); Node puebla = new Node("Puebla"); Node tlaxcala = new Node("Tlaxcala"); df.addEdge(new Edge(df, toluca, 100)); df.addEdge(new Edge(df, cuernavaca, 90)); toluca.addEdge(new Edge(toluca, cuernavaca, 150)); toluca.addEdge(new Edge(toluca, puebla, 350)); toluca.addEdge(new Edge(toluca, tlaxcala, 340)); cuernavaca.addEdge(new Edge(cuernavaca, puebla, 100)); puebla.addEdge(new Edge(puebla, tlaxcala, 20)); Graph graph = new Graph(); graph.addNode(df); graph.addNode(toluca); graph.addNode(cuernavaca); graph.addNode(puebla); return graph; } public static void main(String[] args) { Graph graph = getCities(); System.out.println(graph); } }
Salida:
Graph [nodes=[ Node [city=DF, edges=[ Edge [origin=DF, destination=Toluca, distance=100.0], Edge [origin=DF, destination=Cuernavaca, distance=90.0]]], Node [city=Toluca, edges=[ Edge [origin=Toluca, destination=Cuernavaca, distance=150.0], Edge [origin=Toluca, destination=Puebla, distance=350.0], Edge [origin=Toluca, destination=Tlaxcala, distance=340.0]]], Node [city=Cuernavaca, edges=[ Edge [origin=Cuernavaca, destination=Puebla, distance=100.0]]], Node [city=Puebla, edges=[ Edge [origin=Puebla, destination=Tlaxcala, distance=20.0]]]]]
Si observamos la salida del programa podemos ver que cada ciudad cuenta con sus aristas que representan la unión de ambos puntos y cuenta con la distancia entre ellas como se mostró en la imagen.
Siguientes pasos
En próximos posts se explicará ejecutar algoritmos sobre este grafo, agregar dirección a las aristas y muchas más operaciones, si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.
Autor: Alejandro Agapito Bautista
Twitter: @raidentrance
Contacto:raidentrance@gmail.com
Muchas gracias, realmente me ayudaste, lo unico es como sacar el camino mas corto y si tuviera costos el camino mas barato
Me gustaLe gusta a 1 persona