Neste tutorial, você aprenderá como criar e manipular estruturas de dados de grafos em Java. Grafos são uma estrutura de dados fundamental usada para representar relações entre objetos. Exploraremos os diferentes tipos de grafos, como representá-los e como implementar operações comuns, como adicionar e remover vértices e arestas, busca em largura (breadth-first search), busca em profundidade (depth-first search) e muito mais.
Primeiramente, criaremos uma classe Node para representar os vértices no grafo. Cada nó terá um nome e, possivelmente, outras informações, como um valor ou peso.
public class Node {
private String name;
public Node(String name) {
this.name = name;
}
public String getName() {
return name;
}
}Em seguida, criaremos uma classe Graph para representar o grafo em si. Usaremos uma lista de adjacência (adjacency list) para armazenar as arestas e seus pontos finais.
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);
}
}Agora, vamos criar um grafo e adicionar alguns nós e arestas.
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);Agora, implementaremos um algoritmo de busca em largura para percorrer os nós no grafo em ordem de busca em largura.
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;
}
}Exemplo de como executar:
javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearchAgora, implementaremos um algoritmo de busca em profundidade para percorrer os nós no grafo em ordem de busca em profundidade.
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);
}
}
}
}Exemplo de como executar:
javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearchPodemos remover um nó do grafo e também remover quaisquer arestas conectadas a esse nó.
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);Podemos remover uma aresta entre dois nós no 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);Neste tutorial, aprendemos como criar uma estrutura de dados de grafo em Java usando uma representação de nó e lista de adjacência (adjacency list). Também implementamos operações para manipular o grafo, incluindo adicionar e remover nós e arestas. Finalmente, implementamos dois algoritmos de busca: busca em largura (breadth-first search) e busca em profundidade (depth-first search).
