Estructuras de datos de grafos en Java

Introducción

En este tutorial, aprenderá a crear y manipular estructuras de datos de gráficos en Java. Los gráficos son una estructura de datos fundamental utilizada para representar relaciones entre objetos. Exploraremos los diferentes tipos de gráficos, cómo representarlos y cómo implementar operaciones comunes como agregar y eliminar vértices y aristas, búsqueda en anchura, búsqueda en profundidad y más.

Crea una clase Nodo

Primero, crearemos una clase Node para representar los vértices en el gráfico. Cada nodo tendrá un nombre y posiblemente otra información, como un valor o un peso.

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

Crea una clase Grafo

A continuación, crearemos una clase Graph para representar el grafo en sí mismo. Usaremos una lista de adyacencia para almacenar las aristas y sus extremos.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1!= null) {
            list1.remove(node2);
        }
        if (list2!= null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

Crea un grafo

Ahora, vamos a crear un grafo y agregar algunos nodos y aristas.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

Búsqueda en Anchura

Ahora implementaremos un algoritmo de búsqueda en anchura para recorrer los nodos del grafo en orden de anchura.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

Ejemplo de cómo ejecutar:

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

Búsqueda en Profundidad

Ahora implementaremos un algoritmo de búsqueda en profundidad para recorrer los nodos del grafo en orden de profundidad.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

Ejemplo de cómo ejecutar:

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

Eliminar un nodo

Podemos eliminar un nodo del grafo y también eliminar cualquier arista conectada a ese nodo.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

Eliminar un borde

Podemos eliminar una arista entre dos nodos del grafo.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

需要注意的是，你提供的代码中graph.addEdge(nodeB, nodeC);这里的nodeC未定义，我按照原文翻译了，但实际代码可能存在问题。

Resumen

En este tutorial, aprendimos cómo crear una estructura de datos de grafo en Java utilizando una representación de nodos y lista de adyacencia. También implementamos operaciones para manipular el grafo, incluyendo la adición y eliminación de nodos y aristas. Finalmente, implementamos dos algoritmos de búsqueda: búsqueda en anchura y búsqueda en profundidad.